快排的基本思路是每次选出一个基准元素，将小于该元素的移动到一边，大于该元素的移到另一边，最后将基准元素移动到它应该在的位置，找到这个位置后，对左右两边的元素递归快排，直到不再满足left < right的条件。
按照上面的逻辑，快排具有一个好用的性质，即每轮能最终确定一个基准元素的位置，基于这个性质，能实现在无序数组中以O(n)时间复杂度找到第k大元素的算法。
快排类似于二叉树的前序遍历，排序方法其实就是一个递归函数的结构，终止条件——>处理当前节点——>处理左右子区间。
一个完整的快排实现包含两个方法，一个递归调用的quickSort方法，一个用于处理每个节点的partition方法。
partition方法的具体逻辑是选择一个元素，用快慢双指针的方式将大于和小于该元素的值分别划分到一边——快指针遍历，慢指针记录当前区间的末位置，遍历完成后，将基准元素交换到慢指针标记的位置，并且返回该位置，后续以该位置划分左右子区间。
快排实现：
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
| public class QuickSort {
private void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
System.out.println(Arrays.toString(arr));
return i + 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
在无序数组中以O(n)时间复杂度找到第k大元素算法实现：
与快排最大的不同是，每一轮不再需要搜寻左右两个区间，而只需要根据基准下标与k的关系，搜索k所在的那一个子区间，搜到了就直接返回，不需要再往下递归，时间复杂度为：n/2 + n/4 + n/8 + ··· + 1，等比数列求和为 2n + 1。
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
35
36
37
38
| public class KthLargest {
private int findKthLargest(int[] arr, int k) {
if (arr == null || arr.length < k) {
return -1;
}
int pivotIndex = partition(arr, 0, arr.length - 1);
while (pivotIndex + 1 != k) {
if (pivotIndex + 1 < k) {
pivotIndex = partition(arr, pivotIndex + 1, arr.length - 1);
} else {
pivotIndex = partition(arr, 0, pivotIndex - 1);
}
}
return arr[pivotIndex];
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] > pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
