第一种算法是最容易想到的，就是利用快速排序的思想，将一个数组分成以某一个数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);
}
#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;
}
{
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;
}