Question

实验简介

学习了前面一章的查找，我们知道二分查找需要先对数据进行排序，那么这章开始我们就来讲解一下几种经典的排序算法。

一、直接插入排序

首先我们来讲直接插入排序，它的做法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1) 趟扫描以后就完成了整个排序过程，如下图所示。

直接插入排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 直接插入排序
 */
void InsertSort(int *array)
{
  int i, j;
  for (i = 2; i <= n; i++)
  {
    if (array[i] < array[i - 1])
    {
      array[0] = array[i];
      array[i] = array[i - 1];
      for (j = i - 2; array[0] < array[j]; j--)
      {
        array[j + 1] = array[j];
      }
      array[j + 1] = array[0];
    }
  }
}

int main()
{
  int i;
  int *array;
  printf("请输入数组的大小：");
  scanf("%d", &n);
  array = (int*) malloc(sizeof(int) * (n + 1));
  printf("请输入数据（用空格分隔）：");
  for (i = 1; i <= n; i++)
  {
    scanf("%d", &array[i]);
  }
  InsertSort(array);
  printf("排序后为：");
  for (i = 1; i <= n; i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

二、希尔排序

希尔排序也是插入排序的一种，但它在效率上要比上面的直接插入排序高，它是对直接插入排序的改进，它的基本思想是先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2< d1 重复上述的分组和排序，直至所取的增量 dt=1(dt<…< d2< d1)，即所有记录放在同一组中进行直接插入排序为止，增量序列尤为关键，一般的初次取序列的一半为增量，以后每次减半，直到增量为 1，大致过程如下图所示。

希尔排序的代码实现：

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 希尔排序
 */
void ShellSort(int *array)
{
  int k = n / 2; //增量序列（仅作举例）
  while (k > 0)
  {
    int i, j;
    for (i = k + 1; i <=n; i++)
    {
      if (array[i] < array[i - k])
      {
        array[0] = array[i];
        for (j = i - k; j > 0 && array[0] < array[j]; j -= k)
        {
          array[j + k] = array[j];
        }
        array[j + k] = array[0];
      }
    }
    k = k / 2;
  }
}

int main()
{
  int i;
  int *array;
  printf("请输入数组的大小：");
  scanf("%d", &n);
  array = (int*) malloc(sizeof(int) * (n + 1));
  printf("请输入数据（用空格分隔）：");
  for (i = 1; i <= n; i++)
  {
    scanf("%d", &array[i]);
  }
  ShellSort(array);
  printf("排序后为：");
  for (i = 1; i <= n; i++)
  {
    printf("%d ", array[i]);
  }
  printf("\n");
}

三、小结

这一章讲了插入排序中的两个经典算法，直接插入排序和希尔排序。直接插入排序的主要思想是每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序，它属于稳定的排序，最坏时间复杂性为 O(n^2)，空间复杂度为 O(1)。希尔排序的主要思想是分组插入，它是不稳定的排序，它的时间复杂度跟增量序列有关，在取增量序列时要保证其中的值没有除 1 之外的公因子，并且最后一个增量值必为 1。

作业

结合这章讲的插入排序实现二分查找。

实验中有任何问题欢迎到 实验楼问答 提问。