插入排序（Insertion Sort）

插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 取出下一个元素（即要插入的元素），在已经排序的元素序列中从后向前扫描；
  • 如果已排序的元素大于要插入的元素，将该元素向后移动一位；
  • 重复步骤3，直到找到已排序的元素小于或者等于要插入的元素的位置；
  • 将要插入的元素插入到该位置后；
  • 重复步骤2~5。

动图演示

算法分析

最佳情况：T(n) = O(n)
最坏情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

代码实现

Java

Java 实现
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
import java.util.Arrays;

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                int index = i;
                while (index > 0 && temp < arr[index - 1]) {
                    arr[index] = arr[index - 1];
                    index--;
                }
                arr[index] = temp;
            }
            System.out.printf("排序第%2d次后数组为：%s\n", i + 1, Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        System.out.printf("原始数组：%s\n", Arrays.toString(arr));
        insertionSort(arr);
        System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
    }
}

Ptyhon

Ptyhon 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def insertion_sort(arr):
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            temp = arr[i]
            index = i
            while index > 0 and temp < arr[index - 1]:
                arr[index] = arr[index - 1]
                index -= 1
            arr[index] = temp
        print('排序第%2d次后数组为：%s' % (i + 1, arr))


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print('原始数组：', arr)
    insertion_sort(arr)
    print('排序后数组：', arr)

Go

Go 实现
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
package main

import (
    "fmt"
)

func InsertionSort(arr *[15]int) {
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i-1] {
            temp := arr[i] // 记录要插入的数
            index := i     // 记录要插入的位置
            for ; index > 0 && temp < arr[index-1]; index-- {
                arr[index] = arr[index-1]
            }
            arr[index] = temp
        }
        fmt.Printf("排序第%2d次后数组为：%v\n", i, *arr)
    }
}

func main() {
    arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
    fmt.Printf("原始数组：%v\n", arr)
    InsertionSort(&arr)
    fmt.Printf("排序后数组：%v\n", arr)
}