排序选择何种算法取决于排序元素个数及已排序的程度以及所使用的存储设备
A[1..n]含n个元素的数组 个数n=length[A]
插入排序--适合少量元素的排序
for j<-- 2 to length[A]
do key<--A[j]
//将A[j]插入到排好序的序列A[1..j-1]
i<--j-1
while i>0 and A[i]>key
do A[i+1]<--A[i]
i<-- i-1
A[i-1]<--key
用c++源程序描述:
#include<iostream>
using namespace std;
int insertSort(int*array){
int key,i;
for(int j=1;j<6;++j){
key=array[j]; //将第二个开始的元素放入key
i=j-1;
while(i>=0&&array[i]>key){ //将大于key的元素至key原本所在位置的所有元素向后移动一个,并覆盖了key原来的位置
array[i+1]=array[i];
--i;
}
array[i+1]=key;//将key插入到array[i]的位置
}
return(0);
}
int main(){
int a[6]={11,65,53,78,38,63};
insertSort(a);
for(int i=0;i<6;++i)
cout<<a[i]<<'\t';
return(0);
}
该方法在算法设计中叫增量方法Incremental