本文為原創，如需轉載，請注明作者和出處，謝謝！
第一種算法是最容易想到的，就是利用快速排序的思想，將一個數組分成以某一個數X為軸，左邊的所有的數都比X小，而右邊的數都比X大。但我快速排序不同的是，在這個算法中只考慮X的一邊，而不是兩邊都考慮。
如果X的位置是i,那么要得到第k個數，如果k<=i, 那么這個數一定在i的左邊，否則在i的右邊。
源碼如下：
#include <stdio.h>
#include <stdlib.h>
int new_random(int min, int max)
{
return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}
void swap(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
int partition(int A[], int p, int r)
{
int i = p - 1, j;
for(j = p; j < r; j++)
{
if(A[j] <= A[r])
{
i++;
swap(&A[i], &A[j]);
}
}
swap(&A[i + 1], &A[r]);
return i + 1;
}
int randomize_partition(int A[], int p, int r)
{
int i = new_random(p, r);
swap(&A[i], &A[r]);
return partition(A, p, r);
}
//第一種算法
int randomized_select(int data[], int p, int r, int k)
{
if(k > (r - p + 1)) return 0;
if(p == r) return data[p];
int i = randomize_partition(data, p, r);
//int i = partition(data, p, r); //不好使，死循環, 必須用隨機數，在第二步時總是在最大數處劃分
int count = i - p + 1;
if(k <= count)
return randomized_select(data, p, i, k);
else
return randomized_select(data, i + 1, r, k - count);
}
另外一種對這種算法做了一下改進，即將數組每5個數一組進行排序，然后取得它的中位數，再對這些中位數進行排序。然后先出的軸X最比較好的，因此X的左邊和右邊的數總是很平均，所以平均查找速度更快。算法如下：
void quicksort(int data[], int b, int e)
{
if(b < e)
{
int k = partition(data, b, e);
quicksort(data, b, k - 1);
quicksort(data, k + 1, e);
}
}
int partition1(int A[], int p, int r, int x)
{
int i = p - 1, j;
for(j = p; j <= r; j++)
{
if(A[j] <= x)
{
i++;
swap(&A[i], &A[j]);
}
}
A[i + 1] = x;
return i + 1;
}
//第二種算法
int select_new(int data[], int p, int r, int k)
{
if(r - p < 75)
{
quicksort(data, p, r);
return data[p + k - 1];
}
int i;
for(i = 0; i <= (r - p - 4) / 5; i++)
{
quicksort(data, p + 5 * i, p + 5 * i + 4);
swap(&data[p + 5 * i + 2], &data[p + i]);
}
int x = select_new(data, p, p + (r - p - 4) / 5, (r - p - 4)/10); // 得到更好的軸X
i = partition1(data, p, r, x);
int count = i - p + 1;
if(k <= count)
return select_new(data, p, i, k);
else
return select_new(data, i + 1, r, k - count);
}
int main()
{
int data[] = {3, 1, 7, 34, 8, 11, 678, 12, -1, 100};
printf("%d\n", randomized_select(data, 0, 9, 2));
int data1[] = {3, 1, 7, 34, 8, 11, 678, 12, -1, 100};
printf("%d\n", select_new(data1, 0, 9, 2));
return 0;
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining