無序數組的中第k小的數字

04-17

在一個無序數組中查找第k小的數字,默認第0小的數字為最小數字

思路:

在隨機快速排序演算法中，先在數組中隨機選擇一個數字，然後調整數組中數字的順序，使得比選中數字小的都在左邊，比數字大的都在右邊。

如果這個選中的數字下標正好是k，那麼這個數字就是我們要找的數字。如果下標大於k，就去左邊尋找。如果下標小於k，就去右邊尋找。

參考代碼:

root@gt:/home/temp# ./a.out 6root@gt:/home/temp# cat 1.c#include <stdio.h>void exchange(int* pa,int* pb){ int temp = *pa; *pa = *pb; *pb = temp;}int partition(int* parr,int start,int end){ int index = parr[end]; int i = start - 1; int j = start; for(;j < end;++j) { if(parr[j] <= index) { ++i; exchange(&parr[i],&parr[j]); } } exchange(&parr[i + 1],&parr[j]); return i + 1;}int core(int* parr,int len,int k){ if(parr == NULL || len <= 0) return 0; int start = 0; int end = len -1; int index = partition(parr,start,end); while(index != k) { if(index > k) { end = index - 1; index = partition(parr,start,end); } else { start = index + 1; index = partition(parr,start,end); } } int res = parr[k]; return res;}int main(){ int parr[] = {9,3,2,4,7,6,5,8,1}; int res = core(parr,sizeof(parr)/sizeof(int),5); printf("%d ",res); return 0;}