C语言 谁能讲解一下选择排序法以及有效排序。

Question

如题所述

Answer 1

1、直接选择排序的基本思想
　
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为r[1..n]，有序区为空。
②第1趟排序

　在无序区r[1..n]中选出关键字最小的记录r[k]，将它与无序区的第1个记录r[1]交换，使r[1..1]和r[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
③第i趟排序
　　第i趟排序开始时，当前有序区和无序区分别为r[1..i-1]和r[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录r[k]，将它与无序区的第1个记录r[i]交换，使r[1..i]和r[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

　这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
直接选择排序的具体算法如下：
　void
selectsort(seqlist
r)
　{

int
i，j，k；

for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)

k=i；

for(j=i+1;j<=n;j++)
//在当前无序区r[i..n]中选key最小的记录r[k]

if(r[j].key<r[k].key)

k=j;
//k记下目前找到的最小关键字所在的位置

if(k!=i){
//交换r[i]和r[k]

r[0]=r[i]；r[i]=r[k]；r[k]=r[0]；
//r[0]作暂存单元

}
//endif

}
//endfor

}
//seleetsort

Answer 2

用[4,1,3,2]作例子吧
(1)找出最小的元素-----(4,1),即用4和1比较,是有效排序，比较结果是1比较小，因此1再和3，2比较，（1，3），（1，2）这两次比较就不是有效比较了（1在3，2前面且比它们小）
因此第一轮排序为[1，4，3，2]
最小元素和第一个元素互换
（2）在剩余序列中继续找最小的元素（即排除了1）-----（4，3）比较，是有效排序。3比较小，因此3再和2比较，（3，2）是有效排序。找出最小的元素2。
第二轮排序为[1，2，3，4]
2和第二个元素4互换
（3）依次类推，（3，4）不是有效排序了。
因此，最后结果为[1，2，3，4]
有效排序为（4，1)
(4,3)
(3,2)
程序这东西要自己想，况且这个应该挺容易想出来的。。。。