参考文献:
快速排序算法
快速排序(图解详细流程)
数组中的第K个最大元素
1. 排序流程
快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
-
首先设定一个分界值,通过该分界值将数组分成左右两部分。
-
将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
-
然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
-
重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
2. 排序步骤
设要排序的数组 A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序(partition)。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是:
1)设置两个变量 i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为关键数据,赋值给 key,即 key=A[0]
;
3)从 j 开始向前搜索,即由后开始向前搜索 (j–),找到第一个小于 key 的值 A[j];
4)从 i 开始向后搜索,即由前开始向后搜索 (i++),找到第一个大于 key 的 A[i],将 A[i] 和 A[j] 的值交换;
5)重复第 3、4 步,直到 ij; (3,4步中,没找到符合条件的值,即 3 中 A[j] 不小于 key, 4 中 A[i] 不大于 key 的时候改变 j、i 的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候 i, j 指针位置不变。另外,ij 这一过程一定正好是 i++ 或 j-- 完成的时候,此时令循环结束)。
3. 排序演示
假设一开始序列 {xi} 是:5,3,7,6,4,1,0,2,9,10,8。
此时,ref=5,i=1,j=11,从后往前找,第一个比 5 小的数是 X8=2,因此序列为:2,3,7,6,4,1,0,5,9,10,8。
此时 i=1,j=8,从前往后找,第一个比 5 大的数是 X3=7,因此序列为:2,3,5,6,4,1,0,7,9,10,8。
此时,i=3,j=8,从第 8 位往前找,第一个比 5 小的数是 X7=0,因此:2,3,0,6,4,1,5,7,9,10,8。
此时,i=3,j=7,从第 3 位往后找,第一个比 5 大的数是 X4=6,因此:2,3,0,5,4,1,6,7,9,10,8。
此时,i=4,j=7,从第 7 位往前找,第一个比 5 小的数是 X6=1,因此:2,3,0,1,4,5,6,7,9,10,8。
此时,i=4,j=6,从第 4 位往后找,直到第 6 位才有比 5 大的数,这时,i=j=6,ref 成为一条分界线,它之前的数都比它小,之后的数都比它大,对于前后两部分数,可以采用同样的方法来排序。
4. 实现
public class Solution {
public static int[] qsort(int arr[], int start, int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (i < j) {
while ((i < j) && (arr[j] > pivot)) {
j--;
}
while ((i < j) && (arr[i] < pivot)) {
i++;
}
if ((arr[i] == arr[j]) && (i < j)) {
i++;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i - 1 > start) arr = qsort(arr, start, i - 1);
if (j + 1 < end) arr = qsort(arr, j + 1, end);
return (arr);
}
public static void main(String[] args) {
int arr[] = new int[]{3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321};
int len = arr.length - 1;
arr = qsort(arr, 0, len);
for (int i : arr) {
System.out.print(i + "\t");
}
}
}
5. Partition 的另一种实现
private int partition(int[] nums, int l, int r) {
int x = nums[l];
int k = l - 1; // k 一直指向 <=x 的最后一个下标
for (int i = l; i <= r; i++) {
if (nums[i] <= x) {
swap(nums, ++k, i);
}
}
swap(nums, k, l);
return k;
}
6. 快速选择
参考 数组中的第K个最大元素
一个无序数组,快速选择第 k 大的数。 时间复杂度为 O(N),证明:我也不会。。
import java.util.Random;
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] nums, int l, int r, int index) {
int q = randomPartition(nums, l, r);
if (q == index) {
return nums[q];
}
return q < index ? quickSelect(nums, q + 1, r, index) : quickSelect(nums, l, q - 1, index);
}
public int randomPartition(int[] nums, int l, int r) {
int i = new Random().nextInt(r - l + 1) + l;
swap(nums, i, l);
return partition(nums, l, r);
}
private int partition(int[] nums, int l, int r) {
int x = nums[l];
int k = l - 1;
for (int i = l; i <= r; i++) {
if (nums[i] <= x) {
swap(nums, ++k, i);
}
}
swap(nums, k, l);
return k;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}