企业官网建设流程全解析

次序选择问题

Selection Problem

背景和问题

背景：最小值查找

给定一个数组A，寻找最小值

依次扫一遍，记录最小值

问题：如何求得数组中第k小的元素

中位数…
Selection Problem
input ：a [ 1…n ] 整数k
output ：a [ 1…n ] 中第k小的元素

• 数组排序
  1. 排个序，直接取a[ k-1 ]
  2. O(n * log n)
     ? 是否有必要每个都排好序（是每个的次序都要吗？）
     问题分析：次序选择
• 不必求所有元素的次序
• 左侧右侧并不关心，不需要对齐排序

• 左侧小于k-1个都小于第k个
• 右侧都大于第k个

启发于[[快速排序]]

回顾

intPartition(int*a,intp,intr){inti=p-1,x=a[r];for(intj=p;j<r;j++){if(a[j]<=x){i++;swap(&a[i],&a[j]);}}swap(&a[i+1],&a[r]);intq=i+1;returnq;}

• 其中每次从左往右找，一直维护i是左侧最右端，j是右侧最右端
• 不断的维护i左侧小于主元，i+1右侧大于主元

  • 若扫的a [ j ] 小于等于主元x，i，j右移，交换a [ j ] a [ i+1]
    

  • 若扫的a [ j ] 大于x，j右移继续，i不用动

• 一次Partition之后，返回的主元的标点q，就是当前的第q-p+1大

求解

一次Partition之后，返回的主元的标点q，就是当前的第q-p+1大

只需要判断k和q-p+1的大小

1. k=q-p+1，a [ q ] 就是第k小元素
2. k<q-p+1，在左侧，在a[𝒑. . 𝒒 − 𝟏]中寻找第𝒌小元素
3. k<q-p+1，在右侧，在a[ 𝒒 + 𝟏. . 𝒓 ]中寻找第𝒌 − (𝒒 − 𝒑 + 𝟏)小元素

分解原问题-> 解决子问题 -> (合并问题解 )

子问题不需要合并，顺着选择走就行

intSelection(int*a,intp,intr,intk){intx;intq=Partition(a,p,r);if(k==q-p+1){x=a[q];}elseif(k<q-p+1){x=Selection(a,p,q-1,k);}else{x=Selection(a,q+1,r,k-(q-p+1));}returnx;}

复杂度分析

摆脱最坏情况

随机划分
Randomized-Partition
随机选择主元

intRandomized_Partition(int*a,intp,intr){ints=p+rand()%(r-p+1);swap(&a[s],&a[r]);intq=Partition(a,p,r);returnq;}

期望复杂度O(n)O(n)O(n)

测试代码

#include<stdio.h>voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}intPartition(int*a,intp,intr){intpivot=a[r];inti=p-1;for(intj=p;j<r;j++){if(a[j]<=pivot){i++;swap(&a[i],&a[j]);}}swap(&a[i+1],&a[r]);returni+1;}intSelection(int*a,intp,intr,intk){if(p>r||k<1||k>r-p+1){return-1;// error case}intq=Partition(a,p,r);if(k==q-p+1){returna[q];}elseif(k<q-p+1){returnSelection(a,p,q-1,k);}else{returnSelection(a,q+1,r,k-(q-p+1));}}voidrunTest(int*arr,intn,intk){intresult=Selection(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;}