你好呀，我是灰小猿，一個超會寫bug的程式猿！
歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！
標題：快速排序
以下代碼可以從陣列a[]中找出第k小的元素
它使用了類似于快速排序中的分治演算法，期望時間復雜度是O(N)的，
請仔細閱讀分析原始碼，填寫劃線部分缺失的內容
package 一八年省賽真題; import java.util.Random; public class Main { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(_______________); //填空 else return quickSelect(a, l, i - 1, k); } public static void main(String[] args) { int a[] = {1,4,2,8,5,7}; System.out.println(quickSelect(a, 0, 5, 4)); } }注意：只提交劃線部分缺少的代碼，不要抄寫任何已經存在的代碼或符號，
解題思路
本題在求解的時候根據題意就應該采用快速排序中的分治法來進行思考，該方法的基本思想是：采用了一種分治的策略，將原問題分解為若干個規模更小但結構與原問題相似的子問題，遞回地解這些子問題，然后將這些子問題的解組合為原問題的解，
然后我們可以很顯然的看到最后填空的部分是一個遞回，那么一定是子問題，所以根據else后面的代碼，就可以推出正確答案，
關于這幾種常用排序的基本思路，大家可以看我的這篇文章：“用大白話和面試官扯“八大常用排序演算法的基本思想””
答案原始碼：
package 一八年省賽真題; import java.util.Random; public class Year2018_Bt5 { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(a, i + 1, r, k - i + l - 1); //填空 else return quickSelect(a, l, i - 1, k); } public static void main(String[] args) { int a[] = {1,4,2,8,5,7}; //1，2，4，5，7，8 //輸出5 System.out.println(quickSelect(a, 0, 5, 6)); } }
輸出樣例：
其中有不足或者改進的地方，還希望小伙伴留言提出，一起學習！
感興趣的小伙伴可以關注專欄！
灰小猿陪你一起進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/273764.html
標籤：其他
上一篇：【ArcGIS Engine二次開發】入門基礎（2）：ArcGIS開發方式（VBA、DLL、Add-in、Engine）對比