直接插入排序

算法实现

直接插入排序的基本思想：插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。简单来说，就是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

实现思路： ①从第一个元素开始，该元素可以认为已经被排序
②取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤

image.png
例如我们有一组数字：｛5，2，4，6，1，3｝，我们要将这组数字从小到大进行排列。 我们从第二个数字开始，将其认为是新增加的数字，这样第二个数字只需与其左边的第一个数字比较后排好序；在第三个数字，认为前两个已经排好序的数字为手里整理好的牌，那么只需将第三个数字与前两个数字比较即可；以此类推，直到最后一个数字与前面的所有数字比较结束，插入排序完成。

参考文章： https://www.cnblogs.com/chengxiao/p/6103002.html

  1. void InsertSort(SqList *L){
  2.     int i,j;
  3.     for(i=2;i<=L->length;i++){
  4.         if(L->r[i]<L->r[i-1]){ //需要将L->r[i]插入到已经排好序的r[1~(r-1)]
  5.             L->r[0]=L->r[i]; //被插入的记录：L->r[i]
  6.             //在L->[1]~L->r[i-1]中找到插入L->r[i]的位置
  7.             for(j=i-1;L->r[j]>L->r[0];j--){
  8.                 L->r[j+1]=L->r[j]; //大于L->r[i]的元素右移，以便空出位置插入L->r[i]
  9.             }
  10.             //这里的L->r[0]就是原来被插入有序序列的元素
  11.             L->r[j+1]=L->r[0];
  12.         }
  13.     }
  14. }

算法性能分析

时间复杂度

  • 最好的情况下，即排序表本身就是有序的，那么比较了n-1次，没有移动记录，时间复杂度为O(n-1)
  • 最坏的情况下，即排序表逆序，这时候需要比较2+3+…+n=(n+2)(n-1)/2次，移动次数也达到了最大值，时间复杂度为O(n^2)
  • 平均情况下，时间复杂度为O(n^2)

    注意： 直接插入排序比简单选择排序和冒泡排序性能略微高一点

空间复杂度

最优的空间复杂度为开始元素已排序，则空间复杂度为 0；
最差的空间复杂度为开始元素为逆排序，则空间复杂度最坏时为 O(N);
平均的空间复杂度为O(1)

稳定性

直接排序算法是基于插入元素，不会改变原来的有序序列，因此是稳定的

希尔排序

算法实现

希尔排序的主要思想就是不断把待排序数组分成gap组（gap的取值一般为{n/2，n/2/2，…，1}），然后在这gap中分别进行直接插入排序，这样就可以使得当gap=1的时候排成了大致的顺序，因此在gap=1的时候就只需要移动极少量的元素即可。

参考文章： https://www.cnblogs.com/chengxiao/p/6104371.html

算法实现

 /**
  * 希尔排序 针对有序序列在插入时采用移动法
  *
  * @param arr 待排序数组
  */
 public static void sort1(int[] arr) {
     //增量gap，并逐步缩小增量
     for (int gap = arr.length / 2; gap > 0; gap /= 2) {
         //从第gap个元素，逐个对其所在组进行直接插入排序操作
         for (int i = gap; i < arr.length; i++) {
             int j = i;
             int temp = arr[j];
             if (arr[j] < arr[j - gap]) {
                 while (j - gap >= 0 && temp < arr[j - gap]) {
                     //移动法
                     arr[j] = arr[j - gap];
                     j -= gap;
                 }
                 arr[j] = temp;
             }
         }
     }
 }

image.png
那这个图来说，当增量gap=2的时候，按照“2和0、3和1、4和2、5和3 ……”这样的规律进行比较并且交换，其实就是在分成的两组中各进行了一次排序。最后当gap=1的时候，就对仅有的一个分组在进行了一次直接插入排序。

算法性能分析

时间复杂度

希尔排序的虽然有三层for循环，但是随着for循环的推进，其循环的次数下降的很快，因此其时间复杂度其实不是很高，但是我这里难以给出严格的数据证明，因此直接说结论。其最坏时间复杂度依然为O(n2)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

空间复杂度

希尔排序的空间复杂度为O(1)，需要借助一个中间量temp

稳定性

希尔排序是一种不稳定的排序算法