直接插入和希尔排序

发表于 | 阅读量 次 | 分类于 |

前言

直接插入在本质上改良了之前的冒泡和选择排序，而希尔排序更是超越O（n^2)的传统排序的改良算法

直接插入排序

算法描述：直接插入排序就是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表
首先先定义数据结构

#define MAXSIZE 10
typedef struct{
int r[Maxsize+1]//用于存储要排序的数组，r[0]用作哨兵或者临时变量
int length; //记录顺序表的长度
}SqList;

接下来不妨以5个数模拟该算法执行过程

初始化为{0,5,3,4,6,2}
从第二个数开始往前比较，如3比5小，那么，3赋值给哨兵，5后移到3位置，哨兵赋值给5位置，此时变成
{3,3,5,4,6,2}；
继续循环，哨兵初始化为0,4比5小，4给哨兵，5后移至4，在比较哨兵与3大小，如果比3小，3后移，在插入到该位置，否则直接插到5位置，ok这就是该算法的核心，在合适的位置直接插入

码上有戏

下面在来看算法，一般理解算法的过程，就把自己当做计算机，自我调试，然后就会发现其中无穷的乐趣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>    
#include <string.h>
#include <ctype.h>      
#include <stdlib.h>   
#include <io.h>  
#include <math.h>  
#include <time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; 
#define MAXSIZE 10000  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
	int r[MAXSIZE+1];	/* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
	int length;			/* 用于记录顺序表的长度 */
}SqList;
void InsertSort(SqList *L)
{
	int i,j; //i用来控制外层循环，也就是r[i]中每个数，j用来控制r[i]与前面的数大小，并插到合适的位置
for(i=2;i<=L->length;i++){
   if(L->r[i]<L->r[i-1]) //要插的数比前一个数大
   {
   	L->r[0]=L->r[i];    //要插入的数先放到哨兵
   	 for(j=i-1;L->r[j]>L->r[0];j--) //依次比较插入的数前面的数，放到合适的位置
   	 	L->r[j+1]=L->r[j]; //记录后移
   	 L->r[j+1]=L->r[0];  //插入合适的位置
   }
}
}
void print(SqList L) //打印元素
{
	int i;
	for(i=1;i<L.length;i++)
		printf("%d,",L.r[i]);
	printf("%d",L.r[i]);
	printf("\n");
}
int main(){
	int i;
      int d[5]={5,3,4,6,2};
        SqList L;
          for(i=0;i<5;i++)
          	L.r[i+1]=d[i];
             L.r[0]=0;
             L.length=5;
            printf("直接插入排序:\n");
             InsertSort(&L);
              print(L);
return 0;
}

下面在看看它的时间复杂度，最好的情况就是{2,3,4,5,6}，也就是说其本身已经是一个有序的，很显然只需要L->r[i]与L->r[r-1]大小，所以此时时间复杂度为O(n);最坏的情况就是{6,5,4,3,2}，即2+3+。。+n为（n+2)(n-1)/2
所以最后根据平局原则，知道直接插入排序的时间复杂度为O(n^2);

希尔排序

基本有序
首先需要了解一下基本有序的概念，就是指小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，如{2,1,3,6,4,7,5,8,9}，但如{1,5,9,3,7,8,2,4,6}这种9在第三位，2在倒数第三位就不叫基本有序

希尔排序的关键就是将相隔某个”增量”的记录组成一个子序列，实现跳跃式的移动

初始一个数组{0,9,1,5,8,3,7,4,6,2}，其中0为哨兵
并且初始化增量为数组长度（哨兵不算），所以为9，并约定一个循环，当且仅当增量小于等于1退出循环，并且每次增量都执行增量=增量/3+1（也可以是其他增量原则），第一次就是4了
然后一个循环变量i从增量+1开始直到小于等于数组长度，然后比较该i值与i-增量值，也就是第一个值大小，后面就是直接插入算法思想了，有一点不一样，就是循环变量j控制不太一样

然后看看上述数组怎么比较的

第一次：i=增量+1=5开始，也就是3与9比较，明显满足3<9,然后交换（直接插入思想），依次7与1，不交换，4与5交换，6与8交换，2与9交换这里那个j条件也满足并且2<3在交换，ok得到一个交换后的数组
{2,1,4,6,3,7,5,8,9}可以发现经过第一轮后，该数组基本有序了
紧接着开始进行第二轮，即增量=增量/3+1=2，即从第三个2与4不交换，1与6不交换，4与3交换，6与7不交换，4与5不交换，7与8不交换，5与9不交换，即得到{2,1,3,6,4,7,5,,8,9};
最后一轮：增量为1,2与1交换，2与4不交换，然后依次比较，由于目前已经基本有序，所以交换的比较少，
最后得到{1,2,3,4,5,6,7,8,9}

码上有戏

通过上面的例子，大概就是希尔排序的模拟过程，可以发现增量值是一个很巧妙的地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void ShellSort(SqList *L)
{
  int i,j;
  int increment=L->length; //初始化增量为数组长度
  do{
    increment=increment/3+1; //增量序列
    for(i=increment+1;i<=L->length;i++) //从增量序列后一位开始
    {
      if(L->r[i]<L->r[i-increment]) //该位置与第一位比较，是否交换
      {
        L->r[0]=L->r[i]; //若交换，先放到哨兵位置
         for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment)
           L->r[j+increment]=L->r[j]; //记录后移
            L->r[j+increment]=L->r[0];//插入到正确位置
      }
    }
  }while(increment>1);
}
int main(){
	int i;
      int d[5]={5,3,4,6,2};
        SqList L;
          for(i=0;i<5;i++)
          	L.r[i+1]=d[i];
             L.r[0]=0;
             L.length=5;
            printf("希尔排序:\n");
           ShellSort(&L);
               print(L);
              print(L);
return 0;
}

可以发现希尔排序的关键就是增量的选择，而它的时间复杂度是O(n^(3/2)),显然比传统的算法O(n^2)时间复杂度要小很多

快乐源于分享，总结溢于提高

热评文章