直接插入排序

发表于 分类于 ， ， Waline： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

直接插入排序

写法1：查找插入位置 后移腾出位置 插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 直接插入排序，每次取下一个元素后。
 * 插入前面已经有序的序列中，并保证插入后依然有序。
 * 先查找待插入的位置，然后把该位置之后的其他元素后移一位。
 * 然后在放入插入的元素
 * 
 * @param data 待排序的数组
 */
public static void directSortInsertByFind(int[] data) {
    if (data == null)
        return;
    // 第0个元素已经有序，从第1个开始向前方已经有序的序列中插入
    for (int i = 1; i < data.length; i++) {
        // 缓存待插入的元素
        int toInsert = data[i], insertIndex;
        // 从前向后遍历，查找插入点
        for (insertIndex = 0; insertIndex <= i - 1; insertIndex++) {
            // 当遍历的元素大于待插入的元素时
            if (data[insertIndex] > toInsert)
                break;
        }
        // 后移插入点之后的元素
        for (int k = i; k > insertIndex; k--)
            data[k] = data[k - 1];
        // 待插入的元素，放入插入点之中
        data[insertIndex] = toInsert;
    }
}

写法2：插入末尾 向前冒泡

插入已排序序列的默认，然后使用冒泡法，来调整插入元素的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 直接插入排序
 * 每次取下一个元素，插入到前方已经有序的序列之中。
 * 该元素插入有序序列的末尾，然后使用冒泡法调整插入元素的位置。
 * 
 * @param data 待排序的数字
 */
public static void directSortInsertByMaoPao(int[] data) {
    // 输入合法性判断
    if (data == null)
        return;
    // 数组的第0个元素，必定有序，
    // 所以从第1个元素开始，向前方已排序序列中插入元素
    for (int i = 1; i < data.length; i++) {
        // 从当前元素开始 遍历 到数组开头
        for (int j = i; j > 0; j--) {
            // 把该元素冒泡到前面去
            // 如果遍历的元素比它前面的元素小的话
            if (data[j] < data[j - 1]) {
                // 把该元素换到前面去
                int t = data[j];
                data[j] = data[j - 1];
                data[j - 1] = t;
            } else {
                break;
            }
        }
    }
}

改进写法：二分查找来找插入位置

使用二分查找来查找待插入元素的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * 直接插入排序，每次取出一个元素，插入到前方已排序的序列中。
 * 使用折半查找来查找插入点。
 * 
 * @param data 待排序的数组
 */
public static void directSortInsertByHalfSearch(int[] data) {
    if (data == null)
        return;
    for (int i = 1; i < data.length; i++) {
        int key = data[i];
        // 使用折半查找，找出插入点
        int j = FindInsertIndexByHalfSearch(data, i - 1, key);
        // 把插入点之后的都后移一位
        for (int k = i; k > j; k--)
            data[k] = data[k - 1];
        // 把当前遍历的元素放到插入点之中
        data[j] = key;
    }
}

/**
 * 在数组的0~n的区间内进行折半查找，二分查找
 * 
 * @param data 需要查找的数组
 * @param n 需要在数组的那个位置之前查找,[0,n]
 * @param key 要查找的
 * @return
 */
private static int FindInsertIndexByHalfSearch(int[] data, int n, int key) {
    // if(data==null) return -1;
    int left = 0, right = n;
    // 在已经排好序的序列中查找插入点
    while (left <= right) {
        // 计算中间点的位置
        int mid = (left + right) / 2;
        // 如果中间点的位置与要查找的相等
        if (data[mid] == key) {
            // 返回位置
            return mid;
        }
        // 如果中间点的值比待查找的大
        if (data[mid] > key)
            // 下次到中间点的前方查找，把尾指针指向中间点的前一个位置
            right = mid - 1;
        // 如果中间点的值比待查找的小
        else
            // 下次到中间点的后方去查找，把左指针指向中间点的后一个位置
            left = mid + 1;
    }
    // 当已经排好序的序列中查找不到插入点时，说明这个数比最大的数大，
    // 则直接插入在已排序序列的末尾即可
    right++;
    return right;
}