插入排序及其优化

概念：

插入排序算法的核心是，把一个原本序列分成有序区和无序区，然后通过比较和后移把无序区的元素插入有序区内。
把一个原本序列分成有序区和无序区，如下图所示：
image.png
然后通过不断的比较和后移把无序区的元素插入有序区内，为了更直观的展示这一过程，如下动画。插入排序

  1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）
  2. 从无序区中取出第一个元素，即a[i]，在有序区序列中从后向前扫描。
  3. 如果有序元素大于a[i]，将有序元素后移到下一位置。有序元原本的位置赋值为a[i]
  4. 重复步骤3，直到找到小于或者等于a[i]的有序元素.
  5. 重复步骤2~4，直到无序区元素为0。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun <T : Comparable<T>> MutableList<T>.insertSort(): MutableList<T> {
    for (i in 1 until size) {
        var j = i
        while (j > 0) {
            if (get(j) < get(j - 1)) {
                swap(j, j - 1)
                j--
            } else {
                break
            }
        }
    }
    return this
}

这个解法有个可以优化的点，就是它会不断的发生元素的交换，为此可以改进为当有序元素大于a[i],只将有序元素后移到下一位。然后重复这步骤，直到找到小于或等于a[i]的有序元素，再将a[i]插入到该有序元素的下一个位置中。

  1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）
  2. 从无序区中取出第一个元素，即a[i]，在有序区序列中从后向前扫描。
  3. 如果有序元素大于a[i]，将有序元素后移到下一位置。
  4. 重复步骤3，直到找到小于或者等于a[i]的有序元素，将a[i]插入到该有序元素的下一位置中。
  5. 重复步骤2~4，直到无序区元素为0。

优化插入排序
实现优化后的插入排序的直接插入排序(语言kotlin)，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 直接插入排序
 * 将原本序列分为有序区和无序区，然后通过比较和后移操作将无序区元素插入到有序区中
 */
fun <T : Comparable<T>> MutableList<T>.insertSort(): MutableList<T> {
    for (i in 1 until size) {
        var j = i - 1
        val temp = get(i)
        while (j >= 0 && temp < get(j)) {
            set(j + 1, get(j))
            j--
        }
        set(j + 1, temp)
    }
    return this
}

时间复杂度：
直接插入排序的耗时操作有：比较和后移赋值。
最好的情况：原有的序列是顺序，比较的次数是n-1次,后移赋值的操作是0次，时间复杂度即即O(n)
最坏的情况：原有的序列是降序，比较的次数是n*(n-1)/2次,后移赋值的操作次数比较的次数再加上n-1次。即O(n^2)

二分查找插入排序

概念：

二分查找插入排序的原理：是直接插入排序的一个变种，区别是：在有序区中查找新元素插入位置时，为了减少元素比较次数提高效率，采用二分查找算法进行插入位置的确定。
具体如下实现为升：假设数组为a[0…n]。

  1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n] 为无序区。（i从1开始）

  2. 从无序区中取出第一个元素，即a[i]，使用二分查找算法在有序区中查找要插入的位置索引j。

  3. 将a[j]到a[i-1]的元素后移，并将a[i]赋值给a[j]。

  4. 重复步骤2~3，直到无序区元素为0。

    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
    /**
     * 二分插入排序,是对直接插入排序的一个改进。
     * 因为在有序区找到一个插入的位置，可以使用二分查找，减少元素比较的次数提高效率
     */
    fun <T : Comparable<T>> MutableList<T>.binaryInsertSort(): MutableList<T> {
        for (i in 1 until size) {
            var j = i - 1
            val temp = get(i)
            val index = this.binarySearch(temp, fromIndex = 0, toIndex = j)
            while (j >= 0 && j > index) {
                set(j + 1, get(j))
                j--
            }
            set(index, temp)
        }
        return this
    }

    /**
     * 二分查找
     */
    fun <T : Comparable<T>> List<T>.binarySearch(
        element: T,
        fromIndex: Int = 0,
        toIndex: Int = size,
    ): Int {

        var low = fromIndex
        var high = toIndex - 1
        while (low <= high) {
            val mid = (low + high) / 2// safe from overflows
            val midVal = get(mid)
            if (midVal > element) {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
        return low
    }

  5. 时间复杂度：O(n^2)
    二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
    二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)所以，二分查找排序比较次数为：x=log2n
    二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

  6. 最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n)

  7. 最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)

  8. 渐进时间复杂度（平均时间复杂度）：O(n^2)

  9. 空间复杂度：O(1)
    从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

    希尔排序

    维基百科
    希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。

  • 如果一个较小的数据在已排好序的数组的末端，要让这个数据放到正确的位置。如果使用直接插入排序，需要进行n次的比较和交换才能。因为在插入排序中每次只能将数据移动一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 希尔排序也是对直接插入排序的优化，
 * 突破O(n^2)屏障
 *
 */
fun <T : Comparable<T>> MutableList<T>.shellSort(): MutableList<T> {
    var gap = size / 2
    while (gap > 0) {
        for (i in gap until size step 1) {
            val tmp = get(i)
            var j = i
            while (j >= gap && tmp < get(j - gap)) {
                set(j, get(j - gap))
                j -= gap
            }
            set(j, tmp)
        }
        gap /= 2
    }
    return this
}