数据结构——快排与归并

排序算法

• 前言
• 一、快速排序
• • hoare版本
  • 挖坑法
  • 前后指针版本
  • 快速排序优化：
  • 快速排序非递归
  • 快速排序的特性总结：
  • 二、归并排序
  • • 基本思想：
    • 归并排序的特性总结：
    • 总结

      ---

      前言

      重要的事说三遍！

      学习！学习！学习！

      努力!努力!努力！

      ---

      一、快速排序

      快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

      快排中心思想代码演示：

      // 假设按照升序对array数组中[left, right)区间中的元素进行排序
      void QuickSort(int array[], int left, int right)
      {
       if(right - left <= 1)
       return;
       
       // 按照基准值对array数组的 [left, right)区间中的元素进行划分
       int div = partion(array, left, right);
       
       // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
       // 递归排[left, div)
       QuickSort(array, left, div);
       
       // 递归排[div+1, right)
       QuickSort(array, div+1, right);
      }
      

      将区间按照基准值划分为左右两半部分的常见方式有：

      hoare版本

      

      

      代码实现：

      // 三数取中
      int GetMidi(int* a, int left, int right)
      {
      	int mid = (left + right) / 2;
      	// left mid right
      	if (a[left] < a[mid])
      	{
      		if (a[mid] < a[right])
      		{
      			return mid;
      		}
      		else if (a[left] > a[right])  // mid是最大值
      		{
      			return left;
      		}
      		else
      		{
      			return right;
      		}
      	}
      	else // a[left] > a[mid]
      	{
      		if (a[mid] > a[right])
      		{
      			return mid;
      		}
      		else if (a[left] < a[right]) // mid是最小
      		{
      			return left;
      		}
      		else
      		{
      			return right;
      		}
      	}
      }
      //hoare
      int PartSort1(int* a, int left, int right)
      {
      	int midi = GetMidi(a, left, right);
      	Swap(&a[left], &a[midi]);
      	int keyi = left;
      	while (left < right)
      	{
      		// 找小
      		while (left < right && a[right] >= a[keyi])
      		{
      			--right;
      		}
      		// 找大
      		while (left < right && a[left] <= a[keyi])
      		{
      			++left;
      		}
      		Swap(&a[left], &a[right]);
      	}
      	Swap(&a[keyi], &a[left]);
      	return left;
      };
      

      为什么要有三数取中这个函数呢？

      那我们不妨设想一下，如果我们传过去的数组是有序的呢！

      

      三数取中无疑会使这种算法趋近理想最佳化

      

      挖坑法

      

      

      代码实现：

      int PartSort2(int* a, int left, int right)
      {
      	int midi = GetMidi(a, left, right);
      	Swap(&a[left], &a[midi]);
      	int key = a[left];
      	// 保存key值以后，左边形成第一个坑
      	int hole = left;
      	while (left < right)
      	{
      		// 右边先走，找小，填到左边的坑，右边形成新的坑位
      		while (left < right && a[right] >= key)
      		{
      			--right;
      		}
      		a[hole] = a[right];
      		hole = right;
      		// 左边再走，找大，填到右边的坑，左边形成新的坑位
      		while (left < right && a[left] <= key)
      		{
      			++left;
      		}
      		a[hole] = a[left];
      		hole = left;
      	}
      	a[hole] = key;
      	return hole;
      }
      

      前后指针版本

      

      

      代码实现：

      int PartSort3(int* a, int left, int right)
      {
      	int midi = GetMidi(a, left, right);
      	Swap(&a[left], &a[midi]);
      	int prev = left;
      	int cur = prev + 1;
      	int keyi = left;
      	while (cur <= right)
      	{
      		if (a[cur] < a[keyi] && ++prev != cur)
      		{
      			Swap(&a[prev], &a[cur]);
      		}
      		++cur;
      	}
      	Swap(&a[prev], &a[keyi]);
      	return prev;
      }
      

      快速排序递归代码：

      void QuickSort(int* a, int begin, int end)
      {
      	if (begin >= end)
      		return;
      	int keyi = PartSort3(a, begin, end);//此处调用前后指针快排，也可调用其他两种排序方法
      	// [begin, keyi-1] keyi [keyi+1, end]
      	QuickSort(a, begin, keyi - 1);
      	QuickSort(a, keyi+1, end);
      }
      

      快速排序优化：

      递归到小的子区间时，可以考虑使用插入排序

      当数组递归到一定程度后，所进行排序的数据个数较小，在这个时候使用插入排序的效率反而会比继续快排递归的效率要高

      代码实现：

      void QuickSortOp(int* a, int begin, int end)
      {
      	if (begin >= end)
      		return;
      	// 小区间优化，小区间不再递归分割排序，降低递归次数
      	if ((end - begin + 1) > 10)
      	{
      		int keyi = PartSort3(a, begin, end);//调用前后指针快排
      		// [begin, keyi-1] keyi [keyi+1, end]
      		QuickSortOp(a, begin, keyi - 1);
      		QuickSortOp(a, keyi + 1, end);
      	}
      	else//当排序的数据个数小于或等于10个时，使用插入排序
      	{
      		InsertSort(a + begin, end - begin + 1);
      	}
      }
      

      为了验证这种排序是否有优化效果，我们可以将两种排序进行比较：

      void TestOP()
      {
      	srand(time(0));
      	const int N = 100000;
      	int* a1 = (int*)malloc(sizeof(int) * N);
      	int* a2 = (int*)malloc(sizeof(int) * N);
      	for (int i = N - 1; i >= 0; --i)
      	{
      		a1[i] = rand();
      		a2[i] = a1[i];
      	}
      	int begin1 = clock();
      	QuickSortOp(a1, 0, N - 1);
      	int end1 = clock();
      	int begin2 = clock();
      	QuickSort(a2, 0, N - 1);
      	int end2 = clock();
      	printf("QuickSortOp:%d\n", end1 - begin1);
      	printf("QuickSort:%d\n", end2 - begin2);
      	
      	free(a1);
      	free(a2);
      }
      

      运行结果：

      

      从运行结果可以看出，优化之后的效率是要高于优化前的效率的

      快速排序非递归

      我们可以用栈来进行非递归快排的代码实现

      

      记得在实现代码之前引入栈的定义代码哦！

      对于栈不清楚的话链接在这里：栈

      代码实现：

      void QuickSortNonR(int* a, int begin, int end)
      {
      	ST st;
      	STInit(&st);
      	STPush(&st, end);
      	STPush(&st, begin);
      	while (!STEmpty(&st))
      	{
      		int left = STTop(&st);
      		STPop(&st);
      		int right = STTop(&st);
      		STPop(&st);
      		int keyi = PartSort1(a, left, right);
      		// [lefy,keyi-1] keyi [keyi+1, right]
      		if (keyi + 1 < right)
      		{
      			STPush(&st, right);
      			STPush(&st, keyi + 1);
      		}
      		if (left < keyi - 1)
      		{
      			STPush(&st, keyi - 1);
      			STPush(&st, left);
      		}
      	}
      	STDestroy(&st);
      }
      

      快速排序的特性总结：

      1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
      2. 时间复杂度：O(N*logN)
      3. 空间复杂度：O(logN)
      4. 稳定性：不稳定

      二、归并排序

      基本思想：

      归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

      

      代码实现：

      void _MergeSort(int* a, int* tmp, int begin, int end)
      {
      	if (end <= begin)
      		return;
      	int mid = (end + begin) / 2;
      	// [begin, mid][mid+1, end]
      	_MergeSort(a, tmp, begin, mid);
      	_MergeSort(a, tmp, mid + 1, end);
      	// 归并到tmp数据组，再拷贝回去
      	// a->[begin, mid][mid+1, end]->tmp
      	int begin1 = begin, end1 = mid;
      	int begin2 = mid + 1, end2 = end;
      	int index = begin;
      	while (begin1 <= end1 && begin2 <= end2)
      	{
      		if (a[begin1] < a[begin2])
      		{
      			tmp[index++] = a[begin1++];
      		}
      		else
      		{
      			tmp[index++] = a[begin2++];
      		}
      	}
      	while (begin1 <= end1)
      	{
      		tmp[index++] = a[begin1++];
      	}
      	while (begin2 <= end2)
      	{
      		tmp[index++] = a[begin2++];
      	}
      	// 拷贝回原数组
      	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
      }
      void MergeSort(int* a, int n)
      {
      	int* tmp = (int*)malloc(sizeof(int) * n);
      	if (tmp == NULL)
      	{
      		perror("malloc fail");
      		return;
      	}
      	_MergeSort(a, tmp, 0, n - 1);
      	free(tmp);
      }
      

      归并排序的特性总结：

      1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。2. 时间复杂度：O(N*logN)
      2. 空间复杂度：O(N)
      3. 稳定性：稳定

      ---

      总结

      重要的事说三遍！

      成功！成功！成功！

      加油吧！从现在开始~