插入排序之希尔排序——【数据结构】

在我们生活中，经常会有排序之类的东西，价格、成绩、好评度……而这些东西都是我们需要的。那什么是排序，就是将数据按照想要的规定(从小到大，从高到底等等)进行排列，使其数据有序。

排序的概念及其运用

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

以上就是我们进行的排序应用。

常见的排序算法

在程序中，我们想要对一种数据进行计算，就会有许多种算法：

今天我们来讲一下希尔排序。

希尔排序

说到希尔排序，我们必须先来说明一下直接插入排序，因为希尔排序的逻辑就是直接插入排序，我们循序渐进。

插入排序

基本思想

接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

单趟：若数组(arr)除最后一个元素外其余全部有序，设最后一个元素的下标为i，将arr[i]与前面的元素比较，比他小则前面的元素向右移动，比他小则在该元素的后面插入。

复合：因为不知道数组中得到前几个元素是已经有序的，所以直接从第二个元素开始执行插入排序，单个过程与上述相同，将每个元素都进行一次插入排序。

函数实现

我们首先应该先完成单趟的交换，在一个有序数组中插入一个数据，我们需要从后向前比较进行。（安装从小到大顺序排列）如果插入的数据小于前面的数据那就进行交换，反之就停止即可。然后就是全部数组的交换，利用for循环进行操控，将数组中的所有数据进行排序。

for (int i = 0; i < n - 1; i++)
  {
    int end = i;
    int tmp = a[end + 1];
    while (end >= 0)
    {
      if (tmp < a[end])
      {
        a[end + 1] = a[end];
      }
      else
      {
        break;
      }
      --end;
    }
    a[end + 1] = tmp;
  }
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

函数实现：

写法一：

int gap = 3;
  for (int j = 0; j < gap; j++)
  {
    for (int i = j; i < n - gap; i += gap)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[n] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
    }
  }
}

使用两次for循环控制，第一个for循环控制进入组的前后顺序，第二个循环是控制每个组进行的间距以及几个组的结束。然后里面嵌套的内容与直接插入排序相似，只是将1换成gap。这种写法是一组排完，再排另外一组。

第二种：

void ShellSort(int* a, int n)
{
  int gap = n;
  while (gap > 1)
  {
    gap /= 2;
    for (int i = 0; i < n - gap; i++)
    {
      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;
    }
  }

第二种方法将两个for循环转变成一个for循环，然后进行嵌套调整。（多组并排）

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就

会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(n^1.25)到O(1.6*n^1.25) 来算。

4. 稳定性：不稳定

以上就是希尔排序的全部内容，感谢大家观看！！！