基础排序算法-快排的非递归和归并的具体实现

目录

快排的非递归实现：

归并排序：

归并排序的非递归实现：

内、外排序 

上文：7大排序算法-- 堆排 快速排序 --精解_luck++的博客-CSDN博客_堆排序 快速排序

快排的非递归实现：

我们知道快排的实现效率很高 但是它还是有个弊端 就是我们本身栈这个空间不大  所以一旦我们的递归太深 这个空间就不够用了 所以我们在一些情况下得 把快排改成分递归得形式

要改成非递归得形式得用到 数据结构中的 栈来实现 

我先把代码放出来 大家先看看：

int PartSort3(int* a, int left, int right)
{
	int tmp = CheckMidKey(a, (right - left + 1) >> 1, left, right);//改变选keyi的方式
	swap(a + left, a + tmp);

	int prev, cur;
	int keyi = left;

	prev = left;
	cur = left + 1;
	while (cur <= right)
	{

		if (a[cur] <= a[keyi] && a[++prev] != a[cur])//附加的判断条件 意思是我的prev和cur中
		{                                            //间交换得有值才让
			swap(a + prev, a + cur);
		}
		cur++;
	}
	swap(a + keyi, a + prev);
	return prev;
}

void QuickSortNonR(int* a, int left, int right)//快排的非递归实现
{
	St tmp;
	StackInit(&tmp);

	StackPush(&tmp, left);
	StackPush(&tmp, right);

	while (!StackIsEmpty(&tmp))
	{
		right = StackTop(&tmp);
		StackPop(&tmp);
		left = StackTop(&tmp);
		StackPop(&tmp);

		int keyi = PartSort3(a, left, right);//排完会把keyi位置的值的正确位置排好

		if (left < keyi - 1)// 等于的时候只有一个数据就不用排了
		{
			StackPush(&tmp, left);
			StackPush(&tmp, keyi - 1);
		}

		if (right > keyi + 1)
		{
			StackPush(&tmp, keyi + 1);
			StackPush(&tmp, right);
		}
	}

	StackDestory(&tmp);
}

 在我们使用栈实现之前 我们要知道栈是后进先出的 也就是栈是始终在数据的尾端进行操作的无论是入数据还是出数据

我们整体的思路是 

① 我们利用 栈 把 表示区间的两个数字 存储 到栈的这种数据结构中 

② 每次要使用时就把这段区间 拿出来使用(拿出来后还要把它删掉) 毕竟我们找keyi的函数的 参数 就是一个区间

③ 使用完 我们根据这个区间选出的 keyi 把它的左右区间 入到栈中 区间只有一个数据不入 区间不存在也是

④ 反复循环 直到栈里面没有区间了

 后面的操作都是一样的直到 我们的栈中没有数据了 

大区间->选keyi->小区间->选keyi->小小区间。。。。

当不再入区间后区间后就会 就轮到出 这个区间前面的区间 这样我们不就模拟了一个递归返回的操作了嘛 

大家看整体是不是和我们递归的操作是一样的内 我们只是用栈来暂时存储我们的区间的数字就可以实现递归的效果！！

实际上按照这样的思想来写的话其实用对列的数据结构来实现的话也是可以的  这不过这个时一层一层(区间逐渐分下来的一种结构)遍历下来的

归并排序：

归并排序其实就和 它的名字一样 是把两组数据归并成一组有序的数据 但有个前提是我们的两组数据的是有序的才行 (后面会说到是为什么 大家也可以先想一想) 时间复杂度：O(N*logN) 空间复杂度：O(N) 稳定性：稳定

我们先看归并排序的思路：

① 我们对两组设置对应的 用于遍历数据的 变量 

② 两组数据从头开始比较 哪一边小 那么这个这边的这个数就要放到我们预先开辟的数组里面(如果是链表的结构 直接插到比他小的数就可以了 如果没有 那么它就做第一个数据) 放完这个对应的变量 ++

这个是 两组数据 不有序 的情况： 

 这个就是 归并排序 的 思想 可是给我们的通常是一组无序的数据 如果只是单单把这组数据分成两部分 那这两部分我们又不能保证他们是有序的

所以我们可以把他们分割成 单个数为一组 不就可以了嘛 毕竟一个数肯定是有序的不是嘛

 现在大家看完思路后 来实现我们的代码吧 (因为我们要开辟一个数组 而我们的分割操作是要用到递归的 所以只写一个函数的话 那每递归一次就会开辟一次 所以我们还要新建一个子函数)

void _MergeSort(int* a, int left, int right, int* tmp)//归并排序
{
	if (left >= right) return;//只有一个数 区间不存在 返回

	int mid = (left + right) >> 1;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
}

这个是我们写的 分割部分 的函数 注意这里我们的区间设置是：

[left,mid] [mid+1,right]

因为我的编译器默认是向下取整的 所以我们的右半区间 应该是 mid+1 

    int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2]) tmp[index++] = a[begin2++];
		else tmp[index++] = a[begin1++];
	}

	while (begin1 <= end1) tmp[index++] = a[begin1++];
	while (begin2 <= end2) tmp[index++] = a[begin2++];
	memmove(a + left, tmp + left, sizeof(int) * (right - left + 1));

    因为很有可能我们在归并的时候我们有一组数据已经排完了 这个时候就要停下来了 因为还有剩的这一组数据就可以直接加到我们最终归并的数组里面去了        

    因为我们剩下的一组数据的第一个数据肯定是大于已经排完的那组中所有数据的(我们是小的先移进去大的留下来)而这个时候我们之前说过要保证我们我们两组数据是有序的 所以直接放进去的剩下的数据是一定比之前数据都大的数 且是有序的！！！

归并排序的非递归实现：

现在我们要实现归并的非递归，那我们要怎样把他们分成一个一个为一组呢，其实我们可以换个思路，又不是一定要把它分组，我们自己设置组不就好了嘛，我们想让它多少个为一组就让它多少个为一组，就好像是这样

 我们的一组的个数只要超过总个数就停下来，所以是不是用两个循环就可以搞定，大家来看我们的代码：

    int* tmp = (int*)malloc(sizeof(int) * n);
	assert(tmp);
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)//换到下一个要归并的两组数据
		{
			int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1;

			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] > a[begin2]) tmp[index++] = a[begin2++];
				else tmp[index++] = a[begin1++];
			}

			while (begin1 <= end1) tmp[index++] = a[begin1++];
			while (begin2 <= end2) tmp[index++] = a[begin2++];

		}
		memcpy(a, tmp, sizeof(int) * n);//我们排完要把排完的再拷回去进行下一层的排序
		gap *= 2;
	}

 但是我们现在的代码并不能很好排序任何数据  因为这里面还涉及我们的边界问题  我们每次gap都是成倍增长  我们划分的区间也是跟随gap变化  所以我们的区间是很有可能越界的   包括到那些不是数组里面的数据

            if (end1 >= n) end1 = n - 1;
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (end2 >= n) end2 = n - 1;

 1.第一个边界处理：这里虽然我们的end1大于end了，那我们的begin2肯定也是大于n的，我们的第二个边界处理是为了让第二个区间不存时不进入第一个while循环，我们虽不会进入第一个循环，这里我们后面不是还有两个while循环嘛(这两个循环是处理剩余数据的)，但是这里它会进去啊，进去一访问不就越界了嘛

2.第二个边界处理：这里的begin1大于了n，那我们的第二个区间就不存在了，后面的所有while循环都不能参加了，所以我们自己改变begin2和end2的大小，begin2>end2，这样我们的区间不存在，后面的循环也就没它的戏了

3.第三个边界同样也是为了防止最后那两个循环，不能让它访问的时候造成越界的问题

非递归和递归的空间复杂度和时间复杂度是一样的 时间复杂度：O(N*logN) 空间复杂度：O(N)

内、外排序 

我们之前学的这几个排序都是可以时内排序，内排序的意思就是在内存中进行排序，外排序就是在磁盘中进行排序(这个时候也就意味着我们的数据很大了)

我们的内排序也更快，相对的外排序就会慢一些；内存中的数据可以使用下标随机访问，但磁盘里的数据不可以，我们访问磁盘数据的形式是文件，我们使用那些文件操作函数的时候，都是串行访问的

 如果我们想要排文件里面的数据，就要把文件里面的数据大小切分成几个适合内存大小的几个小文件，把这几个小文件中的数据放到内存中去排序(别使用归并，会额外开一个空间)，再把排序完的数据拿回来，再在磁盘中对这几个小文件进行归并，合成一个大的有序的文件

谢谢大家看到这里，预祝大家都能收到自己心仪大厂的offer！！！