快速排序计算第K大的数

约定不等于承诺〃 2023-07-18 05:55 19阅读 0赞

先说结论，最终版本代码如下：

public class KthNum {
 public static int k = 2;
 public static boolean bigK = false;
 
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int kNum = quickSort(arr);
 System.out.println("kNum=" + kNum);
 }
 
 public static int quickSort(int arr[]) {
 int length = arr.length;
 if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
 int left = 0, right = length - 1;
 int p = -1;
 while (k != p + 1) {
 if (k p + 1) {
 left = p + 1;
 }
 p = partition(arr, left, right);
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (bigK ? arr[arrIndex] > pivot : arr[arrIndex] < pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

还是老规矩，我会重点谈思路，到底是如何想出这段代码的，请往下看。

熟悉快排的同学都知道，若不熟悉的同学，可以先看我的这篇[白话解析快速排序][Link 1]。快排使用某一个数作为基准点进行分区，通常基准点左边的数都是小于基准点的，在基准点右边的数都是大于基准点的。

例如1,3,4,2这组数字，使用快排以2为基准点进行倒序排序第一次的结果为3,4,2,1 ，如果你恰好是求第3大的数，那么就是基准点2，只用了一次排序，时间复杂度为O(n)。如果你是求第1大的数或者第2大的数，那么继续在基准点左边进行排序比较即可；如果你是求第4大的数，那么在基准点右边进行排序比较即可。**细心的同学可以发现求第K大的数，K的值是和基准点的下标有关系的**。第一次排序完成后，基准点2的下标为2，使用**下标+1**和**K**进行比较，若**K**等于**下标+1**直接返回当前下标的值；若**K**大于**下标+1**，则继续在基准点右边进行查找；若**K**小于**下标+1**，则继续在基准点左边进行查找。循环查找，直到**K**等于**下标+1**，则结束。

基于以上的思路和对快排的理解，我们得出了计算第K大数的第一个版本1.0。

## ** 1.0**： ##

public class KthNum {
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int k = 2;
 // k=4;
 int kNum = quickSort(arr, 0, arr.length - 1, k);
 System.out.println("kNum=" + kNum);
 
 }
 
 public static int quickSort(int arr[], int left, int right, int k) {
 if (left >= right) return -1;
 int p = partition(arr, left, right);
 while (k != p + 1) {
 if (k p + 1) {
 p = partition(arr, p + 1, right);
 }
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] > pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 }

以上代码在K为2时，可以正常求出第2大的数为6,。但是当K为4时，会发生死循环。

**那么为什么发生死循环:**

思路1：

仔细查看while循环中 if 和 else if 中的代码，分析其执行过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70][]

上图是每一次执行完 partition 方法后，基准点的下标 p 的位置。**通过分析第9次和第14次的执行结果，可以发现如果继续往下走就会进入9-13次的死循环。**现在已经发现了问题，那么造成问题的原因是什么？

2个问题导致的：

**1. while循环中left 和  right 的值一直没发生变化**

**     2. 通过分析第8次的执行结果，可以发现2个相同的值5在比较时不会发生数据交换，这导致7, 6, 5, 4, 5, 3, 3, 2, 1 中的第4个数和第5个数无法形成有序的位置。**

思路2：

将while循环中的代码和快排中的代码对比会发现，**在循环中 left 和  right 的值一直没发生变化的。**初步估计会导致已经排过序的数下次循环会继续参与排序，从而导致死循环。

### 1.0小结： ###

主要是想通过复制粘贴的方式快速实现第K大数的方案，偷懒的心态导致了此版本中的死循环问题

## ** 1.1**： ##

··修复1.0版本中的死循环问题：

public class KthNum {
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int k = 2;
 k=4;
 int kNum = quickSort(arr, 0, arr.length - 1, k);
 System.out.println("kNum=" + kNum);
 
 }
 
 public static int quickSort(int arr[], int left, int right, int k) {
 if (left >= right) return -1;
 int p = partition(arr, left, right);
 while (k != p + 1) {
 if (k p + 1) {
 p = partition(arr, p + 1, right);
 }
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] >= pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

修改了 partition 方法中第4行的代码，从 **arr\[arrIndex\] > pivot** 修改为 **arr\[arrIndex\] >= pivot** 。也就是在2个数相等时依然可以进行比较数据交换。

## ** 2.0**： ##

··修复1.0版本中的while循环中left 和  right 的值一直没发生变化导致死循环问题，也是我们的主线版本：

public class KthNum {
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int k = 2;
 k=4;
 int kNum = quickSort(arr, 0, arr.length - 1, k);
 System.out.println("kNum=" + kNum);
 
 }
 
 public static int quickSort(int arr[], int left, int right, int k) {
 if (left >= right) return -1;
 int p = partition(arr, left, right);
 while (k != p + 1) {
 if(k<p+1){
 right=p-1;
 }else if(k>p+1){
 left=p+1;
 }
 p=partition(arr,left,right);
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] > pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

修改了 quickSort 方法中第5行和第7行的代码，将while循环中的 partition 方法调用放到了 if 外面，在 if 和 else if 中修改 left 和right 的值，这样使用快排计算第K大的数就基本实现了。

## 3.0： ##

这个版本是对2.0版本的优化：

public class KthNum {
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int k = 2;
 k=4;
 int kNum = quickSort(arr, 0, arr.length - 1, k);
 System.out.println("kNum=" + kNum);
 }
 
 public static int quickSort(int arr[], int left, int right, int k) {
 if (left >= right) return -1;
 int p=-1;
 while (k != p + 1) {
 if(k<p+1){
 right=p-1;
 }else if(k>p+1){
 left=p+1;
 }
 p=partition(arr,left,right);
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] > pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

修改了 quickSort 方法中第2行的代码，这里的思路是 quickSort  方法中的第2行和第9行都调用了 partition 方法，我希望可以把它们统一起来，于是我给p赋值为-1，统一调用while循环中的partition方法。

## 4.0： ##

这个版本是对3.0版本的调整优化：

public class KthNum {
 public static int k = 4;
 
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int kNum = quickSort(arr);
 System.out.println("kNum=" + kNum);
 }
 
 public static int quickSort(int arr[]) {
 int length = arr.length;
 if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
 int left = 0, right = length - 1;
 int p = -1;
 while (k != p + 1) {
 if (k p + 1) {
 left = p + 1;
 }
 p = partition(arr, left, right);
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] > pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

优化点：

1. 将 quickSort 方法的局部参数 left 和 right 放到方法内部赋值

2. 移除了原quickSort 方法中 left 和 right  的比较

3. quickSort 方法中添加了 K 值合理性的判断

### 4.0小结发散思考： ###

至此，快排计算第K大的数就完成了。我们还是发散思考一下，既然第K大的数，那么肯定也有求第K小的数的需求。带着这个问题，我们重新审视一下上述4.0的代码，可以得出2种方案：

1. 既然求第K大的数在while循环中可以通过K和P+1，在不同的区间范围排序查找。那么同理，求第K小的数也可以通过K和P的关系算出来。

2. 上述 partition 方法中是通过倒序的方式求第K大的数，那么求第K小的数只需要采用升序的方式即可。

## 4.1： ##

这个版本就是4.0小结中的求第K小的数的第1种解决方案：

public class KthNum {
 public static int k = 3;
 public static boolean bigK = false;
 
 public static void main(String[] args) {
 int arr[] = {3, 2, 3, 1, 7, 4, 5, 5, 6};
 int kNum = quickSort(arr);
 System.out.println("kNum=" + kNum);
 }
 
 public static int quickSort(int arr[]) {
 int length = arr.length;
 if (k <= 0 || k > length) throw new RuntimeException("K值不合理");
 int left = 0, right = length - 1;
 int p = bigK ? -1 : partition(arr, left, right);
 while (k != (bigK ? p + 1 : length - p)) {
 if (bigK ? k length - p) {
 right = p - 1;
 } else if (bigK ? k > p + 1 : k < length - p) {
 left = p + 1;
 }
 p = partition(arr, left, right);
 }
 return arr[p];
 }
 
 public static int partition(int[] arr, int left, int right) {
 int pivot = arr[right];
 int sortIndex = left;
 for (int arrIndex = sortIndex; arrIndex < right; arrIndex++) {
 if (arr[arrIndex] > pivot) {
 swap(arr, arrIndex, sortIndex);
 sortIndex++;
 }
 }
 swap(arr, sortIndex, right);
 return sortIndex;
 }
 
 public static void swap(int[] arr, int i, int j) {
 if (i == j) return;
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
 }
 
 
 }

代码的改动是涉及K和P的关系的比较，属于一个逆势思维。在一串倒序的数中求第K小的数，例如在7, 6, 5, 5, 4, 3, 3, 2, 1 这组数中6是第2大的数，是第8小的数。有兴趣的可以看下，不过重点推荐5.0版本的实现方案。

## 5.0： ##

这个版本就是4.0小结中的求第K小的数的第2种解决方案：

这里新增了一个成员变量 bigK 来做标识：**true代表求第K大的数；false代表求第K小的数**。同时在 partition 方法中的第4行也做了改动：若bigK为true，则采用倒序；若bigK为false，则采用升序。这样就以最小的改动实现了求第K大的数和第K小的数的需求，完美。

[Link 1]: https://blog.csdn.net/Royal_lr/article/details/103119925
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70]: /images/20230528/7bb27d1724fa48348fbbba173202cf2f.png