数据结构与算法(19): 排序- 插入排序

发表于   |   分类于

  插入排序的基本思想：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
  时间复杂度：O($N^{2}$)。
  插入排序是稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    /**
     * 插入排序：从大到小
     */
    public class InsertSort extends Sort {
    public static void sort(int[] a){
        for (int i = 1; i < a.length; i++){
            for (int j = i; j > 0; j--){
                if (a[j] > a[j-1]){
                    swap(a, j, j-1);
                }
            }
            System.out.println("------第"+i+"趟-------");
            print(a);
        }
    }
}

感谢:http://www.cnblogs.com/skywang12345/p/3596881.html