
_START_ARTICLE_
插入排序
_START_SECTION_
记载
_START_PARAGRAPH_
最早拥有排序概念的机器出现在1901至1904年间由Hollerith发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。_NEWLINE_Hollerith在1896年创立的分类机公司的前身，为计算机制表记录公司（CTR）。他在计算机制表记录公司曾担任顾问工程师，直到1921年退休，而计算机制表记录公司在1924年正式改名为IBM。
_START_SECTION_
概述
_START_PARAGRAPH_
Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。_NEWLINE_举例：_NEWLINE_Input: {5 2 4 6 1 3}。_NEWLINE_首先拿起第一张牌, 手上有{5}。_NEWLINE_拿起第二张牌2, 把 2 insert 到手上的牌{5}, 得到 {2 5}。_NEWLINE_拿起第三张牌4, 把 4 insert 到手上的牌{2 5}, 得到 {2 4 5}。_NEWLINE_以此类推。
_START_SECTION_
C语言
_START_PARAGRAPH_
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 }
_START_SECTION_
C++
_START_PARAGRAPH_
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 }
_START_SECTION_
C#
_START_PARAGRAPH_
public static void InsertSort(int[] array){_NEWLINE_    for(int i = 1;i < array.length;i++)_NEWLINE_    {_NEWLINE_        int temp = array[i];_NEWLINE_        for(int j = i - 1;j >= 0;j--)_NEWLINE_        {_NEWLINE_            if(array[j] > temp)_NEWLINE_            {_NEWLINE_                array[j + 1] = array[j];_NEWLINE_                array[j] = temp;_NEWLINE_            }_NEWLINE_            else_NEWLINE_                break;_NEWLINE_        }_NEWLINE_    }}
_START_SECTION_
PASCAL
_START_PARAGRAPH_
程序使用链表（linked list）做插入排序，目的：将读入的英文名字按字母排列_NEWLINE_TYPElink=^node;node=record_NEWLINE_      data:string;_NEWLINE_      next:link;_NEWLINE_     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_NEWLINE_ BEGIN_NEWLINE_  p:=head;_NEWLINE_  new(n);_NEWLINE_  n^.data:=i;_NEWLINE_  while (i>p^.data) and (p^.next<>nil) do_NEWLINE_   begin_NEWLINE_    q:=p;_NEWLINE_    p:=p^.next;_NEWLINE_   end;_NEWLINE_  if i<head^.data then begin_NEWLINE_                        n^.next:=head;_NEWLINE_                        head:=n;_NEWLINE_                       end_NEWLINE_                  else if (i>p^.data) and (p^.next=nil) then begin_NEWLINE_                                                              p^.next:=n;_NEWLINE_                                                              n^.next:=nil;_NEWLINE_                                                             end_NEWLINE_                                                        else begin_NEWLINE_                                                              q^.next:=n;_NEWLINE_                                                              n^.next:=p;_NEWLINE_                                                             end;_NEWLINE_  readln(f1);_NEWLINE_  read(f1,i);_NEWLINE_ end;p:=head;while p<>nil do_NEWLINE_ begin_NEWLINE_  write(f2,p^.data,' ');_NEWLINE_  p:=p^.next;_NEWLINE_ end;CLOSE(f1);CLOSE(f2);END.
_START_SECTION_
Ruby
_START_PARAGRAPH_
def insert_sort(lst)_NEWLINE_  n = lst.size_NEWLINE_  return lst if n == 1_NEWLINE__NEWLINE_  (1...n).each do |i|_NEWLINE_    i.downto(1).each do |j|_NEWLINE_      if lst[j] < lst[j-1]_NEWLINE_        lst[j], lst[j-1] = lst[j-1], lst[j]_NEWLINE_      else_NEWLINE_        break_NEWLINE_      end_NEWLINE_    end_NEWLINE_  end_NEWLINE_  lstend
_START_SECTION_
Ruby的另一个版本
_START_PARAGRAPH_
def insertion_sort(lst)_NEWLINE_  (1...lst.size).each do |i|_NEWLINE_    temp = lst[i]_NEWLINE_    j =  i - 1_NEWLINE_    while j >= 0 and temp < lst[j]_NEWLINE_      lst[j + 1] = lst[j]_NEWLINE_      j -= 1_NEWLINE_    end_NEWLINE_    lst[j + 1] = temp_NEWLINE_  end_NEWLINE_  lstend
_START_SECTION_
Python
_START_PARAGRAPH_
def insert_sort(lst):_NEWLINE_    n=len(lst)_NEWLINE_    if n==1: return lst_NEWLINE_    for i in range(1,n):_NEWLINE_        for j in range(i,0,-1):_NEWLINE_            if lst[j]<lst[j-1]: _NEWLINE_                lst[j],lst[j-1]=lst[j-1],lst[j]_NEWLINE_            else:_NEWLINE_                break_NEWLINE_    return lst
_START_SECTION_
Python的另一个版本
_START_PARAGRAPH_
def insertion_sort(lst):_NEWLINE_    for i in range(1, len(lst)):_NEWLINE_        temp = lst[i]_NEWLINE_        j = i - 1_NEWLINE_        while j >= 0 and temp < lst[j]:_NEWLINE_            lst[j + 1] = lst[j]_NEWLINE_            j -= 1_NEWLINE_        lst[j + 1] = temp_NEWLINE_    return lst
_START_SECTION_
Java
_START_PARAGRAPH_
public void insertionSort(int[] array) {_NEWLINE_for (int i = 1; i < array.length; i++) {_NEWLINE_int key = array[i];_NEWLINE_int j = i - 1;_NEWLINE_while (j >= 0 && array[j] > key) {_NEWLINE_array[j + 1] = array[j];_NEWLINE_j--;_NEWLINE_}_NEWLINE_array[j + 1] = key;_NEWLINE_}_NEWLINE_}
_START_SECTION_
Java的另一个版本
_START_PARAGRAPH_
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;  _NEWLINE_ 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 }
_START_SECTION_
JavaScript
_START_PARAGRAPH_
1 Array.prototype.insertion_sort = function() _NEWLINE_ 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 };_NEWLINE_用法示例：[3,5,2,11,1,2,"abc","zfd","sad","eng"].insertion_sort();
_START_SECTION_
PHP
_START_PARAGRAPH_
function insertion_sort(&$arr) _NEWLINE_{_NEWLINE_    //php的陣列視為基本型別，所以必須用傳參考才能修改原陣列_NEWLINE_    for ($i = 1; $i < count($arr); $i++) _NEWLINE_    {_NEWLINE_        if ($arr[$i-1] > $arr[$i]) {_NEWLINE_            $temp = $arr[$i];_NEWLINE_            for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)_NEWLINE_                $arr[$j + 1] = $arr[$j];_NEWLINE_            $arr[$j + 1] = $temp;_NEWLINE_        }_NEWLINE_    }}
_START_SECTION_
Rust
_START_PARAGRAPH_
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;    }}_NEWLINE_用法示例：_NEWLINE_let mut a: Vec<i32> = vec![5,8,3,9,1,0];_NEWLINE_insert_sort(&mut a);
_START_SECTION_
Go
_START_PARAGRAPH_
package mainimport (_NEWLINE_"fmt")func InsertSort(array []int) {_NEWLINE_n := len(array)_NEWLINE_if n < 2 {_NEWLINE_return_NEWLINE_}_NEWLINE_for i := 1; i < n; i++ {_NEWLINE_for j := i - 1; j >= 0; j-- {_NEWLINE_if array[j] > array[j+1] {_NEWLINE_array[j], array[j+1] = array[j+1],array[j]_NEWLINE_}else{_NEWLINE_break_NEWLINE_}_NEWLINE_}_NEWLINE_}}func main() {_NEWLINE_array := []int{_NEWLINE_55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,_NEWLINE_}_NEWLINE_fmt.Println(array)_NEWLINE_InsertSort(array)_NEWLINE_fmt.Println(array)}
_START_SECTION_
Swift
_START_PARAGRAPH_
//Swift 5.0func insertionSort(_ arr:[Int]) -> [Int] {_NEWLINE_    if arr.count<=1 {return arr}_NEWLINE_    var sortedArr = arr_NEWLINE_    var tempInt:Int_NEWLINE_    for i in 0..<arr.count {_NEWLINE_        tempInt = sortedArr[i]_NEWLINE_        for j in stride(from: i, to: -1, by: -1){_NEWLINE_            if tempInt < sortedArr[j]{_NEWLINE_                sortedArr.remove(at: j + 1)_NEWLINE_                sortedArr.insert(tempInt, at: j)_NEWLINE_            }_NEWLINE_        }_NEWLINE_    }_NEWLINE_    return sortedArr}let array = [55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9]print(array)print(insertionSort(array))
_START_SECTION_
算法复杂度
_START_PARAGRAPH_
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有次。插入排序的赋值操作是比较操作的次数减去次，（因为次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。_NEWLINE_插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。