排序(2) 插入排序

发表于 | 分类于 | 阅读次数:

插入排序重复地将新的元素插入到一个排好序的子线性表中，直到整个线性表排好序。 遍历数组，遍历到i时，a0,a1,…,ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较是，原来靠后的还是排在后边，所以插入排序是稳定的。 当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。

插入排序

原理

遍历数组，遍历到i时，a0,a1,…,ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。
可见相等元素比较是，原来靠后的还是排在后边，所以插入排序是稳定的。
当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。

插入排序的一个重要的特点是，如果原始数据的大部分元素已经排序，那么插入排序的速度很快（因为需要移动的元素很少）。从这个事实我们可以想到，如果原始数据只有很少元素，那么排序的速度也很快。
－－希尔排序就是基于这两点对插入排序作出了改进。

算法描述

对数列{2, 9, 5, 4, 8, 1, 6}进行排序，可以自己模拟对未排序的数列{9, 5, 4, 8, 1, 6}插入排序，直到数列排好序。

这个算法可以描述为：

插入排序伪代码
1
2
3
for (int i = 1; i < arr.length; i++) {
    将arr[i]插入到已排好序的只线性表中，这样arr[0 ... i]也是排好序的
}

插入arr[i]到arr[0, …, i-1]中有下面的过程：
1.将arr[i]存储在一个名为currentElement的临时变量中；
2.如果arr[i - 1] > currentElement，就将arr[i - 1]移到arr[i]中；
3.如果arr[i - 2] > currentElement，就将arr[i - 2]移到arr[i - 1]中；
4.依此类推，直到arr[i - k] <= currentElement 或者 k > i(传递的是排好序的数列的第一个元素)， 将currentElement赋值给arr[i - k + 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
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 插入arr[i]到已经排好序的子线性表arr[0 ... i-1]中
            int currentElement = arr[i];
            int k;

            for (k = i - 1; k >= 0 && arr[k] > currentElement; k--) {
                arr[k+1] = arr[k];
            }

            //  插入当前元素到arr[k+1]中
            arr[k + 1] = currentElement;
        }
    }

    public static void main(String[] args) {
        int[] list = {2, 32, 3, 34, 45, 8, 89, 20, 23, -1};        
        insertionSort(list);
        
        for (int i: list)
            System.out.print(i + " ");
    }
}

内外层循环的作用：
外层循环（循环控制变量i）的迭代是为了获取已排好序的子线性表，其范围是arr[0] 到arr[i]。

内层循环（循环控制变量k）将arr[i]插入到arr[0]到arr[i-1]的子线性表。

复杂度和稳定性

时间复杂度（平均）： O(n^2)
时间复杂度（最坏）： O(n^2)
时间复杂度（最好）： O(n)

空间复杂度： O(1)

因为在有序部分元素和待插入元素相等的时候，可以将待插入的元素放在前面，所以插入排序是 稳定的。

0%