【手撕排序算法1:插入排序与希尔排序】

void InsertSort(int* a, int n)
{
  //[0,end]有序   end+1  位置的值插入进去,让[0,end+1]有序
  int i = 0;
  //这个for循环是用来控制end的取值的,
  //也就是控制这整个区间,从[0,0]到[0,n-1]有序,
  //也就是整个数组的下标是从0到n-1有序,也就是整个数组有序
  //可以把这个for循环当成摸牌阶段,每摸一张牌,i+1,即end+1,也就是区间长度+1
  for (i = 0; i < n - 1; i++)//这里要小心,i一定要小于n-1,因为如果i==n-1,那么end==n-1,end+1==n,a[n]:为越界访问,会报错
  {
    int end = i;
    int tmp = a[end + 1];
    //可以把这个while循环看作插牌阶段,将比要插入的牌大的牌向后挪动,空出地方来让要插入的牌成功插入进去.
    while (end >= 0)//找位置
    {
      if (a[end] > tmp)//挪动牌
      {
        a[end + 1] = a[end];
        --end;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;//插牌
  }
}

>下面我说一下为什么要break?
>1.我们想要插入一张牌,需要从后往前找适合这张牌插入的位置
>而只有两种情况我们会停下来,
>第一种:找到了一个位置,
>使得这个位置之前的所有牌都小于等于这张牌
>这个位置之后的所有牌都大于这张牌
>这时我们就没有必要再去往前找了,所以我们采用break
>
>第二种:我们没有找到适合的位置,而是一路找到了牌首,
>这个时候end==-1,通过while循环自身的判断条件退出循环
>2.而且,我们发现无论是因为两种情况的哪一种退出了while循环,
>最终我们要插入的牌的位置始终都是退出while循环后的end+1的位置,
>3.所以我们直接考虑在后面进行插入那张牌

1.稳定性的定义:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，
若经过排序，这些记录的相对次序保持不变，
即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，
则称这种排序算法是稳定的；否则称为不稳定的。
2.稳定性的用途:
我们在这里就举一个例子,就能够帮助大家很好的理解:
甲和乙去参加同一个考试,这个考试规定
如果存在相同分数的人,则根据他们提交答案的时间顺序来排名
碰巧甲和乙都考了满分,但是甲比乙提前半个小时交卷
本来应该是甲第一,乙第二
这时如果我们采用的排序算法具有稳定性,则能成功保证甲为第一,乙为第二
如果不稳定,则难以保证甲为第一,乙为第二
那么比赛将失去公平性,所以在这里我们必须要采用具有稳定性的算法.
3.插入排序是具有稳定性的,
因为我们是从后往前依次比较元素大小,
只有当我们遇到比我们要插入的那个数字大的元素时才会将它往后挪
而当我们遇到跟我们所要插入的数字大小相同的元素时,
我们把它归为比我们要插入的数字小的那一类,所以并不会使相同元素的顺序有错乱,也就保证了稳定性
4.时间复杂度的定义:算法中的基本操作的执行次数，为算法的时间复杂度。
注意:当某个算法在不同情况下基本操作执行的次数不同时,按照最坏的情况去计算时间复杂度
时间复杂度:O(N^2),
时间复杂度看最坏的情况:
最坏:逆序变为升序 O(N^2),for循环和while循环都走满了,实际上是1+2+3+....+n-1=(1+n-1)*(n-1)/2=n*(n-1)/2
根据大O的渐进表示法,表示为O(N^2)
最好:升序变为升序O(N),for循环走满了,while循环在每个for循环内只走一次,因为一进去就break跳出来了
所以直接插入排序还是要比直接选择排序要好很多的,因为它的最好情况是 O(N),而直接选择排序最好最坏都是一个样,都是O(N^2)
这里先提一下直接选择排序,后面我们会介绍这个排序算法的
5.插入排序的优劣点:
根据上面提到过的插入排序的时间复杂度的最好情况和最坏情况
我们可以得出以下结论
1.当数组本身部分有序或者整体有序时,直接插入排序的效率非常高,时间复杂度达到了O(N)
2.可是当数组逆序或者部分逆序时,直接插入排序的时间复杂度就达到了O(N^2),所以有人就发明了希尔排序

第一步:预排序:并不是让它直接有序,而是让它尽可能有序
分组排序,
目的:尽可能快的让小的数据去前面,大的数据去后面
间隔为gap是一组
假设gap==3
9 8 7 6 5 4 3 2 1 0
第一组:  9   6   3   0
第二组:  8  5   2
第三组:  7   4   1
分别对每一组进行直接插入排序
经过一轮之后得到:
0 2 1 3 5 4 6 8 7 9
间隔为gap,就有gap组
多组间隔为gap的预排序,gap由大变小,
gap越大,大的数可以越快的到后面,
        小的数可以越快的到前面
但是:
gap越大,预排完越不接近有序,
gap越小,预排完越接近有序
所以gap不能给固定的值,要让gap逐步缩小,缩小直到gap==1,
当 gap==1时,就是直接插入排序

void ShellSort(int* a, int n)
{
  int gap = n;
  //当 gap==1时,就是直接插入排序
  //gap>1时都是预排序  目标;接近有序
  //gap==1时才是插入排序  目标:直接有序
  //所以必须要保证gap的最后一次为1
  while (gap > 1)//保证最后gap会减为一
  {
    //log(2)N
    gap = gap / 2;//除2可以保证最后一次gap一定为1
    //初始状态,保证gap相对于整个数组来说是一个不错的取值既能够使预排序的效果更加明显,又能使整个循环次数降到尽可能小,追求效益最大化
    //有些人认为除以2好,有些人认为除以3好,所以没有固定除法,
    //但是除以2可以保证gap的最后一次为1
    //但是除以3则无法保证
    //所以以下才是gap的有效除法,对3而言
    //gap = gap / 3 + 1;  log(3)(N)
    //当gap很大时,下面预排序时间复杂度为O(N)
    //当gap很小的时候,数组已经很有序了,这时差不多也是O(N)
    //把间隔为gap的多组数据同时排序
    for (int i = 0; i < n - gap; i++)//把间隔为gap的数据同时排,非常巧妙,下面我画图给大家看一下,这是以gap==3作为示例
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}
//其实大家也能够看出来
//只要把直接插入排序中的1替换为gap即可写出里面for循环的式子

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();//我们在这里生成了100000个随机数进行排序
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
  }
  int begin1 = clock();//clock()获取到系统运行到这里的毫秒数
  InsertSort(a1, N);
  int end1 = clock();
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
  int begin5 = clock();
  QuickSort(a5, 0, N - 1);
  int end5 = clock();
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
}

void ShellSort(int* a, int n)
{
//整体的时间复杂度是:O(log(2)(N)*N)或者O(log(3)(N)*N)
//平均的时间复杂度是O(N^1.3)
  int gap = n;
  while (gap > 1)
  {
    //gap /= 2;
    //假设这个最外层的while循环=一共进行x次
    //2*2*2*2*......*2==N
    //即2^x(这里表示2的x次方,而不是2异或x)==N
    //所以x=log(2)(N)(即以2为底N的对数)
    gap = gap/3 + 1;//在这里我们呢忽略掉+1的影响,因为+1对于N来说在待排序的数据相当多的情况下完全可以忽略不计
    //同理这里的次数是log(3)(N)(即以3为底N的对数)
    int end = 0;
    //下面我们来看这个for循环的跑的次数
    //当gap很大时,下面的预排序时间复杂度O(N)
    //当gap很小时,数组已经很接近有序了,这时差不多也是O(N)
    for (int i = 0; i < n - gap; i++)
    {
      end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (tmp < a[end])
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}