次序选择问题

次序选择问题Selection Problem背景和问题背景最小值查找给定一个数组A寻找最小值依次扫一遍记录最小值问题如何求得数组中第k小的元素中位数…Selection Probleminput a [ 1…n ] 整数koutput a [ 1…n ] 中第k小的元素数组排序排个序直接取a[ k-1 ]O(n * log n)? 是否有必要每个都排好序是每个的次序都要吗问题分析次序选择不必求所有元素的次序左侧右侧并不关心不需要对齐排序左侧小于k-1个都小于第k个右侧都大于第k个启发于[[快速排序]]回顾intPartition(int*a,intp,intr){intip-1,xa[r];for(intjp;jr;j){if(a[j]x){i;swap(a[i],a[j]);}}swap(a[i1],a[r]);intqi1;returnq;}其中每次从左往右找一直维护i是左侧最右端j是右侧最右端不断的维护i左侧小于主元i1右侧大于主元若扫的a [ j ] 小于等于主元xij右移交换a [ j ] a [ i1]若扫的a [ j ] 大于xj右移继续i不用动一次Partition之后返回的主元的标点q就是当前的第q-p1大求解一次Partition之后返回的主元的标点q就是当前的第q-p1大只需要判断k和q-p1的大小kq-p1a [ q ] 就是第k小元素kq-p1在左侧在a[. . − ]中寻找第小元素kq-p1在右侧在a[ . . ]中寻找第 − ( − )小元素分解原问题- 解决子问题 - (合并问题解 )子问题不需要合并顺着选择走就行intSelection(int*a,intp,intr,intk){intx;intqPartition(a,p,r);if(kq-p1){xa[q];}elseif(kq-p1){xSelection(a,p,q-1,k);}else{xSelection(a,q1,r,k-(q-p1));}returnx;}复杂度分析最好T(n)O(n)O(n)O(n)最坏T(n)O(n2)O(n^2)O(n2)算法名称最好情况复杂度最坏情况复杂度固定位置快速排序O(nlog⁡n)O(n \log n)O(nlogn)O(n2)O(n^2)O(n2)固定位置次序选择O(n)O(n)O(n)O(n2)O(n^2)O(n2)摆脱最坏情况随机划分Randomized-Partition随机选择主元intRandomized_Partition(int*a,intp,intr){intsprand()%(r-p1);swap(a[s],a[r]);intqPartition(a,p,r);returnq;}期望复杂度O(n)O(n)O(n)测试代码#includestdio.hvoidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}intPartition(int*a,intp,intr){intpivota[r];intip-1;for(intjp;jr;j){if(a[j]pivot){i;swap(a[i],a[j]);}}swap(a[i1],a[r]);returni1;}intSelection(int*a,intp,intr,intk){if(pr||k1||kr-p1){return-1;// error case}intqPartition(a,p,r);if(kq-p1){returna[q];}elseif(kq-p1){returnSelection(a,p,q-1,k);}else{returnSelection(a,q1,r,k-(q-p1));}}voidrunTest(int*arr,intn,intk){intresultSelection(arr,0,n-1,k);if(result-1){printf(Test failed: invalid input (n%d, k%d)\n,n,k);}else{printf(The %d-th smallest element is: %d\n,k,result);}}intmain(){inta[]{7,10,4,3,20,15};intb[]{1,2,3,4,5};intc[]{9};intd[]{5,3,8,6,2};printf(Test Case 1:\n);runTest(a,6,3);printf(\nTest Case 2:\n);runTest(b,5,1);printf(\nTest Case 3:\n);runTest(c,1,1);printf(\nTest Case 4:\n);runTest(d,5,4);printf(\nEdge Case (invalid k):\n);runTest(a,6,0);return0;}