02 April 2013

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

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

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

  • 第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),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;