希尔排序：

希尔排序 其实就是一个对我们上面的直接插入排序的一个优化

① 使用预排序

② 在使用直接插入排序

首先我们上面不是说了直接插入排序比较适应那些 局部有序 和 接近有序 的数组嘛 所以如果说现在给我们一个数组 它并不满足刚刚的两种情况 那我们是不是可以使用一个预排序 是这个数组里的接近我们的这两种情况  这个时候再使用我们的直接插入排序是不是会更好一点呢？

希尔排序--预排序：

我们与排序的思想就是 把大的数更快的到后面去  把小的数更快的到前面去

思想知道了 那我们该怎么去实现它呢？

首先实现预排序 我们要把我们的数据分成一个一个的组(gap) 假设gap=3  (也就是三个间隙为一组)

 大家看到我们此时的分组了 其实我们分组的目的就是为了把数据分成几个组 就好像这里我们是 9 5 6 8 一组 1 8 7一组 3 2 4一组 我们对着三组数据分别进行插入排序的操作

如图所示 就是每一组进行一个插入排序的操作 让小往前移动 让大的往后移动 其他组也是一样的道理： 

还有一组我就不演示了 相信大家应该明白其中的道理了吧

那现在大家想想 我们既然这里gap设置的是3 那如果是其他的值呢 我们的预排序又会有怎样的效果呢？

实际上很显然 当我们的gap越小越接近有序  gap越大 大的数据 可以更快到后面，小的数可以更快到到前面 但他越不接近有序

         int gap=3;
         for(int i=0;i<gap;i++)
         {
           for(int j=i;j<n-gap;j+=gap)
           {
            int end = j;
      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;
           }
         }

这是我们根据思路写出的代码 其实跟直接插入排序的整体结构差不多是不是？ 我们外面两层for循环是为了遍历每一组  我们的边界之所以设成 n-gap：

遍历到 n-gap-1 就可以了 就不用再往后遍历

当然我们还可以这样写 外面的遍历：

        int gap=3;
        for (int i = 0; i < n - gap; i++)
    {
      int 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;
    }

 这样写得话 我们就不是一组一组的遍历了 而是遍历完一组 又到下一组 大家看是不是这样？

我们上面不是说了 gap不同排序的效果也不同嘛 那现在假设我们的 gap=1 现在又是什么情况呢？

其实很简单 我们gap=1不就是间隙为1是同一的组嘛 那这样是不是每个数都是一个组里面的这个时候在实现for循环里面的操作不就是 一个插入排序了嘛？

  我们 的希尔排序分为预排序和直接插入排序  我们 gap不同  也就对应前面的两种顺序 那我们是不似乎可以把gap改成不是固定的值内？  

void ShellSort(int* a, int n)//希尔排序 gap不为1 预排序 gap为1 插入排序
{
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    for (int i = 0; i < n - gap; i++)
    {
      int 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;
    }
  }
}

 我们这里gap的变化并没有固定的标准 只是有些书上是这样建议的 写成其他的也行  我们+1是必须的 因为这样才能保证必定gap会有一次等于 1

希尔排序的时间复杂度：

预排序：

gap很大的时候 数据会跳的很快 差不多是O(N)

我们其实gap很大的时候 我们数据跳的也就越快 假设 gap=n/3 那是不是我们的数据只要跳三次就可以到应该的位置上了呢 那我们此时for循环里面的操作是不是可以忽略不记了呢 以后的数不也是一样的道理嘛 这就是为什么是O(N)了

gap很小的时候 我们的数据 已经很接近有序了 这个时候排的话 只有很少的数才会去交换 那我们的时间复杂度是不是也可以约估成O(N)了呢？

我们外面的while循环又要进行多少次呢？

咋们每次 ÷3+1 ÷3+1 其实＋1就可以忽略掉了

是不是就是这样内  n/3/3/3/3/.../3/3=1;

假设 ÷ 了x次 那么 x=log3n

总结：如果按照这种算法 咋们的希尔排序的时间复杂度就是O(N*log3N) (实际上呢 一本严蔚敏老师的书上 提到的是 按照计算 他的出来希尔排序的比较和移动次数约为n^1.3) 稳定性：不稳定

选择排序：

选择排序其实挺简单的：

我们遍历这个数组选出最小的放到前面 每次遍历的第一个位置都会跟着选出数据的次数更新

我们选出第一个最小的数据了 那么就把它与第一个数据交换 继续遍历数组但不包括第一个位置 此时选出来的数据就要与第二个位置的数据交换了  大家看能明白嘛？

我这里写的呢 跟一般教材上面的不太一样  我这里写得是同时选两个数 也就是一个最大一个最小 但是呢思路都是一样的

void SelectSort(int* a, int n)
{
  int maxi, mini, right, left;
  left = 0;
  right = n - 1;
  while (left < right)
  {
    maxi = mini = left;
    for (int i = left; i < right + 1; i++)
    {
      if (a[mini] > a[i]) mini = i;
      if (a[maxi] < a[i]) maxi = i;
    }
    swap(a + mini, a + left);
    swap(a + maxi, a + right);
    left++;
    right--;
  }
}

 这样我们的代买就写完了  不知道大家对照着这个数组看有没有发现上面是否存在问题呢？

这个问题挺难发现的 我们第一次选 maxi=0 mini=1 我们首先mini与left 交换 可是我们 此时maxi上的位置还是我们的9嘛 刚刚的交换不是就把 9 换到mini的位置上了嘛 所以应该是这样的：

void SelectSort(int* a, int n)
{
  int maxi, mini, right, left;
  left = 0;
  right = n - 1;
  while (left < right)
  {
    maxi = mini = left;
    for (int i = left; i < right + 1; i++)
    {
      if (a[mini] > a[i]) mini = i;
      if (a[maxi] < a[i]) maxi = i;
    }
    swap(a + mini, a + left);
    if(maxi==left) maxi=mini;  
    swap(a + maxi, a + right);
    left++;
    right--;
  }
}

所以正确的代码应该是这样的 因为我们既然我们的maxi变了 就把他修正一下不就行了嘛 left与mini交换了 maxi=left 那么此时正确的max的值不就应该在mini的位置了嘛

传统的选择排序的时间复杂度：O(N^2) 稳定性：不稳定