普林斯頓大學算法公開課筆記——選擇排序

選擇排序（Selection sort）是一種簡單直覺的排序算法。它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。——維基百科

複雜度

簡單選擇排序的特點是交換移動次數很少（至多n-1次），其時間複雜度為 O(n²) （時間主要花在比較上，總的比較次數為N=(n-1)+(n-2)+...+1=n*(n-1)/2），與冒泡排序一樣，但性能上優于冒泡。

示例代碼

public class Selection
{
    public static void sort(Comparable[] a){
        int N = a.length;
        for (int i=0; i<N; i++){
            int min = i;
            for (int j=i+1; j<N; j++ )
                if(less(a[j], a[min]))
                    min = j;
            exch(a, i, min);
        }
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}