插入排序

记载

最早拥有排序概念的机器出现在1901至1904年间由Hollerith发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。
Hollerith在1896年创立的分类机公司的前身，为计算机制表记录公司（CTR）。他在计算机制表记录公司曾担任顾问工程师，直到1921年退休，而计算机制表记录公司在1924年正式改名为IBM。

概述

Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。
举例：
Input: {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有{5}。
拿起第二张牌2, 把 2 insert 到手上的牌{5}, 得到 {2 5}。
拿起第三张牌4, 把 4 insert 到手上的牌{2 5}, 得到 {2 4 5}。
以此类推。

C语言

1 void insertion_sort(int arr[], int len){ 2         int i,j,key; 3         for (i=1;i<len;i++){ 4                 key = arr[i]; 5                 j=i-1; 6                 while((j>=0) && (arr[j]>key)) { 7                         arr[j+1] = arr[j]; 8                         j--; 9                 }10                 arr[j+1] = key;11         }12 }

C++

1 void insertion_sort(int arr[],int len){ 2         for(int i=1;i<len;i++){ 3                 int key=arr[i]; 4                 int j=i-1; 5                 while((j>=0) && (key<arr[j])){ 6                         arr[j+1]=arr[j]; 7                         j--; 8                 } 9                 arr[j+1]=key;10         }11 }

C#

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

PASCAL

程序使用链表（linked list）做插入排序，目的：将读入的英文名字按字母排列
TYPElink=^node;node=record
      data:string;
      next:link;
     end;VARp,q,head,n:link;t,m:integer;f1,f2:text;i:string;BEGINassign(f1,'lianbiao-name-in.txt');reset(f1);assign(f2,'lianbiao-name-out.txt');rewrite(f2);head:=nil;read(f1,t);readln(f1);read(f1,i);new(p);p^.data:=i;p^.next:=nil;head:=p;readln(f1);read(f1,i);FOR m:=2 TO t DO
 BEGIN
  p:=head;
  new(n);
  n^.data:=i;
  while (i>p^.data) and (p^.next<>nil) do
   begin
    q:=p;
    p:=p^.next;
   end;
  if i<head^.data then begin
                        n^.next:=head;
                        head:=n;
                       end
                  else if (i>p^.data) and (p^.next=nil) then begin
                                                              p^.next:=n;
                                                              n^.next:=nil;
                                                             end
                                                        else begin
                                                              q^.next:=n;
                                                              n^.next:=p;
                                                             end;
  readln(f1);
  read(f1,i);
 end;p:=head;while p<>nil do
 begin
  write(f2,p^.data,' ');
  p:=p^.next;
 end;CLOSE(f1);CLOSE(f2);END.

Ruby

def insert_sort(lst)
  n = lst.size
  return lst if n == 1

  (1...n).each do |i|
    i.downto(1).each do |j|
      if lst[j] < lst[j-1]
        lst[j], lst[j-1] = lst[j-1], lst[j]
      else
        break
      end
    end
  end
  lstend

Ruby的另一个版本

def insertion_sort(lst)
  (1...lst.size).each do |i|
    temp = lst[i]
    j =  i - 1
    while j >= 0 and temp < lst[j]
      lst[j + 1] = lst[j]
      j -= 1
    end
    lst[j + 1] = temp
  end
  lstend

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]
            else:
                break
    return lst

Python的另一个版本

def insertion_sort(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 void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}

Java的另一个版本

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

JavaScript

1 Array.prototype.insertion_sort = function() 
 2 { 3   var i,j; 4   for(i = 1;i < this.length; i++){ 5     for(j = 0;j<i;j++){ 6       if(this[j]>this[i]){ 7         this.splice(j,0,this[i]); 8         this.splice(i+1,1); 9         break;10       }11     }12   }13   return this;14 };
用法示例：[3,5,2,11,1,2,"abc","zfd","sad","eng"].insertion_sort();

PHP

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

Rust

fn insert_sort<T>(list: &mut Vec<T>)    where T: PartialOrd + Copy{    let mut i = 0;    while i < list.len()-1 {        let mut j = i + 1;        while j > 0 {            if list[j] > list[j-1] {break;}            let temp = list[j-1];            list[j-1] = list[j];            list[j] = temp;            j -= 1;        }        i += 1;    }}
用法示例：
let mut a: Vec<i32> = vec![5,8,3,9,1,0];
insert_sort(&mut a);

Go

package mainimport (
"fmt")func InsertSort(array []int) {
n := len(array)
if n < 2 {
return
}
for i := 1; i < n; i++ {
for j := i - 1; j >= 0; j-- {
if array[j] > array[j+1] {
array[j], array[j+1] = array[j+1],array[j]
}else{
break
}
}
}}func main() {
array := []int{
55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,
}
fmt.Println(array)
InsertSort(array)
fmt.Println(array)}

Swift

//Swift 5.0func insertionSort(_ arr:[Int]) -> [Int] {
    if arr.count<=1 {return arr}
    var sortedArr = arr
    var tempInt:Int
    for i in 0..<arr.count {
        tempInt = sortedArr[i]
        for j in stride(from: i, to: -1, by: -1){
            if tempInt < sortedArr[j]{
                sortedArr.remove(at: j + 1)
                sortedArr.insert(tempInt, at: j)
            }
        }
    }
    return sortedArr}let array = [55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9]print(array)print(insertionSort(array))

算法复杂度

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