七、排序算法

1. 插入排序

把数据分成两部分，前面是有序的（最初只有一个数据），依次将后面无序部分的数据插入到前面部分，逐渐扩大有序部分，直至无序部分的数据全部插入到有序部分。

• 直接插入排序：
  将待插数据逐一与有序部分的数据作比较以确定插入位置。
• 折半插入排序：
  先找出有序部分位于中间的关键字，与待插数据做比较，每比较一次，就可将有序部分的一半数据排除而不需比较，在数据量大时效率很高。
• 二路插入排序：
  先找出有序部分位于数据中间的关键字，与待插数据做比较，如果插在前半部分，则把前面的数据向前移（一路），反之，把后面的数据向后移（另一路），这样可以减少移动次数（移动的数据少于有序部分的二分之一），但需要一个额外的数组。

实现：

//插入排序类
template<typename D>class InsSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的插入排序类
public:
  void InsertSort()
  {//直接插入排序
    int i, j;
    for(i = 2; i <= length; i++)
      if LT(elem[i].key, elem[i-1].key)  //小于
      {
        elem[0] = elem[i];  //用 elem[0] 存入
        for(j = i-1; LT(elem[0].key, elem[j].key); j--)
          elem[j + 1] = elem[j];
        elem[j + 1] = elem[0];  
      }
  }
  void BInsertSort()
  {//折半插入排序
    int i, j, m, low, high;
    for(i = 2; i <= length; i++)
      if LT(elem[i].key, elem[i-1].key)
      {
        elem[0] = elem[i];
        low = 1; 
        high = i - 1;
        while(low <= high)
        {
          m = (low + high) / 2;
          if LT(elem[0].key, elem[m].key)
            high = m - 1;
          else
            low = m + 1;
        }
        for(j = i - 1; j >= high + 1; j--)
          elem[j + 1] = elem[j];
        elem[high + 1] = elem[0];
      }
  }
  void P2_InsertSort()
  {//二路插入排序
    int i, j, first, final, mid;
    D *d;
    d = new D[length];
    d[0] = elem[1];  //设第一个数据为 d 中有序的数据（存在 [0]）
    first = final = 0; //first和final分别指示d中有序数据的第一个位置和最后一个位置
    for(i = 2; i <= length; i++)
    {
      if (first > final)
        j = length;  //j 是调整系数
      else
        j = 0;
      mid = (first + final + j) / 2 % length;  
      if (elem[i].key < d[mid].key)
      {
        j = first;
        first = (first - 1 + length) % length;
        while(elem[i].key > d[j].key)
        {
          d[(j - 1 + length) % length] = d[j];
          j = (j + 1) % length;
        }
        d[(j - 1 + length) % length] = elem[i];
      }
      else
      {
        j = final++;
        while(elem[i].key < d[j].key)
        {
          d[(j + 1) % length] = d[j];
          j = (j - 1 + length) % length;
        }
        d[(j + 1) % length] = elem[i];
      }
    }
    for(i = 1; i <= length; i++)
      elem[i] = d[(first + i - 1) % length];
    delete[] d;
  }
};

2. 冒泡排序

冒泡排序算法是从前到后逐一比较相邻的两个数据，将小值数据交换到前面。一趟排序后，最大值的数据即排到最后。如果一趟排序中没有数据交换，说明所有数据都已有序，退出排序过程。

实现：

//冒泡排序类
template<typename D>class BubSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的冒泡排序类
public:
  void BubbleSort()
  {//冒泡排序
    int i, j;
    bool change;
    for(i = length, change = true; i > 1 && change; --i)
    {
      change = false;
      for(j = 1; j < i; ++j)
        if LT(elem[j+1].key, elem[j].key)
        {
          swap(elem[j], elem[j+1]);
          change = true;
        }
    }
  }
};

两种优化思路：

• 优化外层循环：判断上一趟排序是否发生交换，未交换则已有序
• 优化内层循环：记住最后一次交换发生的位置 lastExchange ，该位置之后的相邻记录均已有序

推荐阅读：
冒泡排序算法及其两种优化

3. 简单选择排序

简单选择排序算法是在一趟排序中找出关键字最小的数据，并将它交换到正确位置。

实现：

//简单选择排序类
template<typename D>class SelSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的简单选择排序类
private:
  int SelectMinKey(int i)
  {//返回在 [i ~ length] 中 key 最小的数据的序号
    int j, k = i;
    KeyType min = elem[i].key;
    for(j = i + 1; j <= length; j++)
      if (elem[j].key < min)
      {
        k = j;
        min = elem[j].key;
      }
      return k;
  }
public:
  void SelectSort()
  {//简单选择排序
    int i, j;
    for(i = 1; i < length; i++)
    {
      j = SelectMinKey(i);
      if (i != j)
        swap(elem[i], elem[j]);
    }
  }
};

4. 希尔排序

希尔排序算法是把数据等间隔分成若干组。这样分组的好处是：数据在两两交换时，不是与相邻的数据交换，而是与较远处的数据交换。对于离正确位置很远的数据，可以减少交换次数就能到达正确位置。但这样分组并不能保证完全有序，所以希尔排序要进行几次，逐渐减小两相邻数据的间隔，最后一次排序，所有数据在一组中，两相邻数据没有间隔。由于希尔排序在交换时有跳跃，所以是一种不稳定排序。

实现：

//希尔排序类
template<typename D>class SheSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的希尔排序类
private:
  int n;  //增量序列长度
  int *dt;  //增量序列数组指针
  void ShellInsert(int dk)
  {//希尔插入排序，前后数据位置增量是 dk
    for(int i = dk + 1; i <= length; i++)
      if LT(elem[i].key, elem[i - dk].key)
      {
        elem[0] = elem[i];
        for(int j = i - dk; j > 0 && LT(elem[0].key, elem[j].key); j -= dk)
          elem[j + dk] = elem[j];
        elem[j + dk] = elem[0];
      }
  }
public:
  SheSort(int* DT, int N)
  {//构造函数
    n = N;
    dt = new int[N];
    for(int i = 0; i < N; i++)
      dt[i] = DT[i];
    assert(dt[n-1] == 1);  //最后一个增量值必须等于 1 ，否则退出
  }
  ~SheSort()
  {//析构函数
    delete[] dt;
  }
  void ShellSort()
  {//希尔排序
    for(int k = 0; k < n; k++)
    {
      ShellInsert(dt[k]);
      cout << endl << "dt[" << k <<"] = " << dt[k] << "，第" << k+1 
           << "趟排序结果（仅输出关键字）" ;
      for(int i = 1; i <= length; i++)
        cout << elem[i].key << " " ;
    }
  }
};

5. 快速排序

快速排序算法是在无序数据中任选一个作为枢轴，将枢轴数据放在临时单元 [0] 中， low 和 high 指示边界。凡是比枢轴数据小的放在 low 的左边，low 向右移；比枢轴数据大的放在 high 的右边， high 向左移。low 和 high 重合之处，将枢轴放入。此时，枢轴左边元素都不大于枢轴的，枢轴右边元素的数据都不小于枢轴的。枢轴数据已到正确位置。递归地对枢轴左右两部分数据继续进行快速排序，递归到只有一个数据时退出。快速排序也是一种 “不稳定排序” 。

实现：

//快速排序类
template<typename D>class QkSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的快速排序类
private:
  int Partition(int low, int high)
  {//以 elem[low] 的关键字作为枢轴，进行快速排序过程，返回枢轴所在位置
    int i = low, j = high;
    elem[0] = elem[low];
    while(low < high)
    {//从表的两端交替扫描
      while(low < high && elem[high].key >= elem[0].key)
        --high;
      elem[low] = elem[high];
      while(low < high && elem[low].key <= elem[0].key)
        ++low;
      elem[high] = elem[low];
    }
    elem[low] = elem[0];
    return low;
  }
  void QSort(int low, int high)
  {//快速排序
    if (low < high)
    {
      int pivotloc = Partition(low, high);
      QSort(low, pivotloc - 1);
      QSort(pivotloc + 1, high);
    }
  }
public:
  void QuickSort()
  {
    QSort(1, length);
  }
};

6. 堆排序

堆排序算法是把顺序存储的数据看成是一棵完全二叉树。对于大顶堆，确保每棵子树的根结点都是整个子树中最大的，这就保证了根结点是所有数据中的最大值，但并不能保证所有数据有序。

外部排序往往也使用堆排序算法。堆排序算法也可以用于构建优先队列。堆排序也是一种 “不稳定排序” 。

实现：

//堆排序类
template<typename D>class HSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的堆排序类
private:
  void HeapAdjust(int low, int high, bool flag)
  {//已知 elem[low ~ high] 中数据的关键字除了elem[low].key之外均满足大顶堆的定义
   //调整 elem[low] 的位置，使得都满足大顶堆定义
    int j;
    elem[0] = elem[low];
    for(j = 2 * low; j <= high; j *= 2)
    {
      if (flag)  //大顶堆，升序
      {
        if (j < high && LT(elem[j].key, elem[j+1].key))
          j++;
        if (!LT(elem[0].key, elem[j].key))
          break;
      }
      else  //小顶堆，降序
      {
        if (j < high && GT(elem[j].key, elem[j+1].key))
          j++;
        if (!GT(elem[0].key), elem[j].key)
          break;
      }
      elem[low] = elem[j];
      low = j;
    }
    elem[low] = elem[0];
  }
public:
  void HeapSort(bool flag)
  {//堆排序（flag == true : 大顶堆；flag == false : 小顶堆）
    int i;
    for(i = length / 2; i >= 1; i--)
      HeapAdjust(i, length, flag);
    for(i = length; i >= 2; i--)
    {
      swap(elem[1], elem[i]);
      HeapAdjust(1, i-1, flag);
    }
  }
};

7. 二路归并排序

二路归并排序算法首先将所有数据分成每组一个数据的情况，这时每组数据都是有序的；然后再把每两组（二路）有序数据归并成一组有序数据，减少了有序数据的组数，增加每组数据的个数； 最后把所有数据归并到一个有序数组。归并排序需要一个临时数组用来存放已归并的数据。每次归并后，再把临时数组中的数据复制回去。

实现：

//二路归并排序类
template<typename D>class MerSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的二路归并排序类
private:
  D *temp;
  void Merge(int low, int m, int high)
  {//将 elem[low, m] 和 elem[m+1, high] 归并为 elem[low, high]
    int i = low, j = m+1, k = low, p;
    for(; i <= m && j <= high; k++)
      if LQ(elem[i].key, elem[j].key)
        temp[k] = elem[i++];
      else
        temp[k] = elem[j++];
    if (i <= m)
      for(p = 0; p <= m-i; p++)
        temp[k+p] = elem[i+p];
    if (j <= high)
      for(p = 0; p <= high-j; p++)
        temp[k+p] = elem[j+p];
    for(p = low; p <= high; p++)
      elem[p] = temp[p];
  }
  void MSort(int low, int high)
  {//将 elem[low ~ high] 归并排序为 temp[low ~ high]
    if (low < high)
    {
      int m = (low + high) / 2;
      MSort(low, m);
      MSort(m+1, high);
      Merge(low, m, high);
    }
  }
public:
  ~MerSort()
  {//析构函数
    if (temp != NULL)
      delete[] temp;
  }
  void MergeSort()
  {//二路归并排序
    temp = new D[length + 1];
    MSort(1, length);
  }
};

8. 静态链表排序

两种算法：

• Arrange() 算法：顺着静态链表的 next 域依次找到应该排在位置 [i] 的数据目前所在位置 [p] 。将 elem[i] 和 elem[p] 交换，使得 elem[i] 排到正确位置。为了使静态链表不断链，令 elem[i].next = p ，即到位置 [p] 去找原来在位置 [i] 的数据。该算法在最坏情况下（每个数据都不在正确位置）要做 length-1 次交换。
• Rearrange() 算法：通过调用私有成员函数 Sort() ，给私有数据成员 adr[] 数组赋值。adr[i] 的值即是应该排在位置 [i] 的数据目前所在位置。通过循环使得所有数据排到正确位置。

实现：

//静态链表插入排序类
template<typename D>class SLinkSort: public SqTable<D>
{//带模板并继承 SqTable<D> 的静态链表插入排序类
private:
  int *adr;
  void Sort()
  {//求得 adr[i] 为静态链表中第 i 个最小数据的序号
    int i = 1, p = elem[0].next;
    while(p != 0)
    {
      adr[i++] = p;
      p = elem[p].next;
    } 
  }
public:
  SLinkSort()
  {
    adr = NULL;
  }
  ~SLinkSort()
  {
    if (adr != NULL)
      delete[] adr;
  }
  void MakeTableSorted()
  {//使无序的静态链表成为有序链表
    int i, p, q;
    elem[0].rc.key = INT_MAX;
    elem[0].next = 0;
    for(i = 1; i <= length; i++)
    {
      q = 0;
      p = elem[0].next;
      while LQ(elem[p].rc.key, elem[i].rc.key)
      {
        q = p;
        p = elem[p].next;
      }
      elem[q].next = i;
      elem[i].next = p;
    }
  }
  void Arrange()
  {//Arrange() 算法
    int i, p, q;
    p = elem[0].next;
    for(i = 1; i < length; i++)
    {
      while(p < i)
        p = elem[p].next;
      q = elem[p].next;
      if (p != i)
      {
        swap(elem[p], elem[i]);
        elem[i].next = p;
      }
      p = q;
    }
  }
  void Rearrange()
  {//Rearrange() 算法
    int i, j, k;
    adr = new int[length+1];
    Sort();
    for(i = 1; i < length; i++)
      if (adr[i] != i)
      {
        j = i;
        elem[0] = elem[i];
        while(adr[j] != i)
        {
          k = adr[j];
          elem[j] = elem[k];
          adr[j] = j;
          j = k;
        }
        elem[j] = elem[0];
        dar[j] = j;
      }
  }
};

9. 基数排序

基数排序算法采用静态链表排序算法对字符串进行按位排序。

推荐阅读：
基数排序