算法介绍

      顾名思义，快速排序(Quick Sort)是实践中的一种快速的排序算法，由C. A. R. Hoare在1960年提出，排序效率在同为O(NlogN)的几种排序算法中较高，在C++或对Java基本类型的排序中特别有用。快速排序其实是在冒泡排序的基础上做出的一个改进，和归并排序一样，快速排序也是一种利用分治思想的递归算法。

算法描述

实现快速排序包含三个最重要的步骤：

 一、选取枢纽元(从数列中选取的一个基准数)

 二、分割过程：将比枢纽元小的数全放到它的左边，大于或等于它的数全放到它的右边。

 三、递归处理左右子序列，直到每个数都处在正确位置。

如下图所示：

动图演示

算法分析

 时间复杂度：平均O(NlogN)， 最坏O(N²)

 空间复杂度：O(logN)

 稳定性：不稳定

算法优化

一、优化的内部循环

     使用高度优化的内部循环，避免使用大量内存，可将尾递归优化为循环结构(大部分优秀的编译器将自动完成)。

二、选取枢纽元

（1）一种错误的方法：

      通常的、无知的选择是将第一个元素用作枢纽元，如果输入是随机的，那么这是可以接受的，而如果输入是预排序或者反序的，那么就会产生一个劣质的分割(严重不均衡)，更严重的是，这种情况将发生在所有的递归调用中，快速排序的运行时间将退化为二次。值得一提的是，预排序的输入(或具有一大段预排序数据的输入)是十分常见的，因此，使用第一个元素作为枢纽元是很失败的决定，另一种想法是选取前两个互异的关键字中较大的一个作为枢纽元，与前一种想法拥有同样的坏处，所以不建议使用这两种方法选取枢纽元。

（2）一种安全的做法：

     一种安全的选取方法是随机选取枢纽元，一般来说这种方法是非常安全的，除非随机数生成器出现问题(出现几率极小)，因为随机的枢纽元不可能总是产生劣质的分割。另一方面，随机数的生成开销很大，一定程度上增加了平均运行时间。

（3）三数中值分割法：

      一组N个数的中值（也叫作中位数）是第N/2大的数，枢纽元的最好选择就是数组的中值，但这很难算出并且会明显减慢快速排序的速度。这样的中值可以通过随机选取三个元素并用它们的中值作为枢纽元，这样又会用到随机数，那为何不直接用（2）方案呢？事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端、中间位置上的三个元素的中值作为枢纽元。例如，输入序列为[6,1,4,2,0,3,5]它的左端元素是6，右端元素是5，中间元素是2。于是枢纽元就是5，显然使用三数中值分割法消除了预排序输入的坏情况，并且实际减少了14%的比较次数。

三、小数组

      对于很小的数组(N <= 20)，快速排序不如直接插入排序，不仅如此，因为快速排序是递归的，所以这种情况经常发生。通常的解决办法是对于小数组不使用递归的快速排序，而代之以直接插入排序等对小数组有效的排序算法。使用这种策略实际可节约大约15%(相对于不使用此策略)的运行时间，一种好的截止范围是N = 10，虽然在5到20之间任一种截止范围都有可能产生类似的结果。这种做法也避免了一些有害的退化情况，如三个元素的中值实际只有一个或两个元素的情况。

四、相同枢纽元聚集

       在一次排序后，将与枢纽元相等的数放在一起，在下次分割时可以不考虑这些数。例如，输入序列为[6,5,5,2,0,3,5]经过一次递归排序后[2,0,3,5,5,5,6],下次递归调用只需要处理[2,0,3]和[6]，这种聚集与枢纽元相等的值的优化方法，在解决数据冗余的情况下非常有用，提高的效率也是非常多。

五、与其它O(NlogN)排序算法比较

      一、堆排序最坏时间复杂度、空间复杂度都优于快速排序，为什么实践中更多使用快排而不是堆排呢？

     （1）快速排序的过程中，访问数据是顺序进行访问的，而且有非常精练和高度优化的内部循环，但是在堆排序中，需要维护堆性质，导致需要跳着数组下标去进行访问元素，对CPU缓存不友好。

     （2）堆排序过程使用更多的比较次数，值得一提的是，对于不同的语言，比较的代价是不同的，具体可参考归并排序的分析。

 二、与归并排序的比较详情参考归并排序的分析。

六、与堆排序的结合

      通过将快速排序和堆排序结合，由于堆排序的O(NlogN)最坏时间复杂度，我们可以对几乎所有的输入都能到达快速排序的快速运行时间，该算法的最坏运行时间为O(NlogN)。

优化总结

     对于经典快速排序，效率最高的优化方案应该是三数中值分割法 + 小数组处理 + 聚集相等枢纽元，对于尾递归的优化可有可无(编译器自动优化)，对于效率的改变不大。算法效率还与具体的实现语言相关，详情可查看归并排序分析。

代码实现

      以下一种快速排序的实现是大量分析和经验研究的结果，它代表实现快速排序的非常有效的一种方法(三数中值分割法 + 小数组处理)，即使是对该方法最微小的偏差都可能引起意想不到的坏结果。其中一些细节地方值得读者细细品味，相信读者一定会有所收获。

// C++ 
class QuickSort {  // 快速排序类 
public:
  // 快排驱动程序1(全排序)
  vector<int> quickSort(vector<int>& nums) {   
  quicksort(nums, 0, nums.size() - 1);  // 调用私有方法quickSort排序 
  return nums;  // 返回已排序对象 
  }
  // 快排驱动程序2(部分排序)
  vector<int> quickSort(vector<int>& nums, int left, int right) {   
  quicksort(nums, left, right);  // 调用私有方法quickSort排序 
  return nums;  // 返回已排序对象 
  }
private:
  const int CUTOFF = 10;  // 小数组判定界限 
  // 快速排序递归函数 
  void quicksort(vector<int>& nums, int left, int right) {  
  if (left + CUTOFF <= right) {  // 判定是否为小数组 
    int pivot = median(nums, left, right);  // 选取枢纽元 
    int i = left;  // 左边起始位置之前 
    int j = right - 1;  // 右边起始位置之后 
    for (;;) {  // 双指针遍历 
    while (nums[++i] < pivot) { }  // 从左找到第一个大于枢纽元的值 
    while (nums[--j] > pivot) { }  // 从右找到第一个小于枢纽元的值 
    if (i < j) {  // 未完成一次遍历 
      swap(nums[i], nums[j]);  // 交换nums[i]和nums[j]的值 
    } else {  // 完成一次遍历 
      break;  // 退出循环 
    }
    }
    // 将枢纽元放在正确的位置(左边都比枢纽元小，右边都比枢纽元大)
    swap(nums[i], nums[right - 1]);
    quicksort(nums, left, i - 1);  // 递归排序左子序列 
    quicksort(nums, i + 1, right);  // 递归排序右子序列 
  } else {  // 小数组采用直接插入排序 
    insertionSort(nums, left, right);  // 直接插入排序 
  }
  }
  // 三数中值分割法选取枢纽元 
  int median(vector<int>& nums, int left, int right) {  
  int mid = (left + right) / 2;  // 中间位置 
  // 将最小数放在最左边，最大数放在最右边 
  if (nums[mid] < nums[left]) {
    swap(nums[mid], nums[left]);
  }
  if (nums[right] < nums[left]) {
    swap(nums[right], nums[left]);
  }
  if (nums[right] < nums[mid]) {
    swap(nums[right], nums[mid]);
  }
  //  因最右边值已经大于中值，将中值与最右边的左边的元素交换
  swap(nums[mid], nums[right - 1]);  // 可减少比较次数，优化 
  return nums[right - 1];  // 返回中值 
  }
  // 直接插入排序 
  void insertionSort(vector<int>& nums, int left, int right) {
     for (int i = left + 1; i <= right; ++i) {  // 遍历无序序列
         int key = nums[i];  // 记录准备插入的元素
         int j = i - 1;  // 记录当前比较位置指针
         while (j >= 0 && nums[j] > key) {  // 寻找插入位置
             nums[j + 1] = nums[j];  // 元素后移 
             --j;  // 指针减1，当前比较位置前移
         }
         nums[j + 1] = key;  // 插入合适位置
     }
  }
};

参考

算法导论

数据结构与算法分析(Java语言描述)

数据结构(C语言版)

————————————————

版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/Acx77/article/details/117376556