快速排序算法实现，欢迎交流，指正错误。
1. 快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
采用了分治的思想：
该方法的基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
1.1. 复杂度分析
- 时间复杂度（平均）：O(nlogn)
- 时间复杂度（最坏）：O(n^2) （退化为冒泡排序）
- 时间复杂度（最好）：O(nlogn)
- 空间复杂度：O(nlogn)
- 稳定性：不稳定
2. 快速排序实现
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
28
29
30
31
32
33
34
|
/**
* 快速排序的实现
*/
public void quickSort(int[] arr) {
if (null == arr || 1 >= arr.length) { return; }
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int start, int end){
if (start >= end) { return; }
// 寻找左右划分的边界
int boundary = findBoundary(arr, start, end);
// 左边使用快排
quickSort(arr, start, boundary - 1);
// 右边使用快排
quickSort(arr, boundary + 1, end);
}
private int findBoundary(int[] arr, int l, int r){
int pivot = arr[start]; // 以第一个元素作为基准
while (l < r){
// 最右边开始找， 找到第一个比pivot小的数
while (l < r && pivot <= arr[r]) { r--; }
arr[l] = arr[r];
// 最左边开始找，找到以一个比pivot大的数
while (l < r && arr[l] <= pivot) { l++; }
arr[r] = arr[l];
}
arr[l] = pivot;
// 返回边界值
return l;
}
|
3. 快速排序的应用
题目：
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
思路：
一般top K问题适合用堆排序解决，但此处要求使用快速排序的思路解决。
我们知道快速排序每经历一次排序后（降序排序），pivot所处的位置是固定的，因为pivot前面的数都不小于它，而pivot后面的数都不大于它，因此经过K次排序后的结果即为第K大。
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
28
29
30
31
|
public int findKth(int[] a, int n, int K) {
// write code here
if(a == null || a.length == 0) return -1;
return quickSort(K, a, 0, n-1);
}
private int quickSort(int K, int[] a, int start, int end){
// 寻找边界
int boundary = findBoundary(a, start, end);
// 边界值 + 1 == K，找到第K大的数
if(boundary + 1 == K)
return a[boundary];
// 边界值 + 1 < K，应在右半部分找第K大的数
else if(boundary + 1 < K)
return quickSort(K, a, boundary + 1, end);
// 边界值 + 1 > K，应在左半部分找第K大的数
else
return quickSort(K, a, start, boundary - 1);
}
private int findBoundary(int[] a, int start, int end){
int pivot = a[start];
while(start < end){
while(start < end && a[end] <= pivot) end--;
a[start] = a[end];
while(start < end && a[start] >= pivot) start++;
a[end] = a[start];
}
a[start] = pivot;
return start;
}
|