選擇排序
找到數(shù)組中最小的元素，然后將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素就是最小的元素就自己和自己交換）。其次在剩下的元素中找到最小的元素，將它和數(shù)組的第二個(gè)元素交換。如此反復(fù)，直到數(shù)組的最后一個(gè)元素完成上述邏輯。此時(shí)，整個(gè)數(shù)組完成排序。

動(dòng)態(tài)圖

選擇排序

Java代碼實(shí)現(xiàn)

/**
* 選擇排序
*/
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);
    }
}

算法分析

對(duì)于長(zhǎng)度為N的數(shù)組，選擇排序需要大約N^2/2次比較和N次交換。

外循環(huán)1=0時(shí)，內(nèi)循環(huán)執(zhí)行N-1次比較；i=2時(shí)，執(zhí)行N-2次比較。以此類推，比較總次數(shù)：

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

交換只在外循環(huán)執(zhí)行，即內(nèi)循環(huán)中找到最小的元素時(shí)，完成一次交換。

N(exchange) = N