算法之插入排序

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

选择排序

分类	数据结构	时间复杂度	最优时间复杂度	平均时间复杂度	空间复杂度
插入排序	数组	О(n²)	О(n)	О(n²)	总共О(n), 辅助空间 O(1)

使用插入排序为一列数字进行排序的过程

代码范例

C语言

void insertion_sort(int arr[], int len) {
    int i, j;
    int temp;
    for (i = 1; i < len; i++) {
    temp = arr[i]; 
    //與已排序的數逐一比較，大於temp時，該數向後移
    j = i - 1;  
    // 如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
    for (; j >= 0 && arr[j] > temp; j--) {
        //j循环到-1时，由于[[短路求值]](http://zh.wikipedia.org/wiki/短路求值)，不会运算array[-1]
        arr[j + 1] = arr[j];
    }
    arr[j + 1] = temp; 
    //被排序数放到正确的位置
   }
}

Python

def insert_sort(lst):
    n=len(lst)
    if n == 1: return lst
    for i in range(1, n):
        for j in range(i, 0, -1):
            if lst[j] < lst[j-1] : lst[j], lst[j-1] = lst[j-1], lst[j]
    return lst

Python的另一个版本

def insertion_sort(lst):
    if len(lst) == 1:
        return lst

    for i in range(1, len(lst)):
        temp = lst[i]
        j = i - 1
        while j >= 0 and temp < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = temp
    return lst

Java

public static void insertion_sort(int[] arr) {
    for(int i = 0; i < arr.length - 1; i++) {   
        for(int j = i+1; j > 0; j--) {
            if(arr[j-1] <= arr[j])
                break;
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

Java的另一个版本

// 将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
    for (int i = 1; i < arr.length; i++ ) {
        int temp = arr[i];
        int j = i - 1;  
        //如果将赋值放到下一行的for循环内, 会导致在第13行出现j未声明的错误
        for (; j >= 0 && arr[j] > temp; j-- ) {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}

JavaScript

Array.prototype.insertion_sort = function() {
    var i,j;
    for(i = 1;i < this.length; i++) {
        for(j = 0; j < i; j++){
            if(this[j] > this[i]) {
                this.splice(j, 0, this[i]);
                this.splice(i+1, 1);
            }
        }
    }
    return this;
};

PHP

function insertion_sort(&$arr) {
    //php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
    for ($i = 1; $i < count($arr); $i++) {
         $temp = $arr[$i];
         for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
         $arr[$j + 1] = $arr[$j];
         $arr[$j + 1] = $temp;
    }
}

复杂度分析

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为О(n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

参考：https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F