昨天拆掉自行车的两个侧轮之后, 今天女儿就会骑车啦, 昨天陪她骑车的时候我提出来让她试试学会自己骑车, 没想到小家伙心态很开放, 要求拆掉, 然后整个下午摔了几次, 但是可以歪歪扭扭的骑很短一段. 结果今天就学会啦. 这个学习的速度看来比快排还要快一些.
快排和归并排序都采取了分治法策略, 所以时间复杂度都要比之前平方级别的要小一些, 很显然, 如果每次都正好分一半, 就是logN级别的排序, 可谓非常快了.
快排最核心的思路是, 选择数组中一项作为枢轴(pivot), 然后让这一项之前所有的项都小于等于这一项, 让这之后的项都大于等于这一项, 这个动作叫做划分. 很显然, 在递归的思路下对一个数组的排序很简单:
- 对数组进行进行划分
- 对枢轴左右两侧的数组再进行快速排序
基本的划分方法
根据上边的思路, 我们可以先来创建一个最基本的快速排序的方法. 然后来实现一下其中的划分, 看看有什么奥秘.
创建QuickSort类, 来先写好最基本的方法:
public class QuickSort {
private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, boolean reverse) {
if (startIndex < endIndex) {
int pivotIndex = partition(array, startIndex, endIndex, reverse);
sort(array, startIndex, pivotIndex - 1, reverse);
sort(array, pivotIndex + 1, endIndex, reverse);
}
}
private static <T extends Comparable<? super T>> int partition(T[] array, int startIndex, int endIndex, boolean reverse) {
return 0;
}
/**
* 交换数组中两个指定索引的元素的位置的方法
*
* @param array 目的数组
* @param firstIndex 第一个索引
* @param secondIndex 第二个索引
* @param <T> 泛型参数, 实现Comparable接口
*/
private static <T extends Comparable<? super T>> void swap(T[] array, int firstIndex, int secondIndex) {
T temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
}
然后就是核心的划分方法了. 划分方法如果我自己写的话, 很可能会选择数组的中间索引, 然后不断的往两边去循环, 这样其实不是好的算法. 这里也就不用自己想了, 前人都已经想好了, 套路如下:
- 找到数组中一个大小的元素作为枢轴
- 将这个元素与数组最后一个元素交换位置
- 使用两个索引A和B, A是数组的起始, B是数组的倒数第二个位置, 然后A向数组末尾移动, B向数组头部移动. 各自停在大于等于和小于等于枢轴元素的位置, 如果此时A小于B, 就交换二者, 然后继续移动, 直到A>=B结束.
- 将枢轴与A位置的元素交换
这里我先来编写最基本的划分方法如下:
/**
* 用于辅助快速排序的最基本的划分方法
*
* @param array 要划分的数组
* @param startIndex 数组的起始索引
* @param endIndex 数组的结束索引
* @param reverse 是降序还是升序
* @param <T> 泛型参数, 实现Comparable接口
* @return 返回枢轴对应的索引
*/
private static <T extends Comparable<? super T>> int partition(T[] array, int startIndex, int endIndex, boolean reverse) {
//目前是最基本的划分方法, 强行规定中枢是 (startIndex+endIndex)/2
//既然这样, 对于长度是1和2的数组, 可以直接返回结果
//长度是1的数组就是枢轴, 直接返回对应索引
if (startIndex == endIndex) {
return startIndex;
//长度是2的数组, 根据reverse判断大小, 然后直接交换位置, 枢轴直接返回startIndex即可, 因为相邻的(startIndex+endIndex)/2 = startIndex
} else if (endIndex - startIndex == 1) {
//升序的情况下, 比较第一个数是不是比第二个大 ,如果大就交换位置, 否则不交换
if (!reverse) {
if (array[startIndex].compareTo(array[endIndex]) > 0) {
swap(array, startIndex, endIndex);
}
//降序情况下, 比较第一个数是不是比第二个小, 如果小就交换位置
} else {
if (array[startIndex].compareTo(array[endIndex]) < 0) {
swap(array, startIndex, endIndex);
}
}
return (startIndex + endIndex) / 2;
//长度为3及以上的数组
} else {
//先强行选择枢轴索引和对应的元素
int pivot = (startIndex + endIndex) / 2;
T pivotElement = array[pivot];
//将枢轴元素与最后一个元素交换位置
swap(array, pivot, endIndex);
//然后开始各从两端向另外一端扫描
//获取原来的起始索引和右边倒数第二个索引, 下边判断控制条件会用到
int fromRightIndex = endIndex - 1;
int initialIndex = startIndex;
//startIndex>=fromRightIndex就可以终止循环了
while (startIndex < fromRightIndex) {
if (!reverse) {
//从数组开头向数组末尾扫描, 扫描大于pivot的元素, 这个循环停下的位置是大于pivotElement的位置. 如果都没有, 最大也就是endIndex的地方
while (array[startIndex].compareTo(pivotElement) <= 0 && startIndex < endIndex) {
startIndex++;
}
//从数组的倒数第二个元素开始向数组头扫描, 扫描小于pivot的元素, 这个循环停下的位置是小于pivotElement的位置, 最小也就是原来startIndex的地方
while (array[fromRightIndex].compareTo(pivotElement) >= 0 && fromRightIndex > initialIndex) {
fromRightIndex--;
}
} else {
while (array[startIndex].compareTo(pivotElement) >= 0 && startIndex < endIndex) {
startIndex++;
}
//从数组的倒数第二个元素开始向数组头扫描, 扫描小于pivot的元素, 这个循环停下的位置是小于pivotElement的位置, 最小也就是原来startIndex的地方
while (array[fromRightIndex].compareTo(pivotElement) <= 0 && fromRightIndex > initialIndex) {
fromRightIndex--;
}
}
//如果startIndex小于fromRightIndex, 说明需要交换, 否则无需交换
if (startIndex < fromRightIndex) {
swap(array, startIndex, fromRightIndex);
}
}
//循环执行完毕之后, 要么两个索引相等A=B, 要么A和B互换位置导致A>B, 此时A的位置, 必定是大于等于枢轴的位置, 因此交换A与末尾元素(就是枢轴)
swap(array, startIndex, endIndex);
//返回此时的实际枢轴所在位置的索引, 也就是startIndex的索引
return startIndex;
}
}
这个方法基本上就是把算法写成代码, 这里要注意的就是, 一开始按照索引选择枢轴, 但是最后的枢轴并不一定位于原来的位置上, 而是根据这个数组中元素大于和小于枢轴元素的个数来决定.
在编写了这个方法之后, 其实我们的快速排序的核心私有方法就可以正常工作了. 不过在测试中, 可以看到最后返回的枢轴索引并不一定将数组基本上分为两个相等的部分. 由于枢轴的选择对于排序至关重要, 所以来看看改进的方法.
优化划分
优化划分的一大要素是, 尽量让划分之后的枢轴所处的位置在数组的中间, 即返回的枢轴索引可以将数组分成差不多相等长度的两部分.
为了达到这个目的, 显然最好的方法就是给数组排序, 然后获取中间索引, 但是因为排序本来就是我们的目的, 因此这个方法不可取.
比较好的方法是, 取数组的第一个元素, 中间项和最后一项三个数字, 将这三个数值进行排序, 然后取中间项作为枢轴. 这需要编写一个辅助方法就可以了.
private static <T extends Comparable<? super T>> void sortFirstMiddleLast(T[] array, int firstIndex, int middleIndex, int lastIndex, boolean reverse) {
T a = array[firstIndex];
T b = array[middleIndex];
T c = array[lastIndex];
//默认是升序的情况
//a>=b的情况
if (a.compareTo(b) >= 0) {
//如果b>=c, 按照 c b a 排列
if (b.compareTo(c) >= 0) {
array[firstIndex] = c;
array[middleIndex] = b;
array[lastIndex] = a;
//如果a>=c>b, 按照a c b排列
} else if (a.compareTo(c) >= 0) {
array[firstIndex] = b;
array[middleIndex] = c;
array[lastIndex] = a;
//如果c>a>=b, 按照b a c 排列
} else {
array[firstIndex] = b;
array[middleIndex] = a;
array[lastIndex] = c;
}
//a<b的情况
} else {
//b>a>c
if (a.compareTo(c) >= 0) {
array[firstIndex] = c;
array[middleIndex] = a;
array[lastIndex] = b;
//b>c>a
} else if (b.compareTo(c) >= 0) {
array[firstIndex] = a;
array[middleIndex] = c;
array[middleIndex] = b;
//c>b>a
} else {
array[firstIndex] = a;
array[middleIndex] = b;
array[lastIndex] = c;
}
}
//如果降序, 交换一下最大和最小值即可.
if (reverse) {
swap(array, firstIndex, lastIndex);
}
}
这个方法就是先按照降序排列, 如果发现是升序, 再交换一下两头元素的位置即可.
然后在划分方法获取枢轴元素的位置使用这个方法先排序, 再获取枢轴元素:
private static <T extends Comparable<? super T>> int partition(T[] array, int startIndex, int endIndex, boolean reverse) {
if (startIndex == endIndex) {
return startIndex;
} else if (endIndex - startIndex == 1) {
if (!reverse) {
if (array[startIndex].compareTo(array[endIndex]) > 0) {
swap(array, startIndex, endIndex);
}
} else {
if (array[startIndex].compareTo(array[endIndex]) < 0) {
swap(array, startIndex, endIndex);
}
}
return (startIndex + endIndex) / 2;
} else {
int pivot = (startIndex + endIndex) / 2;
//这里新增确定三元枢轴排序的方法
sortFirstMiddleLast(array, startIndex, pivot, endIndex, reverse);
T pivotElement = array[pivot];
swap(array, pivot, endIndex);
int fromRightIndex = endIndex - 1;
int initialIndex = startIndex;
while (startIndex < fromRightIndex) {
if (!reverse) {
while (array[startIndex].compareTo(pivotElement) <= 0 && startIndex < endIndex) {
startIndex++;
}
while (array[fromRightIndex].compareTo(pivotElement) >= 0 && fromRightIndex > initialIndex) {
fromRightIndex--;
}
} else {
while (array[startIndex].compareTo(pivotElement) >= 0 && startIndex < endIndex) {
startIndex++;
}
while (array[fromRightIndex].compareTo(pivotElement) <= 0 && fromRightIndex > initialIndex) {
fromRightIndex--;
}
}
if (startIndex < fromRightIndex) {
swap(array, startIndex, fromRightIndex);
}
}
swap(array, startIndex, endIndex);
return startIndex;
}
}
注意上边红色的部分, 在获取枢轴元素之前, 先按照三元枢轴排一下序, 之后再获取枢轴元素, 这个元素就比刚才直接获取要稍微好一点了.
继续改进
还有继续改进的空间吗? 有的. 对于小数组, 其实划分枢轴和排序也最后会递归得到2项或者3项的小数组. 这会导致大量的判断浪费.
实际上, 对上10项以下的数组, 可以直接将其排序好就行了, 对于小数组, 使用插入排序的效率是可以接受的. 所以最后的改进就是对于数组长度的判断:
private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, boolean reverse) {
if (endIndex - startIndex + 1 < 10) {
if (!reverse) {
InsertionSort.sortBetweenIndex(array, startIndex, endIndex);
} else {
InsertionSort.sortBetweenIndexDesc(array, startIndex, endIndex);
}
} else {
int pivotIndex = partition(array, startIndex, endIndex, reverse);
sort(array, startIndex, pivotIndex - 1, reverse);
sort(array, pivotIndex + 1, endIndex, reverse);
}
}
如果数组长度小于10, 直接插入排序, 大于10的数组, 才选择枢轴然后进行划分. 这样快排基本上就做好了.
可以看到一个快排, 几乎用上了各种套路, 对于低级数组还使用插入排序帮忙. 相比归并排序, 快排不使用额外的空间, 经过一些手段处理枢轴之后, 整体的效率比较好, 不愧是所有排序中, 很多都是以方法命名, 就这种排序不叫什么划分排序, 直接叫快速排序, 真的是快速啊.
