[Day16] CH10：排序大家族——选择排序法

今天介绍的是第二种排序法是选择排序法（Selection Sort）。

选择排序法

将资料分成已排序与未排序，由未排序资料中找最小值，放入已排序资料最末端。由此可知，每一次我们有两件事要做，一是找到当前的最小值，二是把它放到已排序的最末端。

给定一个阵列：

41, 24, 97,  6, 19, 53, 78

一开始从未排序的 41 到 78 之间选出最小值 6，和最前面的 41 换位子。

 6, 24, 97, 41, 19, 53, 78

接下来从未排序的 24 到 78 中选出最小值 19，和 24 换位置。

 6, 19, 97, 41, 24, 53, 78

再来从未排序的 97 到 78 中间选出最小值 24，和 97 换位置。

 6, 19, 24, 41, 97, 53, 78

一直持续到最後两个数字交换完位子，便完成由小至大的排序，以下是动图与程序码：

public class SelectionSort {
    public static void main(String[] args){
        int[] arr = {41, 24, 97, 6, 19, 53, 78};
        int n = arr.length;
        for(int i = 0 ; i < n-1 ; i++){
            int min = i;
            for(int j = i+1 ; j < n ; j++){
                if(arr[min] > arr[j]){  //找最小值
                    min = j;
                }
            }
            int t = arr[i]; //两数交换
            arr[i] = arr[min];
            arr[min] = t;
        }
        for(int i = 0 ; i < n ; i++){
            System.out.printf("%d ", arr[i]);
        }
    }
}

时间复杂度

• 找到最小值

  首先要从 n 个未排序数字中找到最小值，需要 n 个步骤。

  最常见找最小值的方法：先设阵列的第一个数字是「目前的最小值」，再把阵列後面的数值一一读取。如果读取的数字比目前的最小值大，就不动。否则把目前的最小值换成这个数。重复这个方法把所有阵列里的数都读过一遍，就能找到整个数列的最小值。

  从上面的例子来看，第一次要从 7 个数中找到最小值，需要 7 个步骤，第二次 6 个...，直到最後一次 1 个，总共是 (n + (n - 1) + ... + 1) = n * (n + 1) / 2

• 放到最左边

  每次找到最小值，就和最左边的数俩俩交换，总共需要交换 n 次，共 n 个步骤。

两者加起来为 n * (n + 1) / 2 + n，所以时间复杂度为 O()，不管是最差、平均或最好都一样，因为每次都需要做所有的步骤。

今天的时间复杂度和昨天一样ㄟ，那哪一个比较快呢？明天会不会更快呢？让我们继续看下去