【初级排序算法】选择排序

选择排序
找到数组中最小的元素，然后将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素就自己和自己交换）。其次在剩下的元素中找到最小的元素，将它和数组的第二个元素交换。如此反复，直到数组的最后一个元素完成上述逻辑。此时，整个数组完成排序。

动态图

选择排序

Java代码实现

/**
* 选择排序
*/
public class Selection extends Sort {

    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            // 将a[i]和a[i+1..N]中最小的元素交换
            int min = i; // 最小元素索引s
            for (int j = i + 1; j < N; j++) {
                // (N-1) + (N -2) + ... + 2 + 1 ~ N^2/2次比较
                if (less(a[j], a[min])) {
                    min = j;
                }
            }
            // N次交换
            exch(a, i, min);
        }
    }

    public static void main(String[] args) {
        String[] a = {"1", "3", "2", "9", "4", "8"};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

算法分析

对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换。

外循环1=0时，内循环执行N-1次比较；i=2时，执行N-2次比较。以此类推，比较总次数：

N(compare) = (N-1) + (N -2) + ... + 2 + 1 ~ N^2/2

交换只在外循环执行，即内循环中找到最小的元素时，完成一次交换。

N(exchange) = N