快速選擇算法
一盛霎、基本原理： 從一個數(shù)組中，快速找到一個排名第K大或者第K小的元素耽装。
二愤炸、實現(xiàn)思路：依據(jù)快排的思路，找到軸樞元素的索引與排名k之間的關(guān)系掉奄。
三规个、具體分析：
舉例1：
問題： 假如現(xiàn)在有6個學(xué)生的體重，想知道6個學(xué)生中體重第二輕的是多少kg挥萌？
抽象成如下問題：
在未排序的數(shù)組中绰姻，找到排名第K的元素。
給定一個數(shù)組： [30,83,56,76,21,95] 和 k = 2
輸出： 30
結(jié)合之前學(xué)習(xí)過的快速排序引瀑，我們只需要保證軸樞元素（X）前的元素均比X小狂芋，X后的元素均比X大即可。且比X小的元素為k-1個憨栽，那么此時的X就是我們需要找的第K位元素帜矾。
即沒必要對原數(shù)組進(jìn)行整體的排序，只需要找到滿足條件的元素X即可屑柔。
參照快速排序的partion過程屡萤，在第一輪結(jié)束后，軸樞元素X的位置為ind
import java.util.Arrays;
public class quick_sort_test {
public static void main(String[] args) {
int[] arr = new int[] {30,83,56,76,21,95};
quickSort(arr, 0 ,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public void swap(int[] nums, int i, int j) {
if(i == j) {
return;
}
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public static void quickSort(int[] nums, int left, int right) {
int middle;
if(left < right) {
middle = partition(nums, left, right);
System.out.println("軸樞元素的下標(biāo)：" + middle);
System.out.println("軸樞元素的值：" + nums[middle]);
// 對分界值分隔的兩個數(shù)組掸宛，繼續(xù)遞歸該方法死陆。
// quickSort(nums, left, middle-1);
// quickSort(nums, middle+1, right);
}
}
//執(zhí)行完一次后，輸出分界值的坐標(biāo)
public static int partition(int[] nums, int left, int right) {
if (left > right) {
return 0;
}
int pivot = nums[left];
while(left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
}
將測試數(shù)組傳入，軸樞的元素的下標(biāo)ind為1（即為排名第k=2的元素）措译， X的值為30
問題中的k=2(當(dāng)k=3, k = 1是分別得出以下結(jié)論：)
- 當(dāng) ind = k -1 時别凤，此時的ind對應(yīng)的元素X就是要求解的值。
- 當(dāng) ind < k -1 時领虹，此時需要從軸樞元素分隔的后部分?jǐn)?shù)組開始尋找规哪，范圍為：[ind+1, nums.length-1]
- 當(dāng) ind > k - 1時，測試需要從軸樞元素分隔的前部分?jǐn)?shù)組開始尋找塌衰，范圍為： [0诉稍， ind-1]
落到具體的代碼上：
import java.util.Arrays;
public class quick_select {
public static void main(String[] args) {
int[] arr = {30,83,56,76,21,95};
// 快速選擇算法：從數(shù)組中找出排名第k位的元素，并輸出最疆。
// eg: 從數(shù)據(jù)中找出排名第2的元素杯巨。
int k = 2;
// int k = 3;
// int k = 1;
int result = quickSelect(arr, 0, arr.length-1, k);
System.out.println("排名第" +k + "位的元素值為：" + result + "\n");
System.out.println("此時數(shù)組的內(nèi)容為：" + Arrays.toString(arr
));
}
public static void swap(int[] nums, int i, int j ) {
if(i == j) {
return;
}
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/**
* 快速排序的核心思想是找到排名第k位置的元素， 所以僅需保證前k-1的元素比k位置的元素小即可肚菠，
* 沒有必要對整個數(shù)組進(jìn)行全部的排序
* @param nums
* @param left
* @param right
* @param k
* @return 返回的是排名第K位置的元素值舔箭。
*/
public static int quickSelect(int[] nums, int left, int right, int k) {
if(left > right) {
return 0;
}
while (left < right) {
int privot = nums[left];
while (left < right && nums[right] >= privot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= privot) {
left++;
}
nums[right] = privot;
}
// 完成了第一輪比較，此時left和right相等蚊逢，均指向第一個軸樞元素层扶。即ind = left = right
int ind = left;
if(ind == k - 1) {
return nums[ind];
} else if (ind < k - 1) {
return quickSelect(nums, ind + 1, nums.length-1, k);
} else {
return quickSelect(nums, 0, ind-1, k);
}
}
}
①、當(dāng)k = 2（ind == k - 1）烙荷，執(zhí)行結(jié)果如下：
②镜会、當(dāng)k = 3（ind < k - 1）， 執(zhí)行結(jié)果如下：
③终抽、當(dāng)k = 1（inx > k - 1）戳表，執(zhí)行結(jié)果如下：
觀察該測試數(shù)據(jù)，可以發(fā)現(xiàn)在一輪排序的過程中昼伴，剛好將所有的數(shù)據(jù)排序完成了匾旭，此時難以驗證快速選擇算法的。所以我們更換一組測試數(shù)據(jù)圃郊，執(zhí)行后觀察：符合預(yù)期
int[] arr = {8,2,3,5,10,7,19,4,14};
