0%

插入排序

发表于 分类于

文章字数：175,阅读全文大约需要1分钟

插入排序就是将数据依次和左边的数据比较，直到有一个位置是它存在的区间（大于左边的，小于右边的）。就插入，并开始下一个。直到全部插入左边。即右边按顺序取出数据放到左边合适的地方

时间复杂度 o(n) - o(n^2)
因为找到合适的位置就不再对比了，所以最好的情况是已经拍好，即每个都对比一次O(n)。最不好的情况是反向排序，每个都要对比O(n^2)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int value = arr[i];
        int j = 0;//插入的位置
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j+1] = arr[j];//移动数据
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入数据
    }
}