• 要求
• 算法描述
• 算法实现
• 与冒泡排序比较

要求

• 能够用自己语言描述选择排序算法
• 能够比较选择排序与冒泡排序
• 理解非稳定排序与稳定排序

  算法描述

1. 将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集

2. 重复以上步骤，直到整个数组有序

   算法实现

   public static void selection(int[] a) {
   for (int i = 0; i < a.length - 1; i++) {
       // i 代表每轮选择最小元素要交换到的目标索引
       int s = i; // 代表最小元素的索引
       for (int j = s + 1; j < a.length; j++) {
           if (a[s] > a[j]) { // j 元素比 s 元素还要小, 更新 s
               s = j;
           }
       }
       if (s != i) {
           swap(a, s, i);
       }
       System.out.println(Arrays.toString(a));
   }
   }

   优化点：为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素

   与冒泡排序比较

3. 二者平均时间复杂度都是 $O(n^2)$

4. 选择排序一般要快于冒泡，因为其交换次数少
5. 但如果集合有序度高，冒泡优于选择
6. 冒泡属于稳定排序算法，而选择属于不稳定排序
   • 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序
   • 不稳定排序则反之