本文共 739 字，大约阅读时间需要 2 分钟。

插入排序法

选择一个数字，放到该放的位置

插人排序法(insertion sort)的基本思想是把新插入记录的关键码与已排好序的各记录关键码逐个比较,当找到第一个比新记录关键码大的记录时,该记录之前即为插入位置k。然后从序列最后一个记录开始到该记录,逐个后移一个单元,将新记录插入k位置。如果新记录关键码比序列中所有的记录都大,则插入到最后位置。 设有A[1]~A[n]的n个数据v插入排序的过程可以描述为: ①已排序列首先为A[1].(一个数字一定是有序的)； ②然后将A[2]~A[n]逐个插人序列中,进行第à趟排序。将A[i门与 A[1]~A[i一1]，的关键码进行比较,若找到A[k]比 A[i]大,则A[i一1]~A[k]逐个后移一个单元,将A[i]插人到k位置;若A[i]比所有元素都大,则什么也不做。重复进行n-1趟后﹐整个排序过程结束。

图例：

#include 
   
    #include 
    
     #include
     
      using namespace std;#define N 10void sort(int A[],int n){
   	int t,i,j,k;	for(i=1;i
      
       t){
   				A[k+1]=A[k];k--;				if(k==-1)break;							}			A[k+1]=t;			}	}int main(){
   	int A[N],i;	srand((unsigned int )time(0));	for(i=0;i
      
     
    
   

结果图示：

改进：在查找插入位置时候，可以采用二分查找方法。 复杂度：0（n²） 稳定性：稳定

转载地址：http://yjexi.baihongyu.com/