|
6#
楼主 |
发表于 2007-10-11 02:02:22
|
只看该作者
小的在此先谢过各位了,你们的肯定我会当作动力的。。。
下面是我们今天作业的一些资料
简单的选择排序
选择排序的基本思想是,在待排区段的记录序列中选出关键字最大或最小的记录,并将它移动到法定位置。第 i(i=1,2,…,n-1)趟的简单选择排序(序列中前 i-1 个记录的关键字均小于后 n-i+1 个记录的关键字)的作法是,在后 n-i+1 个记录中选出关键字最小的记录,并将它和第 i 个记录进行互换。如右图所示。
算法
void SelectSort (SqList &L)
{
// 对顺序表L作简单选择排序
for (i=1; i<L.length; ++i) { // 选择第 i 小的记录,并交换到位
j = i;
for ( k=i+1; k<=L.length; k++ )
// 在L.r[i..L.length]中选择关键字最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ;
if ( i!=j ) L.r[j] ←→L.r; // 与第 i 个记录互换
}// for
} // SelectSort
无论待排序列处于什么状态,选择排序所需进行的"比较" 次数都相同,为 ,而 "移动" 次数在待排序列为"正序" 时达最小为0,在 "逆序" 时达最大为 3(n-1)。
选择排序其中有堆排序,堆排序的时间复杂度为O (nlogn)。和选择排序雷同,无论待排序列中的记录是正序还是逆序排列,都不会使堆排序处于"最好"或"最坏"的状态。 |
|