Articles

插入排序(Insertion Sort)

两本经典的算法书Introduction to Algorithms和The Algorithm Design Manual都将插入排序作为书中的第一个算法。我一直有个疑问,难道第一个排序算法不应该是冒泡排序吗?至少我初中学的第一个算法就是冒泡排序。但仔细想想,在学习冒泡排序之前我就会打牌了。会打牌的人都会插入排序,所以这两本经典的书将插入排序作为第一个算法也是可以理解的,因为插入排序与生活更接近,也更容易被理解。

但这两本书中提供的插入排序的代码却不完全相同,我们先来看看Introduction to Algorithms这本书中的伪代码是什么样的。

INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j] 
        // Insert A[j] into 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

这段代码与我们打牌时讲牌排序的方法基本是一样的,从第二张牌开始,逐渐将第j张牌插入到前面已经排好序的1 … j – 1张牌中去。插入之前,我们先将这张牌取出并保存到key中(拿在手中)。然后比较这张牌与前面那些牌的大小,将比这张牌大的牌都挪到后面去,以便空出位置。最后将这张牌插入到合适的位置。

而The Algorithm Design Manual中提供的代码却有少许不同。

insertion_sort(item s[], int n)
{
    int i,j; /* counters */
    for (i=1; i<n; i++) {
        j=i;
        while ((j>0) && (s[j] < s[j-1])) {
            swap(&s[j],&s[j-1]);
            j = j-1;
        }
    }
}

这段代码并没有将当前的牌保存在key中,而是将它不断的与前面一张比较,然后交换。所以,这个插入排序其实是不停的交换排序,不如Introduction to Algorithms这本书中的代码形象。

最后,提供一段我自己写的该算法的C++实现。

template <typename T>
void insertion_sort(T a[], int length)
{
    for (int i = 1; i < length; i++)
    {
        T key = a[i];

        // insert a[i] into a[0] ... a[i - 1]
        int j = i - 1;
        while ((j >= 0) && (a[j] > key))
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

插入排序算法在最坏情况下的时间复杂度是\( O(n^2) \),空间复杂度是\( O(1) \)。