c语言算法 - 分而治之算法 - 选择排序

核心提示：对于给定的n个元素的数组a[0 : n - 1]，要求从中找出第k小的元素，c语言算法 - 分而治之算法 - 选择排序，当a[0 : n - 1]被排序时，该元素就是a[k - 1]，只需进行0次或1次递归调用，新代码见程序1 4 - 7，假设n=8，每个元素有两个域k e y和I D

对于给定的n个元素的数组a[0 : n - 1]，要求从中找出第k小的元素。当a[0 : n - 1]被排序时，该元素就是a[k - 1]。假设n=8，每个元素有两个域k e y和I D，其中k e y是一个整数，I D是一个字符。假设这8个元素为[( 1 2 ,a)，( 4 ,b)，( 5 ,c)，( 4 ,d)，( 5 ,e)，( 1 0 ,f)，( 2 ,g)，( 2 0 ,h)], 排序后得到数组[( 2 ,g)，( 4 ,d)，( 4 ,b)，( 5 ,c)，( 5 ,e)，( 1 0 ,f)，( 1 2 ,a)，( 2 0 ,h)]。如果k=1，返回I D为g 的元素；如果k=8，返回I D为h 的元素；如果k=6，返回是I D为f 的元素；如果k=2，返回I D为d 的元素。实际上，对最后一种情况，所得到的结果可能不唯一，因为排序过程中既可能将I D为d 的元素排在a[1]，也可能将I D为b 的元素排在a[1]，原因是它们具有相同大小的k e y，因而两个元素中的任何一个都有可能被返回。但是无论如何，如果一个元素在k=2时被返回，另一个就必须在k=3时被返回。

选择问题的一个应用就是寻找中值元素，此时k=[n / 2]。中值是一个很有用的统计量，例如中间工资，中间年龄，中间重量。其他k值也是有用的。例如，通过寻找第n / 4 , n / 2和3 n / 4这三个元素,可将人口划分为4份。

选择问题可在O( n l o g n )时间内解决，方法是首先对这n个元素进行排序（如使用堆排序式或归并排序），然后取出a[k - 1]中的元素。若使用快速排序（如图1 4 - 11所示），可以获得更好的平均性能，尽管该算法有一个比较差的渐近复杂性O( n2 )。

可以通过修写程序1 4 - 6来解决选择问题。如果在执行两个w h i l e循环后支点元素a[l]被交换到a[j] ,那么a[l]是a[l : j]中的第j - l + 1个元素。如果要寻找的第k个元素在a[l : r]中，并且j - l + 1等于k，则答案就是a[l]；如果j - l + 1 <k，那么寻找的元素是r i g h t中的第k - j + l - 1个元素，否则要寻找的元素是left中的第k个元素。因此，只需进行0次或1次递归调用。新代码见程序1 4 - 7。S e l e c t中的递归调用可用f o r或w h i l e循环来替代（练习2 5）。

程序14-7 寻找第k个元素

template
T Select(T a[], int n, int k)
{// 返回a[0 : n - 1]中第k小的元素
// 假定a[n]是一个伪最大元素
if(k <1 || k >n) throw OutOfBounds();
return select(a, 0, n-1, k);
}
template
T select(T a[], int l, int r, int k)
{// 在a[l : r]中选择第k小的元素
if(l >=r) return a[l];
int i=l, // 从左至右的游标
j=r + 1; // 从右到左的游标
T pivot=a[l];
// 把左侧>=pivot的元素与右侧<=pivot 的元素进行交换
while(true) {
do {// 在左侧寻找>=pivot 的元素
i=i + 1;
} while(a[i] <pivot);
do {// 在右侧寻找<=pivot 的元素
j=j - 1;
} while(a[j] >pivot);
if(i >=j) break; // 未发现交换对象
Swap(a[i], a[j]);
}
if(j - l + 1==k) return pivot;
// 设置p i v o t
a[l]=a[j];
a[j]=pivot;
// 对一个段进行递归调用
if(j - l + 1 <k)
return select(a, j+1, r, k-j+l-1);
else return select(a, l, j-1, k);
}