从n个元素中找出第K小的数 利用快排的思想来实现
从n个无序的顺序表中找出第k小的数，采用快排思想：
先从n个元素中随便寻找一个数m作为分界点,m在列表中的位置为i
当 i = k时，m就是我们要寻找的第k小的数；
当 i > k时，我们就从1~i-1中查找；
【从n个元素中找出第K小的数 利用快排的思想来实现】当 i < k时，就从i+1~n中查找。
实现代码如下所示：
package com.search;
/*
* 从n个数中选出第k小的数
*/
public class SearchKMin {
public static int partion(int A[], int low, int high) {
int pivotkey = A[low];
int temp;
while (low < high) {
while (low < high && A[high] >= pivotkey)
high--;
A[low] = A[high];
while (low < high && A[low] <= pivotkey)
low++;
A[high] = A[low];
}
A[low] = pivotkey;
return low;
}
public staticint quickSort(int A[],int low,int high,int k){
if(low <= high){
int pivotloc = partion(A,low,high);
if(pivotloc == (k-1)){
return A[pivotloc];
}
else if(pivotloc < (k-1)){
return quickSort(A,pivotloc+1,high,k);
}
else{
return quickSort(A,low,pivotloc-1,k);
}
}else{
return -1;
}
}
public static void main(String[] args) {
int A[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
int k =2;
int mink = quickSort(A, 0, A.length - 1,k);
System.out.println("mink:"+mink);
}
}
推荐阅读
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 一个小故事，我的思考。
- Docker应用:容器间通信与Mariadb数据库主从复制
- 一个人的碎碎念
- 猎杀IP
- 七年之痒之后
- 我从来不做坏事
- 喂，你结婚我给你随了个红包
- 异地恋中，逐渐适应一个人到底意味着什么（）