快速排序原理理方法详解

来源：蜘蛛抓取(WebSpider) 时间：2019-01-25 04:03 标签： 快速排序原理

Arrays.sort()方法可以通过源码发现内部使用嘚是快速排序然后我们探索一下快速排序的原理

快速排序是交换排序的一种，交换排序的含义是根据序列中的两个元素关键字的比较结果来交换两个记录在序列中的位置同时，冒泡排序（时间复杂度为O(n2)）作为交换排序中的经典快速排序也是对冒泡排序的一种改进。
快速排序是所有内部排序算法性能最优的排序算法但是它是一个不稳定的排序算法。

  1. 通过一趟排序将待排序的记录分割成独立的两部分其中一部分比基准元素大，另一部分比基准元素小
  2. 基准元素在其排好序的位置上
  3. 分别对划分好的两部分继续进行快速排序直到整个序列囿序

平均时间为Tavg(n) = kn ln n，其中n为待排序序列中记录的个数k为某个常数，在所有同类数量级的此类排序方法中快速排序的常数因子k最小。
空间複杂度最坏的情况下O(n)，就是每个数字都作为一次基准平均情况是O(nlog2n)
时间复杂度，在很大程度上取决于划分算法与序列本身的情况平均嘚时间复杂度为O(nlog2n)。
在未改进的情况下若初始记录序列按照关键字有序或基本有序时，快速排序会退化为冒泡排序时间复杂度为O(n2)。

通常使用“三者取中”的法则来选取枢轴记录即比较a[start]、a[end]、a[(start+end)/2]，取三者取中值记录为枢轴采用这种方法能够大大改善快去排序在最坏情况下的性能。

为什么要学习快速排序：我们知噵希尔排序相当于直接插入排序的升级版，他们同属于插入排序类堆排序是简单选择排序的升级，同属于选择排序快速排序则是最慢排序冒泡排序的升级，同属于交换排序类就是通过不短的比较和移动交换来实现排序的，只不过他的实现增大了记录比较和移动的距離将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面从而减少了总的比较次数和移动交换次数。對于一个包含n个数的数组来说快速排序是一个时间复杂度为O(n^2)的排序算法，但是他的数学期望为O(nlogn),而且他的隐含的常数因子非常小而且他昰原址排序的（就是自己在自己数组里折腾，而像归并排序就不是原址排序因为他是在引入的一个新数组里进行的排序，再复制给原来嘚数组的）在虚存环境（虚拟内存的概念是相对于物理内存而言的，当系统的物理内存空间入不敷出时操作系统便会在硬盘上开辟一塊磁盘空间当做内存使用，这部分硬盘空间就叫虚拟内存）中也能很好的工作

快排的基本思想：就是通过一趟排序将待排记录分割成独竝的两部分，其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录分别进行排序，从而可以达到整个序列有序的目的（其实就是任意选择一个关键字，把比它小的都放在左边比它大的都放在后面）  

他的精髓就在于Partition函数，我们把它叫做Partition过程（非常經典的就是荷兰国旗问题就是选一个标记值（也叫划分值），把比他小的放在左边比他大的放在右边，和他一样大的放在中间选好尛于区（起始区域不包含数据），大于区（要注意的是大于区的区域先包含这个标记值）遍历数组，要是当前数小于标记数当前位置囷小于区后一个数交换位置，且小于区右移一位当前数跳下一个要是当前数等于标记数，当前数直接跳下一个要是当前数比标记数大，那么大于区的前一个数和当前数进行交换且当前数不动大于区往前括一个位置等到当前数到大于区时，把当前数也就是大于区的第一個数与标记数也就是最后一个数进行交换（要是大于区不扩标记值需要拿一个变量来记录一下标记值的值，因为那个值位置不固定会亂跑，下面来看实现这段过程的代码：

下面来看真正的快速排序的代码：


①和归并排序一样首先要考虑的问题时传进来的数组是否需要進行快速排序，也就是该数组是非空且长度大于1的数组才有意义
//判断是否有排序的必要
//调用真正有意义的归并排序方法
②当数组长度大于1時我们调用真正的快速排序，从上面我们介绍什么是归并的时候介绍的非常清晰就是利用递归来完成对子区间的划分，向我们上面举嘚递归的demo一样构造递归，对左右两部分进行排序然后合并，代码如下：
//base case这是在构建递归时第一步要考虑的
//就是递归终止的条件
` //因为递歸终止的条件没有开始的条件少所以取反过程仍然需要考虑
//首先应该从该数组中随机选取一个数，然后把它当做标记值也就是分割值讓它与数组的最后一个数据进行交换
③就是我们非常重要的partition过程了，代码详见荷兰国旗问题对应的partition过程  
 

 
为什么工程上经常用随机快速排序洏不用经典快速排序因为经典快速排序遇到不平均的可能性很高，因为快速排序的最差时间复杂度为O（n^2）就会导致快速排序并不“快速了”，而真正在工程上落地的是随机快速排序因为随机就变成了一个数学问题，他的数学期望值为O(nlogn)又因为他的常系数很小，所以速喥贼快
 
 

 空间复杂度：快速排序所占用的时间复杂度，其实就是递归造成的栈的使用最好情况，也就是每次左右都差不多这样其空间複杂度为O（log2 n）,最坏的情况就是需要进行n-1次递归调用，这样他的空间复杂度就是O(n)其平均空间复杂度为O（logn）

（1）子数组的头指针和尾指针：茬一个数组中假设有一个子数组。这个子数组的第一个值在原数组的下标我们定义为子数组的头指针。而子数组的最后一个值在原数組的下标我们定义为子数组的尾指针。

在其中随便取出一个子序列

则子数组{7 4 3}的头指针为2（数组首地址为0）尾指针为4。
（2）参考值和参栲指针：对于任意一个子数组首先选定子数组的第一个元素为参考值，参考值在原数组中的位置被称为初始参考指针

初始参考值是子數组的第一个元素7，参考指针为2此时的参考指针和子序列的头指针是一样的（但注意，我们是要排序的排序后就不一定一样了）。

快速排序本质是对参考值与数组的其他值进行一系列交换操作使得交换后子序列满足如下条件

（1）位于参考值前的数据都小于参考值（2）位于参考值后的数据都大于参考值（3）对参考值前的所有数据（即小于参考值的数据）没有顺序要求（4）对参考值后的所有数据（即大于參考值的数据）没有顺序要求 先不要管一系列交换操作都干了什么，先来理解一下快速排序的大局思路

（1）先对整个数组做上述交换操莋（2）取参考值前的所有数据作为一个子数组，我们给他起个名字叫左数组（3）取参考值后的所有数据作为一个子数组我们给他起个名芓叫右数组（4）分别对左数组和右数组重复上述交换操作 那么什么时候停止计算呢？


答曰：当子数组为空或者只有一个元素时停上述操莋
于是按照上述步骤就实现了排序。以数组{4 3 7 2 5 1 6}为例排序过程如下图所示。注意：我们在操作子数组的时候都直接在原数组中操作这样操莋结束后原数组就是有序的了。
接下来看看如何实现上述的一系列交换操作的
这里就需要用到头指针和尾指针和参考指针了

首先进行尾指针和参考指针的相关操作
（1）判断尾指针里的数据是否小于参考值。
（2）如果小于交换参考值和尾指针里的数值（尾指针不变），参栲指针移动到尾指针处结束尾指针的操作。
（3）如果大于或者等于尾指针向前移动一位。
（4）判断尾指针是否和头指针重合不重合時重复上述操作，否则结束尾指针的操作

之后进行头指针和参考指针的相关操作 因为有尾指针的操作，这时参考指针已经和头指针脱离開了


（1）判断头指针里的数据是否大于参考值。
（2）如果大于交换参考值和头指针里的数值（头指针不变），参考指针移动到头指针處结束头指针的操作。
（3）如果小于或者等于头指针向前移动一位。
（4）判断尾指针是否和头指针重合不重合时重复上述操作，否則结束尾指针的操作
进入头指针操作时尾指针和参考指针是重合的，但经过头指针操作二者又脱离开了

最后判断头指针和尾指针是否偅合 如果没重合，重新进行尾指针操作和头指针操作一直到头尾指针重合。

这样操作可以保证头指针左侧的数都一定小于参考数，尾指针右侧的数都一定大于参考数！！！
因为：尾指针中的数大于参考数时才会向左移动等于或者小于的时候则不会动；头指针中的数小於参考数时才会向右移动，等于或者大于的时候则不会动

从小到大排序的代码如下：

我要回帖

更多关于 快速排序原理 的文章

 

随机推荐