插入排序

相关术语

关键码

假设一个档案有n条记录{}，对应的关键码是{}，排序家就是将此n个记录按照关键码的大小递增（或递减）的次序排列起来，使这些记录由无序变为有序的一种操作。排序后的序列若为{}时，其对应的关键码值满足{}或{}。

若在待排序的记录中，存在两个或两个以上的关键码值相等的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的方法，否则是不稳定的方法。

内部排序和外部排序

根据排序过程中涉及的存储器不同，可以将排序方法分为两大类：一类是内部排序，指的是待排序的几率存放在计算机随机存储器中进行的排序过程；另一类的外部排序，指的是排序中要对外存储器进行访问的排序过程。

内部排序是排序的基础，在内部排序中，根据排序过程中所依据的原则可以将它们分为5类：插入排序、交换排序、选择排序、归併排序和基数排序；根据排序过程的时间複杂度来分，可以分为三类：简单排序、先进排序、基数排序。

评价排序算法优劣的标準主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应；另一个是执行算法所需要的附加存储单元的的多少。

分类

包括：直接插入排序，二分插入排序（又称折半插入排序），鍊表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。

直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

例如,已知待排序的一组记录是：

60,71,49,11,24,3,66

假设在排序过程中，前3个记录已按关键码值递增的次序重新排列，构成一个有序序列：

49,60,71

将待排序记录中的第4个记录（即11）插入上述有序序列，以得到一个新的含4个记录的有序序列。首先，应找到11的插入位置，再进行插入。可以将11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序，才能完成。

直接插入排序的算法思路：

（1） 设定监视哨r[0]，将待插入记录的值赋值给r[0]；

（2） 设定开始查找的位置j；

（3） 在数组中进行搜寻，搜寻中将第j个记录后移，直至r[0].key≥r[j].key为止；

（4） 将r[0]插入r[j+1]的位置上。

直接插入排序算法：

public void zjinsert (Redtype r[],int n)

{

int I,j;

Redtype temp;

for (i=1;i

{

temp = r[i];

j=i-1;

while (j>-1 &&temp.key

{

r[j+1]=r[j];

j--;

}

r[j+1]=temp;

}

}

折半插入排序（二分插入排序）

将直接插入排序中寻找A[i]的插入位置的方法改为採用折半比较，即可得到折半插入排序算法。在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。所谓折半比较，就是在插入A[i]时，取A[i-1/2]的关键码值与A[i]的关键码值进行比较，如果A[i]的关键码值小于A[i-1/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，故可以在A[0]到A[i-1/2-1]之间继续使用折半比较；否则只能插入A[i-1/2]到A[i-1]之间，故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间採用折半，其中间结点为A[k+r/2]，经过一次比较即可排除一半记录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是档案记录必须按顺序存储。

折半插入排序的算法思想：

算法的基本过程：

（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；

（2）在相应的半个範围里面找插入的位置时，不断的用（1）步骤缩小範围，不停的折半，範围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；

（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

3 希尔排序法

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序档案中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重複上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

各组内的排序通常採用直接插入法。由于开始时s的取值较大，每组内记录数较少，所以排序比较快。随着不断增大，每组内的记录数逐步增多，但由于已经按排好序，因此排序速度也比较快。

原理

{{a1}，{a2，a3，a4，…，an}}

{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

假设在一个无序的数组中，要将该数组中的数按插入排序的方法从小到大排序。假设啊a[]={3,5,2,1,4};插入排序的思想就是比大小，满足条件交换位置，一开始会像冒泡排序一样，但会比冒泡多一步就是交换后（a[i]=a[i+1]后）原位置（a[i]）会继续和前面的数比较满足条件交换，直到a[i+1]前面的数组是有序的。比如在第二次比较后数组变成a[]={2,3,5,1,4};

设计步骤

算法设计有很多方法。插入排序使用的是增量（incremental）方法；在排好子数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；

步骤

⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；

⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；

⒊重複第二步，共进行n-i次插入处理，数列全部有序。

思路

假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.

描述

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

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

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

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

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

⒌ 将新元素插入到下一位置中

⒍ 重複步骤2~5

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

实现

伪代码

INSERTION-SORT(A)

1forj=2tolength[A]

2dokey=A[j]

3 //InsertA[j] into the sorted sequenceA[1..j-1].

4 i=j-1

5 whilei>0 andA[i] >key

6 doA[i+1] =A[i]

7 i=i-1

8 A[i+1] =key

C语言

示例代码为C语言，输入参数中，需要排序的数组为array[ ]，起始索引为first（数组有序部分最后一个的下标，或者直接标 0），终止索引为last（数组元素的最后一个的下标）。示例代码的函式採用insert-place排序，调用完成后，array[]中从first到last处于升序排列。

voidinsertion_sort(intarray[],intfirst,intlast){inti,j;inttemp;for(i=first+1;i=0)&&(array[j]>temp)){array[j+1]=array[j];j--;}//存在大于temp的数if(j!=i-1)array[j+1]=temp;}}

这个更好：

voidinsert_sort(int*array,unsignedintn){inti,j;inttemp;for(i=1;i0&&*(array+j-1)>temp;j--){*(array+j)=*(array+j-1);}*(array+j)=temp;}}

c++版本

#includetemplatevoidinsertion_sort(biIterbegin,biIterend){typedeftypenamestd::iterator_traits::value_typevalue_type;biIterbond=begin;std::advance(bond,1);for(;bond!=end;std::advance(bond,1)){value_typekey=*bond;biIterins=bond;biIterpre=ins;std::advance(pre,-1);while(ins!=begin&&*pre>key){*ins=*pre;std::advance(ins,-1);std::advance(pre,-1);}*ins=key;}}

PHP版本

functioninsertSort($arr){for($i=1;$i=0&&$tmp<$arr[$key]){$arr[$key+1]=$arr[$key];$key--;}if(($key+1)!=$i)$arr[$key+1]=$tmp;}return$arr;}

Java版本

/***插入排序*@paramarr*@return*/privatestaticint[]insertSort(int[]arr){if(arr==null||arr.length<2){returnarr;}for(inti=1;i0;j--){if(arr[j]0;j--){if(arr[j]
运行软体：eclipse
JavaScript版本
//测试数组vararr=newArray(1,3,2,8,9,1,5);//插入排序functionInsertionSort(arr){if(arr==null||arr.length<2){returnarr;}for(leti=1;i=0&&arr[j]>arr[j+1];j--){lettemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}returnarr;}//控制台输出console.log(arr);InsertionSort(arr);console.log(arr);
 
C#版本
classProgram{staticvoidMain(string[]args){InsertionSort();}///
///插入排序法///
privatestaticvoidInsertionSort(){Console.WriteLine(插入排序法);inttemp=0;int[]arr={23,44,66,76,98,11,3,9,7};Console.WriteLine(排序前的数组：);foreach(intiteminarr){Console.Write(item+,);}Console.WriteLine();varlength=arr.Length;for(inti=1;i0;j--){if(arr[j]>arr[j-1]){temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}//每次排序后数组PrintResult(arr);}Console.ReadKey();}///
///列印结果///
///privatestaticvoidPrintResult(IEnumerablearr){foreach(intiteminarr){Console.Write(item+,);}Console.WriteLine();}}
Pascal版本
procedure insertsort(var R:filetype);
//对R[1..N]按递增序进行插入排序，R[0]是监视哨
begin
for I := 2 To n do //依次插入R[2],...,R[n]
begin
R[0]:=R[I];j:=l-1;
while R[0] < R[J] Do //查找R[I]的插入位置
begin
R[j+1]:=R[j]; //将大于R[I]的元素后移
j:=j-1;
end;
R[j+1]:=R[0] ; //插入R[I]
end;
 
end; //InsertSort
(运行软体：Free Pascal IDE 2.6.4)
Ruby版本
definsertion_sort(array)array.each_with_indexdo|element,index|nextifindex==0#第一个元素默认已排序j=index-1whilej>=0&&array[j]>elementarray[j+1]=array[j]j-=1endarray[j+1]=elementendarrayend
Scala版本
definsertSort(ilist:Array[Int]){for(i<-1untililist.length){for(j<-(0untili).reverse){if(ilist(j+1)
python版本
importrandomRange=100Length=5list=random.sample(range(Range),Length)#在指定序列中随机获取指定长度片段print('beforesort:',list)foriinrange(1,Length):#默认第一个元素已经在有序序列中，从后面元素开始插入forjinrange(i,0,-1):#逆向遍历比较，交换位置实现插入iflist[j]
算法複杂度
如果目标是把n个元素的序列升序排列，那么採用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间複杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序套用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
稳定性
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。