快速排序算法算是所有排序算法中知名度最高的了，应用也超级广泛，正是由于其良好的性能才独得恩宠。今天就来好好的认识一下快速排序。
一、原理
快速排序一般都是使用递归来实现的，采用的是“分而治之”的思想。
一组待排数据，选择一个基准元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,然后对这两部分重复同样的操作。
上面的过程你会发现，这一趟扫描可以增大元素之间的移动距离，因为关键字较大的元素可能直接从最前面直接移动到后面。我们看一张维基百科的动图：
1-动图.gif
红色部分的是基准元素，就这样不管相隔多远，比基准元素大的都会到前面，比基准元素小的都会到后面。不过这张图只是帮助我们从宏观上去了解去分析。大学的时候我们都学过数据结构的话，我们来看这个经典的例子：
2-快拍.png
也就是说，我们分而治之的时候，采用了这种裂变的方式，最终体现在就是速度的提高。下面我们就使用代码来实现一下：
二、代码实现
1、基本实现
我们首先看一下最基本的快速排序实现：
public static void sort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}//每一趟结束的条件
i = low;
j = hight;
index = a[i]; // 第一个记录做基准元素
while (i < j) {
//先从右边进行扫描，找到大于基准值的元素
while (i < j && a[j] >= index)
j--;
//找到之后交换
if (i < j)
a[i++] = a[j];
//然后从左边扫描，找到小于基准值的元素
while (i < j && a[i] < index)
i++;
//找到之后交换
if (i < j)
a[j--] = a[i];
}
a[i] = index;
sort(a, low, i - 1); // 对低子表进行递归排序
sort(a, i + 1, hight); // 对高子表进行递归排序
}
上面就是最基本的使用方法，不过你会发现这种方式是不稳定的，为什么不稳定，因为交换的元素距离可能很大。如果元素的交换是相邻的，那就是稳定的，如果元素的交换不相邻，隔了元素或者是隔了很多元素，那就是不稳定的。
这种最基本的快速排序，不管是从空间上还是从时间上都是很好的，不过如果我们仔细考虑的话，里面依然有很多缺点。比如说我们的基准值如果进一步优化，那么将会减少比较次数，在比如说如果每次在移动元素的时候，不再移动，而是采用赋值的操作，会进一步缩短时间。有了这些想法，我们就开始进行优化。
2、优化实现
改进思路：
（1）分而治之时候，分到了最后，数组已经很小，这时候采用插入排序代替快速排序。
（2）基准值的选取，我们随机取出来3个数，取中间大小的为基准值。
（3）取三个变量切分数组，将数组分为大于，等于，小于基准元素三部分，这样在递归时就可以剔除相等的元素，减小比较的次数
有了这些改进想法，我们就看一下如何实现：
private static void sort(Comparable[] a,int low,int height){
//改进处1：由插入排序替换
if(height <= low + M){//M取5-15
InsertSort.sort(a,lo,hi);
return;
}
//改进处3：三向切分
int lt=low,i=low+1,gt=height; //三个变量，
//改进处2：基准元素的选取
int i=medianOf3(a,low,low+(height-low)/2, height);
while(i<=gt){
int cmp = a[i].compareTo(a[low]);
if(cmp<0)
exch(a,lt++,i++);
else if(cmp>0)
exch(a,i,gt--);
else
i++;
}
sort(a,low,lt-1);
sort(a,lt+1,height);
}
这就是快速排序的改进，是不是很简单，这里面有俩函数没有讲，medianOf3和exch。medianOf3函数是找到三个数的中间值，exch是交换两个数的位置，很简单，这里就不说了。
三、分析
在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
在最坏的情况下，最终其时间复杂度为O(n2)。
快速排序的平均时间复杂度为O（nlog（n））。
快速排序的使用场景那就是太多了，快排被称为是最好而且使用最广泛的一种排序机制算法。
默认标题_方形二维码_2019.08.16.png
网友评论