排序算法 - 插入排序(Insertion Sort)

by LauCyun Jul 25,2014 20:35:53 4,086 views

核心:通过构建有序序列,对于未排序序列,在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历),找到相应位置并插入。

一般来说,插入排序都采用in-place在数组上实现。具体算法描述(如图1所示)如下:

  1. 从第一个元素开始,该元素可认为已排序
  2. 取下一个元素,对已排序数组从后往前扫描
  3. 若从排序数组中取出的元素大于新元素,则移至下一位置
  4. 重复步骤3,直至找到已排序元素小于或等于新元素的位置
  5. 插入新元素至该位置
  6. 重复2~5

图1 Insertion Sort

如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找插入排序。

性质

  • 交换操作和数组中倒置的数量相同
  • 比较次数>=倒置数量,<=倒置的数量加上数组的大小减一
  • 每次交换都改变了两个顺序颠倒的元素的位置,即减少了一对倒置,倒置数量为0时即完成排序。
  • 每次交换对应着一次比较,且1到N-1之间的每个i都可能需要一次额外的记录(a[i]未到达数组左端时)
  • 最坏情况下需要~N^2/2次比较和~N^2/2次交换,最好情况下需要N-1次比较和0次交换。
  • 平均情况下需要~N^2/4次比较和~N^2/4次交换

 

1 算法实现

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

void InsertSort(ElemType *array);

void Show(ElemType *array);

void InsertSort(ElemType *array) {
    for (int i = 0; i < N; i++) {
        ElemType temp = array[i];
        int j = i;
        for (; j > 0 && array[j - 1] > temp; j--) {
            array[j] = array[j - 1];
        }
        array[j] = temp;
        cout << "i = " << i << " => ";
        Show(array);
    }
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main() {
    ElemType array[N] = {6, 5, 3, 1, 8, 7, 2, 4};
    Show(array);
    InsertSort(array);
    Show(array);
    return 0;
}

Python

#!/usr/bin/env python

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentvalue:
            alist[position] = alist[position - 1]
            position = position - 1

        alist[position] = currentvalue
    return alist


unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
print(insertionSort(unsorted_list))

 

2 算法过程演示

如果显示不好,请戳 这里

 

3 复杂度分析

如果目标是把\(n\)个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。

  • 最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需\((n-1)\)次即可。
  • 最坏情况就是,序列是降序排列,那么此时需要进行的比较共有\({\displaystyle {\frac {1}{2}}n(n-1)}\)次。
  • 插入排序的赋值操作是比较操作的次数加上\((n-1)\)次。平均来说插入排序算法复杂度为\({\displaystyle O(n^{2})}\)

因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。 

 

4 参考文档

(全文完)

Tags