C语言-每天认识一个排序算法之希尔排序（二）

希尔排序

 希尔排序又称为“缩小增量排序”，它是对直接插入排序算法的改进。
 希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次直接插入排序。这是它的基本思想。最后我们所取的增量应为1.

void ShellSort(int arr[], int n)
{
  int i, j, d;
  d =  n / 2; /*确定固定增量值*/
  while (d >= 1)
  {
    for (i = d + 1; i <= n; i++) /*数组下标从d+1开始进行直接插入排序*/
    {
      arr[0] = arr[i]; /*设置监视哨*/
      j = i - d;       /*确定要进行比较的元素的最右边位置*/
      while ((j > 0) && (arr[0] < arr[j]))
      {
        arr[j + d] = arr[j]; /*数据右移*/
        j = j - d ;           /*向左移d个位置V*/
      }
      arr[j + d] = arr[0]; /*在确定的位罝插入arr[i]*/
    }
    d = d / 2; /*增量变为原来的一半*/
  }
}

 因为设置了监视哨，所以传入数组的第一个数要专门留下来给监视哨使用。
 希尔排序是一种不稳定的排序算法，据统计分析其时间复杂度约为O(n^1.3)，在排序过程中仅需要一个元素的辅助空间用于数组的元素值的交换，空间复杂度为O(1)。

为什么不直接使用直接插入排序算法？

 这里有一个统计表大家可以用作参考，通过表格大家可以明显的看到，希尔排序比较和交换值的次数是远远比插入排序要低的，在数据量过大的情况下，会节省内存等性能优化的问题，这也是使用算法的目的。