快速排序算法分析与实现
介绍
快速排序算法是一种基于分治思想的排序算法，分治思想有以下特点：
- 将一个问题可划分为同一类型的若干个子问题，子问题的规模相同或者相近
- 求解这些子问题，然后合并这些子问题的解，可得到原问题的答案
快速排序的主要思想按照元素的值进行划分。对于一个数组A，经过一次快速排序后，使得A[i]左边的元素全都小于等于A[i]，A[i]右边的元素全部大于等于A[i]，然后利用相同的排序方式处理两个子数组（即A[i]左右两边的元素组成的数组），直到子数组的元素个数为1，此时原数组成为有序数组。
算法伪代码如下：
1
2
3
4
5
6
7
8
9
| QuickSort(A[low...high]):
if low < high:
s = partition(A[low...high])
QuickSort(A[low...s-1])
QuickSort(A[s+1...high])
|
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public void sort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
private void quickSort(int[] nums, int low. int high) {
if (low < high) {
int segment = partition(nums, low, high);
quickSort(nums, low, segment - 1);
quickSort(nums, segment + 1, high);
}
}
private int partition(int nums, int low, int high) {
int pivot = nums[low];
while(low < high) {
while(low < high && pivot <= nums[high]) {
high--;
}
nums[low] = nums[high];
while(low < high && pivot >= nums[low]) {
low++;
}
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
|
时间复杂度
最优情况：分割点全都位于数组的中间位置，此时比较次数为:
Cbest(n) = 2Cbest(n/2) + n, Cbest(1) = 0
最坏情况：所有的分割点都在数组的端点位置，此时的比较次数为：
Cworst(n) = (n + 1) + n + (n - 1) + … + 3, O(n2)
平均情况：
Cavg(n) = 2nln(n) ≈ 1.39nlog(2n)
根据时间复杂度可以看出，该算法在平均情况下仅比最优情况下多执行39%的操作，其内循环的效率较高使得该算法在处理随机排列的数组时会比合并排序快。
优化点
- 更好的中轴选择方法：三平均划分法（以数据最左边，最右边和最中间元素的中位数作为分割点）
- 当子数组很小时，改用插入排序或不再进行排序，在算法结束后利用插入排序处理剩下未进行排序的元素，即利用两个算法进行排序。