【排序算法】插入排序

	本篇博客的主要内容是插入排序。常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希尔排序。这里介绍两个,直接插入排序和希尔排序。
	在介绍排序算法时,我将从基本思想、实例讲解、代码理解三个方面整理。
	【直接插入排序】
	1.基本思想
	直接插入排序(Straight Insertion Sorting)的基本思想是一次将每个记录插入到一个已排好序的有序表中去,从而得到一个新的、记录数增加1的有序表。
	2.具体做法
	我们把第一个序列元素看成是已经排好序的一个记录,后面的元素依次与已排好序的序列中的最后一个元素进行比较。
	3.实例讲解
	给序列{23,21,44,35,67,11,87,54}进行排序。
	下面是具体比较过程:
	21与23比较,序列更新为{21,23,44,35,67,11,87,54}
	44与23比较,序列更新为{21,23,44,35,67,11,87,54}
        35与44比较,序列更新为{21,23,35,44,67,11,87,54}
        67与44比较,序列更新为{21,23,35,44,67,11,87,54}
        11与67、44、35、23、21比较,序列更新为{11,21,23,35,44,67,87,54}
        87与67比较,序列更新为{11,21,23,35,44,67,87,54}
        54与87、67、44比较,序列更新为{11,21,23,35,44,54,67,87}
        4.代码理解
        看着上面的过程,对于直接插入排序的基本思想也得到了实践证明,心里上似乎明白了这样一种排序方法。但实际上,对于下面的代码,还需要好好理解一番。
        直接插入排序算法描述如下:
void StraightInsertSorting(List R,int n)   //直接插入排序,定义集合R,序列元素个数n
    {    int i,j;                              //定义整数i、j
         for (i=2;i<=n;i++)                    //i=2,从第二个数开始,与前面的数进行比较,直到最后一个
         {    R[0]=R[i];                       //将要“进行比较的数”赋值给哨岗R[0]
              j=i-1;                           //找到要进行比较的“前一个数”
              while(R[0].key<R[j].key)         //当“前一个数”的值大于哨岗的值
              {    R[j+1]=R[j];                //则将“前一个数”与该数位置交换
                   j--;                        //再继续与前面的数进行比较,直至可以确定该数的位置
              }
              R[j+1]=R[0];                     //否则两个数位置不变
          }
    }
	【希尔排序】
	希尔排序,又叫“缩小增量排序”。
	1.基本思想
        先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
        从上述基本思想中可以看出希尔排序与直接插入排序有着紧密联系,希尔排序也是在确立分组后在组内进行一次次的直接插入排序。
        2.具体做法
        我们需要先确定此个序列的增量序列。先取一个小于序列个数n的整数d1作为第一个增量,把记录分成d1个组,在组内进行直接出入排序,然后取第二个增量d2,重复上述分组和排序工作,直至所取的增量d1=1,即所有的记录放在同一组进行直接插入排序为止。
        (一般初次取序列一半为增量,然后每次减半,直到增量为1。)
        3.实例讲解
        给{48,37,64,96,75,12,26,54}进行排序。
        在这里,先确定增量序列为“4,2,1”,具体过程如下:
        第一次分组:{48,75}{37,12}{64,26}{96,54}
        
        序列更新为{48,12,26,54,75,37,64,96}
    第二次分组:{48,26,75,64}{12,54,37,96}
【排序算法】插入排序
    序列更新为{26,48,64,75,12,37,54,96}
    第三次挨个进行直接插入排序:
序列更新为{12,26,37,48,54,64,75,96}
    4.代码理解
void shellSort(int data[],int len)         //希尔排序,定义数组data[],数组长度为len
    {
         int d = len;                      
         int i,j;
         while(d > 1)
         {
             d = (d+1)/2;                     //确定增量值
             for(i = 0;i < len-d;i++)
             {
                   if(data[i+d] < data[i])    //数组的第一个数与间隔增量的数进行比较
                   {
                       int temp;
                       temp = data[i+d];
                       data[i+d] = data[i];
                       data[i] = temp;        //若间隔增量的数小于前面与之比较的数,则交换
                   }
                   for(j = 0;j < 8;j++ )
                   {
                       printf("%d,",data[j]);
                   }
             }
         }
         for(j = 0;j < 8;j++ )
         {
              printf("%d,",data[j]);
         }
    }
	【总结】
         将直接插入排序与希尔排序比较总结后,发现希尔排序本质上其实就是直接插入排序,两者的联系在于希尔排序最后一轮进行的增量为1的排序便是纯粹的直接插入排序;两者的不同在于希尔排序在进行最后一轮之前,经过确定了增量后,便在组内进行直接插入排序,而进行比较的元素间隔便等于增量。
         总结完两个排序后,感觉太累,不过这是必须要做的。自考、软考,一遍又一遍,每次都知道了过程是怎样的,但看代码还是困难。所以在软考小组讨论交流的时候,有人提出,直接带数跟着代码走,这样理解更容易,也可以证明自己想的是否正确。这两个排序的代码便是自己通过将实例中的数带进去,一步一步,感觉又有了一些深的理解。    

上一篇:[leetcode/lintcode 题解] 字节跳动面试真题:删除字符


下一篇:SpringBoot+Redis实现Session数据共享