快速排序计算第K大的数

article/2025/9/30 15:09:05

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

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) {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 (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;}}

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

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

        例如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, left, p - 1);} else 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 中的代码，分析其执行过程如下：

上图是每一次执行完 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, left, p - 1);} else 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) {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;}}

优化点：

    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 < p + 1 : 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种解决方案：

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) {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 (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;}}

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

 


http://chatgpt.dhexx.cn/article/Dp8KOrGn.shtml

相关文章

寻找第K大的数 C语言实现的一种方法

寻找第K大的数 C语言实现的一种方法

描述 在一个数组中&#xff0c;找到第K 大的数值一个数组&#xff0c;如&#xff1a;[3,2,1,5,6,4] &#xff0c;输入 2&#xff0c;返回&#xff1a;5也就是这个K的取值&#xff0c;是从 1 开始的&#xff0c;不超过数组的最大个数 解决思路 可以使用任意的排查函数&#x…
阅读更多...
C++——寻找第k大的数

C++——寻找第k大的数

给出一个数组&#xff0c;找出数组的第k大的数&#xff1a;基于快速排序的思路&#xff0c;每次快排后&#xff0c;基准的左边都是比其小的数&#xff0c;右边都是比其大的数&#xff0c;一次快排结束后&#xff0c;若基准所处的位置正好是第k大&#xff08;即基准右边有k-1个数…
阅读更多...
面试题：从n个数中找出第K大的数

面试题：从n个数中找出第K大的数

参考https://blog.csdn.net/orangefly0214/article/details/84997668的思路 从有n个元素的乱序数组中找出第k大的元素 方法1&#xff1a;基于冒泡排序和简单选择排序&#xff0c;时间复杂度o(n*k) 我们知道&#xff0c;在冒泡排序和简单选择排序中&#xff0c;最外层的循环每…
阅读更多...
在N个数中查找第K大的数字（Top K问题）

在N个数中查找第K大的数字（Top K问题）

在N个乱序数字中查找第k大的数字&#xff0c;时间复杂度可以减小至 O(N*logN)O(N)O(1)O(2) 答案&#xff1a;B 所谓“第&#xff08;前&#xff09;k大数问题”指的是在长度为n(n>k)的乱序数组中S找出从大到小顺序的第&#xff08;前&#xff09;k个数的问题。 注意&…
阅读更多...
idea控制台乱码解决方法

idea控制台乱码解决方法

一、问题情况&#xff1a; IntelliJ IDEA 控制台输出中文乱码部分如图所示&#xff1a; 二、解决方法&#xff1a; 1.打开tomcat配置页面&#xff0c;Edit Configurations。 2.选择项目部署的tomcat&#xff0c;在配置项VM options文本框中输入-Dfile.encodingUTF-8,点击Appl…
阅读更多...
idea 控制台乱码问题的问题

idea 控制台乱码问题的问题

工程(环境window10&#xff0c;gradle-6.8.3版本&#xff0c;编辑器IntelliJ IDEA 2019.3.4&#xff09; 一&#xff09;问题表现编译build的时候控制台带中文信息的会乱码 1、 找到Help->Editor Custom VM Options 2、 添加 -Dfile.encodingUTF-8 该设置是针对编辑器级别…
阅读更多...
IDEA中控制台乱码的解决方式

IDEA中控制台乱码的解决方式

1.在设置中的“文件编码”中将3个位置设为UTF-8&#xff0c;注&#xff1a;此处设置与控制台乱码无关&#xff0c;3处可均设为UTF-8或均设为系统默认值。 2.在Tomcat的“编辑配置”中&#xff0c;将VM options设为-Dfile.encodingGBK(与第三步类似&#xff0c;默认即为GBK)。…
阅读更多...
IDEA控制台乱码终极解决办法

IDEA控制台乱码终极解决办法

【关于IDEA中文乱码的终极解决方法】 查了很多资料&#xff0c;大多数博主都是修改四个地方&#xff1a;&#xff08;前四步&#xff09;如果前四步还是不行&#xff0c;可以看五、六步。第一步&#xff1a;idea 安装目录下/bin/idea.exe.vmoptions 和/bin/idea64.exe.vmoption…
阅读更多...
IDEA控制台乱码解决

IDEA控制台乱码解决

解决办法&#xff1a; 打开Intellij的安装的bin目录&#xff08;D:\Program Files\JetBrains\IntelliJ IDEA 14.0\bin &#xff09;&#xff0c;找到上图的两个文件&#xff08;根据你的系统是32位或64位选择其中一个配置文件&#xff09;&#xff0c;在配置文件中添加&#xf…
阅读更多...
多种方法帮你解决tomcat项目部署，idea控制台乱码问题

多种方法帮你解决tomcat项目部署，idea控制台乱码问题

解决在使用Tomcat过程中idea控制台出现的乱码问题 以下将介绍几种方法&#xff08;都是小编亲测实用的方法&#xff09;&#xff0c;尝试并寻找适合自己的方法即可 由于我已经处理过了乱码问题&#xff0c;我就重新配置一下 &#xff08;我有效解决的方案是把-Dfile.encoding…
阅读更多...
idea 控制台乱码

idea 控制台乱码

1.我原来的修改idea的控制台乱码是 在ideasettings--Editor--File encodings修改为UTF-8 2.tomcat 中修改的conf logging.properties配置文件 由UTF-8修改为GBK 以上是我之前的修改.最近有个项目这样配置之后在项目运行的时候.有个页面要获取一个json字段.但是代码中有乱码的…
阅读更多...
IDEA控制台乱码问题,原因解决方式,解决不了算我输

IDEA控制台乱码问题,原因解决方式,解决不了算我输

IDEA 控制台乱码问题 文章目录 IDEA 控制台乱码问题为了节省大家时间, 直接展示下我的编码配置方案我的编码配置原则我的编码配置 另外说一下几个重要但是和乱码无关的配置乱码原因解决方式我为什么推荐控制台使用 GBK我的编码设置思想第一种解决方案的弊端end 附加技巧如何找出…
阅读更多...
解决idea控制台乱码

解决idea控制台乱码

控制台乱码如下&#xff1a; 解决方案一&#xff1a;修改当前 Web 项目 Tomcat Server 的虚拟机输出选项 上方导航栏“Run→Edit Configurations…”进入配置页面&#xff0c;修改当前 Web 项目 Tomcat Server 的虚拟机输出选项 VM options 添加 -Dfile.encodingUTF-8 。重启&…
阅读更多...
IDEA控制台乱码(已解决)

IDEA控制台乱码(已解决)

先来说说我遇到的问题&#xff0c;用IDEA打开项目首先可以保证编辑器内不会乱码&#xff0c;启动Tomcat后控制台出现乱码   我在网上找了很多方式都没有解决&#xff0c;大多数的方式由以下几种&#xff1a; 进入File->Settings->Editor->File Encodings 将右侧的所…
阅读更多...
详细解决tomcat乱码 IDEA控制台乱码

详细解决tomcat乱码 IDEA控制台乱码

1、启动Tomcat时打印出一大堆看不懂的文字 如下图&#xff1a; 原因&#xff1a;产生乱码的根本原因就是编码和解码不一致 解决办法&#xff1a;将打开tomcat的安装目录conf下的logging.properties文件&#xff0c;将java.util.logging.ConsoleHandler.encoding UTF-8 修改为…
阅读更多...
MyBatis、IDEA控制台乱码

MyBatis、IDEA控制台乱码

控制台乱码&#xff1a; 解决方法 在Maven模块的pom.xml中添加 <properties><maven.compiler.source>8</maven.compiler.source><maven.compiler.target>8</maven.compiler.target><project.build.sourceEncoding>UTF-8</project.buil…
阅读更多...
【IDEA乱码解决方案】IDEA控制台乱码解决方案收集

【IDEA乱码解决方案】IDEA控制台乱码解决方案收集

乱码实例 如图&#xff1a; 我的解决方案 在“帮助”——“编辑自定义VM选项”中&#xff0c;最后一行加上代码&#xff1a; -Dfile.encodingUTF-8然后重启IDEA。 其他方案一&#xff1a;修改IDEA安装目录下的idea64.exe.vmoptions IDEA快捷方式右键->属性->打开文件所…
阅读更多...
idea控制台乱码问题

idea控制台乱码问题

1.控制台乱码 控制台tomcat启动信息乱码解决&#xff08;红色字体&#xff09; 1 在本地 tomcat 的配置文件中找到 logging.properties 文件设置日志输出的编码为 UTF-8 追加的配置信息为&#xff1a; java.util.logging.ConsoleHandler.encoding UTF-8 2 在IDEA中配置tomcat的…
阅读更多...
解决IDEA控制台中文乱码问题(Tomcat、动态网页项目)

解决IDEA控制台中文乱码问题(Tomcat、动态网页项目)

博主在使用idea的创建动态网页的时候&#xff0c;遇到了控制台中文乱码问题&#xff0c;在网上参考了多种解决方案之后&#xff0c;终于将问题成功解决。现在将自己遇到问题的情况和解决问题的方法总结如下&#xff1a; Idea控制台中文乱码问题通常有以下两种情况&#xff08;…
阅读更多...
idea控制台中文乱码的解决方法（最后一种亲测有效）

idea控制台中文乱码的解决方法（最后一种亲测有效）

idea控制台中文乱码的解决方法&#xff08;三种&#xff0c;亲测有效&#xff09; 问题情况&#xff1a; IntelliJ IDEA 控制台输出中文乱码部分如图所示&#xff1a; 解决方法&#xff1a; 方法一&#xff1a; 1.打开tomcat配置页面&#xff0c;Edit Configurations。 2…
阅读更多...
推荐文章

Copyright @ 2022~2023