1插入排序编辑
2基本思想编辑
将n个元素的数列分为已有序和无序两个部分，如
下所示：
插入排序过程示例
{{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};
3设计步骤编辑
算法设计有很多方法。插入排序使用的是增量（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次插入处理，数列全部有序。
void insertSort(Type* arr,long len)/*InsertSort algorithm*/
{
long i=0,j=0;/*iterator value*/
Type tmpData;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=1;i<len;i++)
{
j=i;
tmpData=*(arr + i);
while(j > 0 && tmpData < arr[j-1])
{
arr[j]=arr[j-1];
j--;
}
arr[j]=tmpData;
}
}
思路
假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.
4描述编辑
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5
5实现编辑
伪代码
INSERTION-SORT(A)
1forj← 2tolength[A]
2dokey←A[j]
3 InsertA[j] into the sorted sequenceA[1..j-1].
4i←j-1
5whilei>0 andA[i] >key
6doA[i+1] ←A[i]
7i←i-1
8A[i+1] ←key
C语言
示例代码为C语言，输入参数中，需要排序的数组为array[]，起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从first到last处于升序排列。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
voidinsertion_sort(intarray[],intfirst,intlast){inti,j;inttemp;for(i=first+1;i<=last;i++){temp=array[i];j=i-1;//与已排序的数逐一比较，大于temp时，该数移后while((j>=first)&&(array[j]>temp)){array[j+1]=array[j];j--;}array[j+1]=temp;}} |
这个更好：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
voidinsert_sort(int*array,unsignedintn){inti,j;inttemp;for(i=1;i<n;i++){temp=*(array+i);for(j=i;j>0&&*(array+j-1)>temp;j--){*(array+j)=*(array+j-1);}*(array+j)=temp;}} |
这个是c++语言版本的插入排序。为了支持list使用了std::advance（）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<iterator>template<typenamebiIter>voidinsertion_sort(biIterbegin,biIterend){typedeftypenamestd::iterator_traits<biIter>::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;}} |
C++
#include "iostream"#include "string"using namespace std;//插入排序 time:O(n^2)template<typename T>void InsertionSort(T* arry,int size){int i,j;for(i=0;i<size;i++)//枚举每一个数字{ for(j=i;j>0&&arry[j-1]<arry[j];j--)//不断移动插入前面已经排好的数据 { swap(arry[j-1],arry[j]); }}return;}int
main(){int arry[10]={7,3,4,7,10,9,1,5,3,7};int i;InsertionSort(arry,10);for(i=0;i<10;i++){ cout<<arry[i]<<‘ ‘;}return 0;}php
function insert_sort2($array){ $count = count($array); for($i=1;$i<$count;$i++){ $temp=$array[$i]; //4 for($j=$i-1;$j>=0&&$temp<$array[$j];$j--){ $array[$j+1]=$array[$j]; } $array[$j+1]=$temp; } return $array; }JAVA
public void InsertSort(int[] a){ if(a!=null){ for(int i=1;i<a.length;i++){ int temp=a[i],j=i; if(j >= 1 &&a[j-1]>temp){ while(j>=1&&a[j-1]>temp){ a[j]=a[j-1]; j--; } a[j]=temp; } } }else{ System.out.print("array hasn‘t been inited!"); }}
1 #!/usr/bin/env python
2
3 def insert_sort(str):
4 tmplist = list(str)
5 count = len(tmplist)
6 for i in range(1,count):
7 temp = tmplist[i]
8 for j in range(1,i+1)[::-1]:
9 if(j > 0 and temp < tmplist[j - 1]):
10 tmplist[j] = tmplist[j - 1]
11 tmplist[j - 1] = temp
12 return tmplist
13
14 str = "acdiopqwe"
15 print(insert_sort(str))
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 := I - 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 //
AAuto
io.open();//打开控制台/**-------------------------------------------------------* 插入排序**------------------------------------------------------*///插入排序算法insert_sort = function(array){ for(right=2;#array){ var top = array[right]; //Insert array[right] into the sorted
seqquence array[1....right-1] var left = right -1; while(left and array[left]>top){ array[left+1] = array[left]; left--; } array[left+1] = top; } return array;}//插入排序算法 - 倒序insert_sort_desc = function(array){ for(right=2;#array) { var top = array[right]; //Insert
array[right] into the sorted seqquence array[1....right-1] var left = right -1; while(left and array[left]<top){ array[left+1] = array[left]; left--; } array[left+1] = top; } return array;}io.print("----------------")io.print("插入排序（原地排序）")io.print("----------------")array
={12;3;556;7;17788;23};insert_sort_desc(array)//输出结果for(i=1;#array;1){ io.print(array[i])}execute("pause") //按任意键继续io.close();//关闭控制台
C#
完整的代码，采用产生随机数，然后在利用插入排序重新排列。语言方式与C以及C++都有所不同，方法都是产用类的形式来表达。
class Program{class Carry{private int[] arr;private int numitems;private int upper;public Carry (int size) //构建数组{arr = new int[size];upper = size - 1;numitems = 0; ;}public void insert(int items)//向数组中添加数据{for (int i = 0; i < upper ; i++)arr[numitems] = items;numitems++;}public
void display()//打印数组{for (int i = 0; i < upper; i++)Console.Write(arr[i]+" ");}public void insert sort()//插入排序{for (int outer = 1; outer <= upper; outer++){int temp=arr[outer];int inner = outer ;while(inner>0&&(int)arr[inner-1] >= temp){arr[inner] = arr[inner
- 1];inner --;}arr[inner] = temp;}}}static void Main(string[] args){Carry arry = new Carry⑽；//初始化一个10个数据元素的数组Random rnd = new Random(100);//在1到100中随机产生10个数作为数组成员for (int i = 0; i < 10; i++){arry.insert(rnd.Next (0,100));}arry.insertsort ();//调用插入排序arry.display();//打印数组Console.ReadKey();}}Java代码
public class InsertSort {public static void main(String[] args) {insertSort(new int[]{8,2,4,9,3,6,7,10});}// 辅助函数public static void dumpArray(int[] a) {for (int index = 0; index < a.length; index++) {System.out.print(a[index] + " ");}System.out.println("");}public
static void insertSort(int[] a) {// 输出原始数组dumpArray(a);for (int index = 1; index < a.length; index++) {int subIndex = index;int currentData = a[index]; // 等待插入的数据while ((subIndex > 0) && (a[subIndex - 1] > currentData)) {a[subIndex] = a[subIndex - 1];subIndex--;a[subIndex]
= currentData; // 插入到合适的位置}// 每次排序后也输出dumpArray(a);}}}代码
（defun insert-sort (lt)
（do ((index 1 (1+ index)))
（（>= index (length lt)) nil)
（let ((temp (elt lt index)))
（do ((j 0 (1+ j)))
（（> j index))
（if (> (elt lt j) temp)
（progn
（do ((z index (1- z)))
（（<= z j))
（setf (elt lt z) (elt lt (- z 1))))
（setf (elt lt j) temp)
（return)))))))
（defun test-sort ()
（let ((lt (make-array 10 :fill-pointer 0)))
（dotimes (var 10)
（vector-push (random 10) lt))
（format t "~a~%" lt)
（insert-sort lt)
（format t "~a~%" lt)))
PHP版本
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
functioninsertSort($arr){for($i=1;$i<count($arr);$i++){$tmp=$arr[$i];$key=$i-1;while($key>=0&&$tmp<$arr[$key]){$arr[$key+1]=$arr[$key];$key--;}if(($key+1)!=$i)$arr[$key+1]=$tmp;}return$arr;} |
Java版本
根据C语言第一版进行的Java改写版本。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/***插入排序，排序方向：降序*@paramdata待排序的数据。*/publicstaticvoidinsertion_sort(Comparable[]data){intj=0;Comparablecomparable;for(inti=1;i<data.length;i++){comparable=data[i];j=i-1;while((j>=0)&&comparable.compareTo(data[j])>0){data[j+1]=data[j];j--;}data[j+1]=comparable;}} |
算法的时间复杂度
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
稳定性
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。