简单选择排序算法 Simple Selection Sort
浏览数：20 /
时间：2015年06月08日
1.简单选择排序法的思想：
通过n-i 次关键字间的比较，从n-i+1 个记录中选出关键字最小的记录，并和第i (1<= i <=n)个记录交换之。
1 void SelectSort( SqList * L) 2 { 3 int i, j, min; 4 for(i=1; i<L->length; i++) 5 { 6 min = i; 7 for(j=i+1; j<=L->length; j++) 8 { 9 if(L->r[min] > L->r[j]) 10 { 11 min = j; 12 } 13 } 14 if(i != min) 15 { 16 swap(L, i, min); 17 } 18 } 19 }
2.简单选择排序复杂度分析
无论是最好最差的情况，比较次数都是一样多，第 i 趟排序需要进行 n-i 次关键字的比较，此时需要比较∑1n-1 (n-i) = n-1 + n-2 +... +1 = n(n-1)/2 次。
当最好的时候，交换为0，最差的时候，交换的次数为n-1次。
基于最终的排序时间是比较和交换的次数总和，因此，总的时间复杂度依然是O(n2).
虽然与冒泡算法同为O(n2)，但简单排序算法在性能上还是要略优于冒泡算法。它最大的特点是交换数据次数相当少，这样就节约了相应的时间。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
