插入排序

記載

最早擁有排序概念的機器出現在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個或以下）。