最近看数据结构时看到直接插入排序法，其基本思想是:将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表
下面是代码实现与测试
1 #include <iostream> 2 using namespace std; 3 void InsertSort(int *q,int L) 4 { 5 int i,j,temp; 6 for(i=1;i<L;i++) 7 { 8 temp=q[i]; 9 for(j=i-1;j>=0&&temp<q[j];--j)//扫描前面的i-1个数据，如果没有到头，并且插入的 10 q[j+1]=q[j];//值小于当前值，那么就进行交换，因为前面i-1个数据都已经排好序了 11 q[j+1]=temp;//所以只会交换一次就结束 12 } 13 } 14 int main() 15 { 16 int i=0; 17 int a[10]={1,3,2,9,4,6,5,8,0,7}; 18 cout<<"原始数据是："<<endl; 19 for(i=0;i<10;i++) 20 cout<<a[i]<<" "; 21 cout<<endl<<"直接插入排序后:"<<endl; 22 InsertSort(a,10); 23 for(i=0;i<10;i++) 24 cout<<a[i]<<" "; 25 cout<<endl; 26 getchar(); 27 }
以上是结果...
时间复杂度：
直接插入排序比冒泡和简单选择排序的性能虽然要好一些，但是最后起时间复杂度依然是O(n^2)