題目：

E 快速排序：以下代碼可以從數組a[]中找出第k小的元素。
它使用了類似快速排序中的分治算法，期望時間復雜度是O(N)的。
請仔細閱讀分析源碼，填寫劃線部分缺失的內容。

#include <stdio.h> int quick_select(int a[], int l, int r, int k) {int p = rand() % (r - l + 1) + l;int x = a[p];{int t = a[p];a[p] = a[r];a[r] = t;}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 quick_select( _____________________________ ); //填空elsereturn quick_select(a, l, i - 1, k); } int main() {int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};printf("%d\n", quick_select(a, 0, 14, 5));return 0; }

注意：只填寫劃線部分缺少的代碼，不要抄寫已經存在的代碼或符號。

分析：

好久沒見過快排了，復習也沒看過，這里遇到了就簡單說一下，加深一下印象：
快排是最快的通用內部排序算法。按照分治三步法：
（1）劃分問題：將數組的各個元素重排后分為左右兩個部分，使得左邊的任意元素都小于或等于右邊的任意元素。
（2）遞歸求解：把左右兩邊分別排序；
（3）合并問題：不用合并，因為此時數組已經完全有序。
快排由于劃分方式不同，版本很多，在這里這道題用的是隨機數劃分： int p = rand() % (r - l + 1) + l;表示閉區間【l~r】的任意一個數。

先看參數的作用：
這里的參數l表示左指針，r表示右指針（功能同快速排序一致）
參數1：a表示數組不變
參數2：l表示左指針下標邊界
參數2：r表示右指針下標邊界
參數4：k表示選擇第k小的元素

回到快速排序的各個指針的變化：
l~i區間內都是比樞紐小的，一共i-l+1個元素；
i+1~r都是比樞紐大的
如果i-l+1比k大，說明要在l~i-1中找；還是找第k個元素
如果i-l+1比k小，說明要在i+1 ~r某個值中找，這個值是多少呢？要看還需要找到新一輪遞歸中找第多少小的元素，這里新參數k就等于 原k減去當前一輪的l~i的個數 即k-(i-l+1)

//#include <stdio.h> #include<bits/stdc++.h>int quick_select(int a[], int l, int r, int k) {int p = rand() % (r - l + 1) + l; //l~r之間的一個隨機數int x = a[p];//隨機數a[p]的值{int t = a[p]; //交換隨機數a[p]和高位右邊第一個數a[p] = a[r];a[r] = t;}int i = l, j = r; //i左指針 j右指針while(i < j){while(i < j && a[i] < x)i++;// 最后i==j 或者 a[i]>=xif(i < j) //如果a[i]>=隨機數x{a[j] = a[i]; //選一個比x大的數 放到高位j--;}while(i < j && a[j] > x)j--;// 最后j==i 或者 a[i]<=xif(i < j) //如果a[i]<=隨機數x{a[i] = a[j]; //選一個比x小的數 放到低位i++;}}a[i] = x;// p = i;//這里改了p的值 說明會用到p,且p的值等于i的值if(i - l + 1 == k)return a[i];if(i - l + 1 < k)return quick_select(a,i+1,r,k-(i-l+1)); //填空elsereturn quick_select(a, l, i - 1, k);//a數組不變 k不變 }int main() {int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};printf("%d\n", quick_select(a, 0, 14, 5));return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的2018年蓝桥杯B组题E题+快排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。