插入排序

发表于 阅读次数： 本文字数： 930 阅读时长 ≈ 1 分钟

插入排序的平均时间复杂度是\(O(n^2)\),对于少量元素的排序，是个有效的算法

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌面上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。

插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或逆序数组进行排序要快得多。

伪代码

INSERTION-SORT(A) //对于数组A

1
2
3
4
5
6
7
8
for j = 2 to A.length
    key=A[i]
    //Insert A[j] to the sorted sequence A[1..j-1].
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

简单的实现

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
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int *A;
    int length, i, j, key;
    //输入要排序的数字个数

    scanf("%d", &length);
    A = (int*)malloc((length+1) * sizeof(int));
    //输入数字
    for (i = 1; i <= length; i++)
        scanf("%d", &A[i]);
    //排序
    for (j = 2; j <= length; j++)
    {
        key = A[j];
        i = j - 1;
        while (i > 0 && A[i] > key)
        {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }
    for (i = 1; i <= length; i++)
        printf("%d ", A[i]);
    free(A);//别忘了释放malloc来的空间
    return 0;
}

对插入排序做一些改进我们可以得到一种更高效的排序算法--希尔排序