记载

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

算法描述

一般来说， 插入排序 都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

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

范例程式码

C语言

1 voidinsertion_sort(intarr[],intlen) 2 { 3 inti,j; 4 inttemp; 5 for(i=1;i=0&&arr[j]>temp;j--)12 {//j循环到-1时，由于[[短路求值]](/wiki/短路求值)，不会运算array[-1]13 arr[j+1]=arr[j];14 }15 arr[j+1]=temp;16 //被排序数放到正确的位置17 }18 }

C++

1 template//整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能 2 voidinsertion_sort(Tarr[],intlen){ 3 inti,j; 4 Ttemp; 5 for(i=1;i=0&&arr[j]>temp;j--) 9 arr[j+1]=arr[j];//最后一次执行该语句后，跳出当前for循环前，会再一次执行j--10 arr[j+1]=temp;//执行完上一个语句（即for语句）后，跳出的位置保存在j中，此时arr[j]的值是没有经过移动的，不能替换，应该替换的是arr[j+1]11 }12 }

C#

publicstaticvoidInsertSort(double[]data){inti,j;varcount=data.Length;for(i=1;i=0&&data[j]>t;j--)data[j+1]=data[j];data[j+1]=t;}}

PASCAL

程式使用 linked list 做插入排序，目的：将读入的英文名字按字母排列

TYPElink=^node;node=recorddata: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);FORm:=2TOtDOBEGINp:=head;new(n);n^.data:=i;while(i>p^.data)and(p^.nextnil)dobeginq:=p;p:=p^.next;end;ifip^.data)and(p^.next=nil)thenbeginp^.next:=n;n^.next:=nil;endelsebeginq^.next:=n;n^.next:=p;end;readln(f1);read(f1,i);end;p:=head;whilepnildobeginwrite(f2,p^.data," ");p:=p^.next;end;CLOSE(f1);CLOSE(f2);END.

Python

definsert_sort(lst):n=len(lst)ifn==1:returnlstforiinrange(1,n):forjinrange(i,0,-1):iflst[j]<lst[j-1]:lst[j],lst[j-1]=lst[j-1],lst[j]returnlst

Python的另一个版本

definsertion_sort(lst):iflen(lst)==1:returnlstforiinrange(1,len(lst)):temp=lst[i]j=i-1whilej>=0andtemp<lst[j]:lst[j+1]=lst[j]j-=1lst[j+1]=tempreturnlst

Java

publicstaticvoidinsertion_sort(int[]arr){for(inti=0;i0;j--){if(arr[j-1]<=arr[j])break;inttemp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}

Java的另一个版本

1 // 将arr[i] 插入到arr[0]...arr[i - 1]中 2 publicstaticvoidinsertion_sort(int[]arr) 3 { 4 for(inti=1;i=0&&arr[j]>temp;j--)10 {11 arr[j+1]=arr[j];12 }13 arr[j+1]=temp;14 }15 }

JavaScript

1 Array.prototype.insertion_sort=function() 2 { 3 vari,j; 4 for(i=1;i<this.length;i++){ 5 for(j=0;jthis[i]){ 7 this.splice(j,0,this[i]); 8 this.splice(i+1,1); 9 }10 }11 }12 returnthis;13 };

用法示例：[3,5,2,11,1,2,"abc","zfd","sad","eng"].insert_sort();

PHP

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

Rust

fninsert_sort(list: &mutVec)whereT: PartialOrd+Copy{letmuti=0;whilei0{iflist[j]>list[j-1]{break;}lettemp=list[j-1];list[j-1]=list[j];list[j]=temp;j-=1;}i+=1;}}

用法示例： let mut a: Vec = vec![5,8,3,9,1,0]; insert_sort(&mut a);

算法复杂度

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

参考文献

[97严] 严蔚敏，吴伟民，《数据结构C语言版》，清华大学出版社，1997年4月

[99殷] 殷人昆，陶永雷，谢若阳，盛绪华，《数据结构（用面向对象方法与C++描述）》，清华大学出版社，1999年7月

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。