11月热门下载资源TOP100强力推荐！ 点击了解英特尔云计算
漫谈经典排序算法:二、各种插入排序解析及性能比较
分类： Data Structures And Algorithms2011-09-17 09:55700人阅读评论(0)收藏举报
1、序言
这是《漫谈经典排序算法系列》第二篇，解析了各种插入排序算法。主要包括：直接插入排序、折半插入排序、表插入排序、希尔插入排序。每一种算法的开头都叙述了引出该算法的原因，然后给出代码，最后分析算法效率及和其他插入排序相比，优劣在哪里。
各种排序算法的解析请参考如下：
《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》 《漫谈经典排序算法:二、各种插入排序解析及性能比较》 《漫谈经典排序算法:三、冒泡排序 && 快速排序》 《漫谈经典排序算法:四、归并排序》
《漫谈经典排序算法:五、线性时间排序(计数、基数、桶排序)》 《漫谈经典排序算法:六、各种排序算法总结》
注：为了叙述方便，本文以及源代码中均不考虑A[0],默认下标从1开始。
2、直接插入排序
2.1 引出
给定待排序序列A[ 1.....n ]，现假设A[1...i]已经有序，那么我们取出A[i+1]插入到序列A[1...i].这样有序序列记录数就增加了1.如此重复上述操作，不断取出记录插入有序序列，直到A[n]插入到有序序列，排序完成。
2.2 代码
view plaincopy to clipboardprint?
1. //直接插入排序
2. void straightInsertSort(int *a,int n) 3. { 4. int i,j; 5. int temp;
6. //逐个记录插入有序序列 7. for(i=2;i<=n;i++){ 8. temp=a[i];
9. //把a[i]插入有序序列
10. for(j=i-1;j>=1;j--){ 11. if(temp 16. a[j+1]=temp; 17. } 18. } //直接插入排序void straightInsertSort(int *a{int i,j;int temp;//逐个记录插入有序序列 2.3 效率分析 容易看出，要插入的记录个数为n-1，其中关键字的比较次数和记录移动次数是依赖于给出的待排序序列是否基本有序。在最佳情况下（待排序序列有序），比较次数和移动次数时间为o（1），所以时间复杂度为o（n）.在最坏情况下（待排序序列逆序）和平均时间均为o（n^2）.从上述分析中可以看出，直接插入排序适合记录数比较少、给定序列基本有序的情况。熟悉了排序过程我们发现，直接插入排序是一种稳定的原地排序算法。 3、折半插入排序 3.1 引出 在直接插入排序过程中，我们是把一个记录插入到有序序列中，至于要插入到有序序列中的哪个位置呢？采用的是顺序查找确定插入的位置。显然对于有序序列，折半查找的效率要高，所以在寻找插入位置时可以用折半查找。折半查找主要分为三步：1、查找要插入的位置 2、移位 3、把记录插入相应的位置。 3.2 代码 view plaincopy to clipboardprint? 1. //折半查找 2. int binarySearch(int *a,int low,int high,int key) 3. { 4. int mid=(low+high)/2; 5. if(low>high) 6. return low; 7. if(a[mid]==key) 8. return mid; 9. else if(key 10. return binarySearch(a,low,mid-1,key); 11. else 12. return binarySearch(a,mid+1,high,key); 13. } 14. 15. //折半插入排序 16. void binaryInsertSort(int *a,int n) 17. { 18. int i,j,site,temp; 19. for(i=2;i<=n;i++){ 20. //1.折半查找要插入的位置 21. site=binarySearch(a,1,i,a[i]); 22. temp=a[i]; 23. //2.移位 24. for(j=i;j>site;j--) 25. a[j]=a[j-1]; 26. //3.插入a[i] 27. a[site]=temp; 28. } 29. } //折半查找int binarySearch(int *a,int low{int mid=(low+high)/2;if(low>high)return low; 3.3 效率分析 折半插入排序是对直接插入排序的一种改进，这种改进只考虑了关键字比较次数，并没有减少移位次数，所以平均时间和最坏情况下（待排序序列逆序）时间复杂