经典排序算法（三）--- 选择排序

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法原理

它的工作原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的序列进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

复杂度及稳定性

平均时间复杂度	最优时间复杂度	最坏时间复杂度	空间复杂度	稳定性
O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定

动画演示

视频演示

代码实现

1. python

   def select_sort(_list):
       length = len(_list)
       for i in range(length):
           min_num = i
           for j in range(i+1, length):
               if _list[min_num] >= _list[j]:
                   min_num = j
           if i == min_num:
               pass
           else:
               _list[min_num], _list[i] = _list[i], _list[min_num]
   
       return _list
   
   test_sort = [7, 2, 0, 4, 2, 5, 1, 20, 81, 14, 11, 12]
   print(select_sort(test_sort))
   
   # [0, 1, 2, 2, 4, 5, 7, 11, 12, 14, 20, 81]
   
              

2. java

   static int [] selectionSort(int[] listData){
      int min,temp;
      for (int i=0; i< listData.length; i++){
          min = i;
          for (int j=i+1;j<listData.length;j++){
              if(listData[min]>=listData[j]){
                  min = j;
              }
          }
          if(min==i){
              continue;
          }else {
              temp = listData[i];
              listData[i] = listData[min];
              listData[min] = temp;
          }
      }
      return listData;
   }
   // 查看输出，如果需要倒序，则将listData[min]>=listData[j]改为小于即可
   public static void main(String[] args) {
       int[] test = selectionSort(new int[]{2, 4,3,10,9, 1, 8, 5, 5});
       for (int i: test) {
           System.out.println(i);
       }
   }
   // [1, 2, 3, 4, 5, 5, 8, 9, 10]
              

算法优化

无