- 时间复杂度：高效的排序算法，比较次数和移动次数都应该尽可能的少。
- 空间复杂度：算法执行期所需要辅助空间和待排序的数据量无关。理想空间复杂度为O(1)
简述
快速排序可以说算是针对冒泡排序的一种优化，冒泡排序是顺序交换，这样交换次数顺序增长。如果我们做跳跃的交换，那么可以使得交换次数也是跳跃性，会有所降低
算法思想
- 找出一个枢轴，用于做比较交换，并记下后用。一般用第一个(用第一、中间、最后三个取中后来效果会更好)，定一个高位:high和底位:low
- 从表的高位开始，往左进行比较，找到一个关键字小于枢轴，则将high和枢轴交换。否则high--
- 从表的低位开始，往右进行比较，找到一个关键字大于等于枢轴，则将low和枢轴交换。否则low++
- 重复2和3步，直到low==high位置，此时low和high的位置则是枢轴在本趟排序在表的最终位置，成功将表分成比枢轴小和比枢轴大两个字表在枢轴左右两侧。
以上2和3步骤，每次交换，要做三次记录：
一次移动low到high，一次移动high到low，加中间借助了temp这一类的。
我们可以减少移动记录：
比如一开始记录下枢轴值，在每次移动的时候，只移动要与枢轴交换的记录，移动完成后，最后将开始记录下的枢轴关键字放入最终的枢轴位置。
算法实现
private static class QuickSortClass {
/**
* 进行快速排序
*/
public void quickSort() {
List<Integer> integers = new ArrayList<>();
int[] intArray = new int[]{1, 44, 3, 33, 77, 25, 98, 221, 33, 16};
for (int value : intArray) {
integers.add(value);
}
eSort(integers, 0, intArray.length - 1);
System.out.print(integers);
}
/**
* 计算枢轴位置，通过进行一轮交换得到新的枢轴位置
*
* @param ints
* @return 返回交换后的枢轴的位置
*/
private int evaluatePrivotPartition(List<Integer> ints, int l, int h) {
/*第一步：先选取枢轴记录，使用三者取中原则，我们用第一个、中间一个、最后一个来比较大小，
取中间大小中间一个为枢轴记录并与第一个交换*/
int low = l;
int high = h;
int oneValue = ints.get(low);
System.out.println("oneValue=" + oneValue);
int centerPart = (high + low) / 2;
int centerValue = ints.get(centerPart);
System.out.println("centerValue=" + centerValue);
int lastValue = ints.get(high);
System.out.println("lastValue=" + lastValue);
int privotDef = oneValue;
//取出中间一个，做中枢记录,如果不用此步骤，那么默认选第一个
if (oneValue > Math.min(centerValue, lastValue) && oneValue < Math.max(centerValue, lastValue)) {
privotDef = oneValue;
} else if (centerValue > Math.min(oneValue, lastValue) && oneValue < Math.max(oneValue, lastValue)) {
privotDef = centerValue;
//交换中枢位置
ints.set(low, centerValue);
ints.set(centerPart, oneValue);
} else {
privotDef = lastValue;
ints.set(low, lastValue);
ints.set(high, oneValue);
}
System.out.println("枢轴记录:privotDef=" + privotDef);
/*重复第二三步，直到low==high为止*/
while (low < high) {
/*每一轮的交换执行*/
//第二步：从high往左,如果high位置的值大于等于枢轴记录，那么high--
while (low < high
&& ints.get(high) >= privotDef) {
high--;
}
//小于枢轴值时候，需要和做交换，将high移到low
if (low < high) {
ints.set(low, ints.get(high));
}
//第三步：从low往右,如果low位置的值小于等于枢轴记录，那么low++
while (low < high
&& ints.get(low) <= privotDef) {
low++;
}
//找到比枢轴记录大的值，那么low换到high
if (low < high) {
ints.set(high, ints.get(low));
}
}
//将记录下来的枢轴放入low位置，枢轴记录到位
ints.set(low, privotDef);
for (Integer value : ints) {
System.out.print(value + " ");
}
System.out.print("\n");
return low;
}
/**
* 执行快速排序入口
*
* @param ints
* @param low
* @param high
*/
private void eSort(List<Integer> ints, int low, int high) {
//只要low和high不相等,就代表交换后子表长度依旧大于1
if (low < high) {
int privotP = evaluatePrivotPartition(ints, low, high);
eSort(ints, low, privotP - 1);//对左字表进行递归排序
eSort(ints, privotP + 1, high);//对右字表进行递归排序
}
}
}
- 客户端调用
public static void main(String[] args) {
System.out.println("Hello World!");
new QuickSortClass().quickSort();
}
可以看到，在evaluatePrivotPartition中有一个,取中间值的步骤，不加那一步也是可以，跑一下你就会发现，本次排序用了6趟。如果不加那一步，则默认使用第一个为枢轴记录，最后排序下来的趟数会是7趟。
不要小看只多了一趟，如果数更大，优势会更明显。
算法分析
- 时间复杂度
可以看下排序的递归树：
image
大致也能看出，排序的躺数取决于递归树的深度.
- 最好的情况：每一趟都能将记录均匀分割成两个长度大致相等的子表，类似折半查找。n个序列，枢轴定位时间O(n)，若T(n)是对n个元素进行排序所需对时间，且每次定位，正好把序列划分为长度相等的两个子表，设Cn是一个常数，表示n个元素进行一趟快速排序的时间，则总时间：
T(n)=Cn+2T(n/2)
T(n) <=n+2T(n/2)
继续往下得到T(n)约等于O(nlog2n)
- 最坏的情况：带排序序列已经排好的情况下，其递归数为单只树，每次划分得到一个比上一个少的序列，这样必须经过n-1趟才能将所有记录定位，而且第i趟需要经过n-i次比较，比较次数就为n2/2
为了避免最坏情况，所以我们可以使用三者取中原则进行选取枢轴记录，就是前面代码用到的方式
- 空间复杂度
排序是递归的，所以需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致。为O(log2n)，最坏情况下为O(n)
算法特点
- 不稳定：记录非顺序次地移动导致
- 难用于链式结构：需要定位表的下界和上界，适合顺序结构
- 平均来说，快排可以说是内部排序中最快的一种了，在初始无序，n比较大的情况，使用快排是比较合适的。
