要求

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

    算法描述

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

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

    算法实现

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

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

    与冒泡排序比较

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

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