前几天的那个问题本问题“对1000000个数进行排序找出10个最大的数”也可以用插入排序或选择排序，对于选择排序在目标数中每次选择最大的数，与前面的10个数进行交换，大约需O(10*n)的时间消耗。如下算法：
void InsertSort(long data[], long count)
{
/*
* 在count个数中找到最大的数，与第0个进行交换，然后再在后count-1中找到最大的，与
* 第1个进行交换，依此类推，直到前10个数都与相应的数交换完毕，输出前10个数就行了，
* 这就是选择排序的一部分，不过同快速排序和堆排序一样却破坏了原来的data[]。
*/
long temp, num = 0; // num统计运行的次数
long i = 0, j = 0, k = 0; // 用k纪录data的前10位数
for (i = 0; i < 10; i++)
{
++num;
temp = data[k]; // data[k]作为监视哨
for (j = i; j < count; j++ )
{
++num;
if (data[k] < data[j])
{
data[k] = data[j];
}
}
data[j] = temp; // 交换到位
k++; // 下一个
}
}
|