算法描述
- 从数列中挑出一个元素,称为"基准"(pivot),
- 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
原理
分而治之思想:
- Divide:找到基准元素pivot,将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1...q],左边的元素都比基准小,右边的元素都比基准大;
- Conquer:对俩个划分的数组进行递归排序;
- Combine:因为基准的作用,使得俩个子数组就地有序,无需合并操作。
稳定性
快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。
性能
快排的平均时间复杂度为O(NlogN),空间复杂度为O(logN),但最坏情况下,时间复杂度为O(N^2),空间复杂度为O(N);且排序是不稳定的,但每次都能确定一个元素所在序列中的最终位置,复杂度与初始序列有关。
优化
当初始序列是非递减序列时,快排性能下降到最坏情况,主要因为基准每次都是从最左边取得,这时每次只能排好一个元素。 所以快排的优化思路如下:
- 优化基准,不每次都从左边取,可以进行三路划分,分别取最左边,中间和最右边的中间值,再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素,再交换到最左边,进行排序。
- 在规模较小情况下,采用直接插入排序
适用场景
快速排序在大多数情况下都是适用的,尤其在数据量大的时候性能优越性更加明显。但是在必要的时候,需要考虑下优化以提高其在最坏情况下的性能。
算法实现
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low >= high)
return;
int pivot = partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //基准
while (low < high){
while (low < high && arr[high] >= pivot) --high;
arr[low]=arr[high]; //交换比基准大的记录到左端
while (low < high && arr[low] <= pivot) ++low;
arr[high] = arr[low]; //交换比基准小的记录到右端
}
//扫描完成,基准到位
arr[low] = pivot;
//返回的是基准的位置
return low;
}
近期评论