插入排序

基本思想

插入排序的基本思想:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置p，原来p后的元素一一向右移动一个位置,使得L[1..i]又是排好序的序列。(证明方法:循环不变式)

时间复杂度

插入排序的时间复杂度：O(n^2)

算法实例

例:输入序列数据按非减顺序输出。
pascal程序：

program crpx;
const n=7;
var a:array[0..n] of integer;
    i,j,k,t:integer;
begin
 write('Enter data:');
 for i:= 1 to n do read(a[i]);
 writeln;
 for i:=2 to n do
  begin
   k:=a[i];j:=i-1;
   while (k<a[j]) and (j>0) do
    begin a[j+1]:=a[j];j:=j-1 end;
   a[j+1]:=k;
  end;
 write('output data:');
 for i:= 1 to n do write(a[i]:6);
 writeln;
 end.

插入排序是一个小作品，欢迎帮助扩充这个条目。

C++程序：

# include <iostream>
# include <cstdio>
using namespace std;
 
int n;
int a[10];
 
void I_sort()
{
	for (int i=2;i<=n;++i)
	{
		a[0] = a[i];
		int j = i-1;
		while (j>=1 && a[j]>a[0])
		{
			a[j+1] = a[j];
			--j;
		}
		a[j+1] = a[0];
	}
}
 
int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
		cin>>a[i];
 
	I_sort();
 
	for (int i=1;i<=n;++i)
		cout<<a[i]<<' ';
 
	return 0;
}

插入排序是一个小作品，欢迎帮助扩充这个条目。

py版本示例： s=[14,45,34,15,98,12,68] for i in range(6):

   for j in range((i+1),7):
       if(s[i]>s[j]):
           t=s[j]
           s[j]=s[i]
           s[i]=t

print s