简单选择排序(SELECT SORT)

简单选择排序的原理比较简单：

• 遍历整个待排序序列，选择出最小(大)的值，并与待排序序列的第一个元素进行交换；
• 每一选择，都会选择出一个剩余元素中最小(大)的元素，放在最终的位置上;

选择排序的一些特征总结：

• 第i回合的剩余元素是(n-i+1)个，其中第一次是n个。
• 排序要进(n-1)次(最后一趟只剩一个元素，元素合适的最后一位置上)；
• 每一趟要在(n-i+1)个元素中选择一个最小(大)的元素，要进行(n-i)次比较，一共要进行比较(n-1)趟，所以比较次数是：(n-1)+(n-2)+…+(1)=frac{n(n-1)}{2}。时间复杂度为：O(n^{2});
• 最好情况为有序递增，不需要交换，只进行遍历；最差情况为每次都进行交换；
• 每一次交换操作(可参考《3种交换值的方法》)要使用临时变量来保存，需要进行3次移动操作，最差进行3(n-1)次移动；
• 就地排序，空间复杂度为O(1)；
• 每次交换是选择出的元素与剩余序列中第一个序列进行交换，这个操作可能会导致排序结果不稳定。

简单选择排序演示

• 初始序列：{49,38,65,97,76,13,27,49}；
• 第一趟遍历选出最小的数字13，与49交换：13 {38,65,97,76,49,27,49}；
• 选出最小的27，13,27 {65,97,76,49,38,49}；
• 选出38，13,27,38 {97,76,49,65,49}；
• 这次选出的是靠左的49，默认选出最先遍历到的最小的元素，13,27,38,49 {76,97,65,49}；
• 选出49，13,27,38,49,49, {97,65,76}；
• 选择65，13,27,38,49,49,65, {97,76}；
• 选择76，13,27,38,49,49,65,76,97。

原文链接：简单选择排序(SELECT SORT)，转载请注明来源！