插入排序的主要操作是插入，
其基本思想是：
每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。

插入类排序方法有以下两种：

• 直接插入排序
• 希尔排序

直接插入排序

void  insertSort (int  r[ ], int n){	
   for (i=2; i<=n; i++)   { 
       r[0]=r[i]; j=i-1;
       while (r[0]<r[j])       {  
           r[j+1]=r[j];	
	 j=j-1;	
        }
       r[j+1]=r[0];	
    }
}

空间复杂度O(1)

稳定性：稳定

希尔排序

改进的依据：
（1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；
（2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。

基本思想：

将整个待排序记录分割成若干个子序列，
在子序列内分别进行直接插入排序，
待整个序列中的记录基本有序时，对全体记录进行直接插入排序。
分割：

1. 减少待排序记录个数；
2. 使整个序列向基本有序发展。

如何分?

子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。

解决方法：

将相隔某个“增量”的记录组成一个子序列。

增量应如何取？

希尔最早提出的方法是d1=n/2，di+1=di/2。
在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。当搜索位置＜0，表示插入位置已找到。
在搜索过程中，记录后移也是跳跃d个位置。
在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。

void Shellsort(int r[],int n){
  for (d=n/2; d>=1; d=d/2){
     for (i=d+1; i<=n; i++) {
	     r[0]=r[i];           
	     j=i-d;                
	     while (j>0 && r[0]<r[j])
	     { 
          		r[j+d]=r[j]; 
	          j=j-d;          
	      }
	      r[j+d]=r[0]; 
	}
  }
}

希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。

最后

以上就是柔弱寒风为你收集整理的【数据结构】插入类排序直接插入排序希尔排序的全部内容，希望文章能够帮你解决【数据结构】插入类排序直接插入排序希尔排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。