排序算法也是算法的一个重头戏，里面涉及的算法按时间复杂度可以分为两大类：
时间复杂度为O(n^2): 冒泡排序、选择排序、插入排序
时间复杂度为O(nlogn): 快速排序、归并排序
本文将重点介绍快速排序及其实现。
时间复杂度：
快速排序是目前已有的排序算法中最快的算法，它的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。
核心思路：分治思想
将原问题划分成若干子问题解决：数组A中选一个基准点pivot，数组中其他的元素与pivot逐个比较，每遇到一个大于pivot的元素和一个小于pivot的元素，两者交换位置，大的右移，小的左移，直至所有元素不再进行上述步骤。
pivot的选择：
常见的有以下三种方案：
首/尾法：如果数组是排好序的，那么选首/尾元素为pivot，可能会把所有元素移到另外一边，带来最坏时间复杂度为O(n^2)。
随机选择法：最坏时间复杂度为O(n^2)产生的概率小于头/尾法。
三数中值法：求数组的第一个元素、中间位置元素、最后一个元素的中值，将中值与最后一个元素交换即可，这样做的好处是降低了最坏时间复杂度产生的概率。
下面我们一起来看一下具体的实现：
part 1
思路分析：
pivot.png
代码：
// 三数中值法是为了防止最坏情况的出现，找到三数中值，并与right-1 交换，能减少一次交换次数，因为right 确定＞ 中值；
public int midValue(int a[], int left, int right){
// 先确定数组里的数>=3个,这样才能选三个数里的中值：
if(right-left+1>=3){
int center =(left+right)/2;
if(a[left]> a[center]){
swap(a,left,center);
}
if(a[center]> a[right]){
swap(a,center,right);
}
// 这一步是防止原先的顺序为：321，相当于比较了原来的left、right；
if(a[left]>a[center]){
swap(a,left,center);
}
swap(a,center,right-1);
return a[right-1];
}else{
if(a[left]>a[right]){
swap(a,left,right);
}
return 0;
}
}
part 2
思路分析：
QuickSort.png
代码：
public int[] quickSortNew(int[] a, int left ,int right){
int pivot = midValue(a,left,right);
// 首先分析数组的数目大于3时
if(right-left+1>3){
int i= left;
int j= right -1;
while (i<j){
// 如果满足括号里的条件，会一直继续下去 ，目的：a[i]>pivot 时才停下，所以条件取反时一直往右移：
while (i<j && a[i]<= pivot){i+=1;}
// 同上，找到a[j]<pivot
while (i<j && a[j]>= pivot){j-=1;}
// 以上循环停下的时候 ，如果正好i<j,交换a[i] a[j]的位置
if(i<j){
swap(a, i, j);
}else {
break;
}
}
swap(a,i,right-1);
quickSortNew(a,left,i-1);
quickSortNew(a, i+1, right);
}
return a;
}
小结：
排序算法的很多都用了分治思想，把一个大问题划分成若干子问题来解决，在我们自己学习的时候，也可以把思考的过程划分成若干子过程来仔细研究，就像我刚刚只是思路分析了例子中排序的第一步，如果你感兴趣，且想把快速排序这个问题啃下，建议小伙伴们可以自己分析演练出后序过程，这样可以更好地帮助你理解这个问题。
网友评论