探索数据结构：快速排序与归并排序的实现与优化

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

养成好习惯，先赞后看哦~

所属专栏：数据结构与算法

贝蒂的主页：Betty’s blog

1. 快速排序

1.1. 算法思想

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

1.2. 算法实现

快速排序的实现方式有很多，下面我们主要介绍三种方法。

1.2.1. Hoare法

1. 利用两个变量left，right分别指向数组的起始位置与末尾位置。并且以数组第一个元素作为key值。
2. right先从右往左依次遍历找到比key小的数，left从左往右依次遍历找到比key大的数。然后交换left与right下标对应的值。重复步骤2直至right>=left。
3. 之后交换key与left或者right对应的值，并且把该位置记为mid。
4. 最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2步骤。直至不能划分。

思考：为什么最后相遇位置一定小于或等于**key**值？

我们知道right与left相遇无非两种情况：

1. 情况一：right停住，left移动与right相遇·。因为right一直再找比key小的值，所以right停下位置一定比key小，相遇位置也一定比key小。
2. 情况二：left停住，right移动与left相遇·。此时又分为两种情况：

• left从未移动，右侧数据都比可以大，相遇位置就是key，交换不变。
• left移动过至少一次，也就是至少交换过一次，此时left停留位置的值是上一轮right所对应的值，又因为right一直再找比key小的值，所以相遇位置也一定比key小。

  代码实现：

  void swap(int* p1, int* p2){int tmp = *p1;*p1 = *p2;*p2 = tmp;}int PartSort1(int* arr, int begin, int end){int left = begin, right = end;int keyi = begin;while (left 防止数据出现***循环while (left=arr[keyi])//寻找比key小的值{right--;}while (left  
  1.2.2. 挖坑法
     
  先将起始位置key值 设为坑，之后right从右往左找比key值小的值，找到之后放入坑位，此时right就形成新的坑。然后left从左往右找比key大的值， 找到之后放入坑位，此时left就又形成新的坑。
  最后left与right相遇，将key放入最后一个坑，并将该位置记为mid，。·
  最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2步骤。直至不能划分。
    
  代码实现：
   
  int PartSort2(int* arr, int begin, int end){int left = begin, right = end;int hole = begin;//记录坑位int key = arr[left];while (left 防止数据出现***循环while (left = key)//寻找比key小的值{right--;}arr[hole] = arr[right];hole = right;while (left  
  1.2.3. 前后指针法
     
  先定义一个prev指向数组首元素，然后定义一个cur指向第二个位置。
  cur从左往右依次遍历找key小的值，找到之后++prev，然后交换prev与cur指向的值。之后cur++继续遍历。(key为起始位置的值)
  当cur遍历完之后，此时交换prev指向的值与key。将此时位置记为mid。
  最后划分区间[left，mid-1]与[mid+1,right]继续重复1,2,3步骤。直至不能划分。
    
  代码实现：
   
  int PartSort3(int* arr, int begin, int end){int prev = begin;int cur = begin + 1;int keyi = begin;while (cur if (arr[cur]  
  1.3. 复杂度分析
   

  • 时间复杂度：通常情况下，需要递归logN层，每层都需要遍历，所以时间复杂度为O(NlogN)。
  • 空间复杂度：通常情况下，需要递归logN层，所以空间复杂度为O(logN)。

    1.4. 算法优化

    1.4.1. 改变基准元素

    当数组有序时，我们再对其进行快速排序，其时间复杂度讲话劣化为O(N2)。

    这时候我们为了防止这种现象，可以选择提前改变基准元素key。

    • 三数取中：即取出数组首尾以及中间元素，选取数值位于中间的元素作为准元素key。

      int GetMidNum(int*arr, int left, int right){int mid = (left + right) >> 1;if (arr[mid] > arr[left]){if (arr[mid]  arr[right]){//right  left  midreturn left;}else{//left  right  midreturn right;}}}int PartSort3(int* arr, int begin, int end){int prev = begin;int cur = begin + 1;int keyi = begin;int mid=GetMidNum(arr, begin, end);swap(&arr[begin], &arr[mid]);while (cur if (arr[cur] right,成功划分区间。小于key：[begin,left-1]，等于key：[left, right] 大于key：[right + 1, end]。

    问题：为什么当arr[cur]>key，交换arr[cur]与arr[right]时不让cur++？

    因为交换过来的值可能比key大，也可能比key小。如果直接cur++，并不能对这个元素进行正确的划分。

    void ThreeDivision(int*arr, int*left, int*right){int cur = *left + 1;int key = arr[*left];while (cur if (arr[cur] = end)//不能划分{return;}if ((end - begin + 1)  
    1.4.3. 区间优化
     
    在我们进行递归调用时，递归越深递归调用的次数就会越多，为了优化这个问题，我们可以当区间较小时采用其他排序。
     
    其中我们将递归调用抽象成树的形式：
      
    其中根据我们在树那节学习的知识，我们知道第i层的节点数为2i-1 个，节点总数为2h -1个，**最后三次调用次数就约占据总次数的87.5%。**所以我们可以在倒数三层之后采用其他排序，如插入排序。
     
    void QuickSort(int* arr, int left, int right){if (left >= right)//不能划分{return;}if ((right - left + 1)  
    1.4.4. 尾递归优化
     
    我们知道快速排序的空间复杂度最坏情况下会劣化为O(N)，为了防止栈帧空间的积累，我们可以采用尾递归形式进行递归，并且仅对较短的子数组进行递归。由于较短子数组的长度不会超过n/2，因此这种方法能确保递归深度不超过logN ，从而将最差空间复杂度优化至O(logN) 。
     
    void QuickSort(int* arr, int begin, int end){while (begin > 1;//以中间为分割点_MergeSort(arr, begin, mid, tmp);//归并左区间_MergeSort(arr, mid+1, end, tmp);//归并右区间int i = begin;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;while (begin1 if (arr[begin1]