首页 > 代码库 > 普林斯顿公开课 算法2-2:选择排序

普林斯顿公开课 算法2-2:选择排序

选择排序就是对数组进行扫描,每次扫描找出最小的元素,并将其提到元素的前面。


动图

http://www.sorting-algorithms.com/animation/20/random-initial-order/selection-sort.gif

技术分享


代码


public class Selection {
    public static void sort(Comparable[] li) {
        for(int i = 0; i < li.length; i++) {
            int min = i;
            for(int j = i+1; j < li.length; j++) {
                if(SortUtil.less(li[j], li[min])) {
                    min = j;
                }
            }
            SortUtil.exch(li, min, i);
        }
    }
}


第6行:注意j=i+1。由于已经将i赋值给min了。不是必需再将li[i]与li[j]比較。


命题

选择排序使用了约N^2/2次比較。使用了N次交换。


长处

排序算法的执行时间和输入无关,都是N^2复杂度。

数据的交换次数是最少的,都是N次交换。

普林斯顿公开课 算法2-2:选择排序