快速排序(Quick Sort)

简介: 算法介绍算法描述动图演示算法分析算法优化代码实现参考

算法介绍


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


算法描述


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


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


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


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


如下图所示:



动图演示


2021052900212984.gif


算法分析


 时间复杂度:平均O(NlogN), 最坏O(N2)


 空间复杂度: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

相关文章
|
28天前
3秒的你对战“它”有没有胜算——quicksort
3秒的你对战“它”有没有胜算——quicksort
26 0
|
1月前
|
算法 前端开发
前端算法之快速排序
前端算法之快速排序
19 0
|
6天前
|
算法
数据结构与算法-快速排序
数据结构与算法-快速排序
5 1
|
7天前
|
算法 搜索推荐 数据可视化
【漫画算法】指挥官的排序战术:快速排序算法解密
【漫画算法】指挥官的排序战术:快速排序算法解密
|
11天前
|
算法 搜索推荐
数据结构和算法——快速排序(算法概述、选主元、子集划分、小规模数据的处理、算法实现)
数据结构和算法——快速排序(算法概述、选主元、子集划分、小规模数据的处理、算法实现)
8 0
|
17天前
|
存储 搜索推荐 算法
快速排序算法详解
快速排序算法详解
|
24天前
|
算法 C++
c++算法学习笔记 (1)快速排序
c++算法学习笔记 (1)快速排序
|
27天前
|
算法 搜索推荐
【算法基础】基础算法(一)--(快速排序、归并排序、二分)
【算法基础】基础算法(一)--(快速排序、归并排序、二分)
|
30天前
|
搜索推荐 算法
Quick Sort
Quick Sort “【5月更文挑战第18天】”
30 7
|
1月前
|
搜索推荐 算法 Java
快速排序------一种优雅的排序算法
快速排序------一种优雅的排序算法