一个选择问题的分析

设有一组N个数，要确定其中第k个最大者，这称为选择问题（selection problem）.

该问题的一种解法是将这N个数读进一个数组中，再通过某种简单的算法，比如冒泡排序，以递减顺序将数组排序，然后返回位置k上的元素。

更好一点的算法可以先把前k哥元素读入数组中并（以递减的方式）进行排序。接着将剩下的元素逐个读入。当读到一个新元素时，如果该元素小于数组中第k个元素则忽略之，否则就将其放到数组中的正确位置上，同时将数组中的一个元素挤出数组。当算法终止时，返回第k个位置上的元素作为答案。

冒泡法排序：

#include <stdio.h>
void BubbleSort(int array[],int n);
void PrintArray(int array[],int n);
void main()
{
	int array[6]={23,45,12,6,8,3};
	BubbleSort(array,6);
	PrintArray(array,6);
}
void BubbleSort(int array[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++)
		{
			if(array[j]<array[j+1])
			{
				int temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
			}
		}
	}
}
void PrintArray(int array[],int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d/n",array[i]);
	}
}

冒泡排序效率分析，若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字的比较，且不移动记录。反之若初始序列为“逆序”，则进行n-1趟排序，需进行(2~i=n)∑(i-1)=n(n-1)/2,最坏的时间复杂度是O(n ^2)