[2017.01.04] 经典排序算法思想及其实现

在计算机科学中，排序算法是算法研究中的基本问题之一。在生活和应用中，有很多地方需要对信息进行排序，如图书馆书号排序、教务系统学生成绩排序、银行支票排序等。
排序算法目的是将输入的序列（可能以数组或者链表的形式）按照一定的数值顺序进行排列，使得输入数据项（记录）中的关键字有序。对于一些含有较大卫星数据的记录，通常重新排列记录的指针数组，以减少数据移动量。排序算法的数学描述：

常用的排序算法有冒泡排序、选择排序、归并排序、快速排序、堆排序、基数排序、计数排序、希尔排序等。排序算法根据根据不同的分类标准可以分为不同的形式。如根据内存使用量，可以分为原址排序（in-place，使用较少的附加内存)和移动排序；根据算法的稳定性，可以分为稳定排序（排序后不改变相同元素的相对顺序）和不稳定排序。

下面介绍常用排序算法的主要思想，并给出相应的C++代码。

1. 选择排序
   选择排序是一种基于比较的原址排序算法。把输入数组分为两部分，从左往右逐渐构建一个排序后的左子数组，和剩余的部分组成未排序的右子数组。
   初始时：排序子数组为空，未排序子数组为输入数组。
   排序时：查找未排序子数组中的最大值或最小值，与最左边未排序边界元素交换，然后往右边移动一个单位的子数组边界。
   排序后：左子数组为排序后的数组，右数组为空。

2. 归并排序
   归并排序是一种基于比较的稳定排序算法，使用了分治的思想。
   把未排序的数组分割成n个子数组，每个子数组只包含一个元素，此时单元数子数组有序。然后重复归并子数以产生新的排序的子数组，直到仅剩下一个子数组，也就是排序后的数组。

3. 快速排序
   快速排序是一种高效常用的基于比较的不稳定排序算法，也采用了分治的思想。通俗地讲，快速排序算法就是选择一个轴关键字（pivot），把数组分为两个子数组，使得左子数组全不大于右子数组。递归对左右两半部分进行上述操作，直到数组中的元素全部有序。选择轴关键字和划分子数组的步骤可以有几种不同的实现方式，决定了排序算法有不同的实现。轴关键字选择可以直接选择边界值，或者随机选择，或者三数取中。

4. 堆排序
   堆排序主要是借助了一种称为二叉堆的抽象数据结构实现排序。
   二叉堆是一个完全二叉树，一个大根堆是指根节点的值不小于其他节点的值。主要操作有获得父节点、左孩子、右孩子、从无序输入构造堆、维护堆的性质、堆排序等操作。

/*
 * 2017.01.04 常用排序算法总结和实现
 * 参考资料《算法导论》《数据结构与算法分析——C语言描述》
 */
#include <algorithm>
#include <assert.h>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

//模板元编程
template <typename T> void Swap(T &arr, T &b) {
  T c = arr;
  arr = b;
  b = c;
}

//选择排序算法 
void selectSort(vector<int> &arr) {
  int n = arr.size();
  if (n <= 1)
    return;

  /* arr[0] to arr[n-1] is the array to sort */
  int i, j;

  /* advance the position through the entire array */
  /*   (could do j < n-1 because single element is also min element) */
  for (j = 0; j < n - 1; j++) {
    /* find the min element in the unsorted arr[j .. n-1] */

    /* assume the min is the first element */
    int iMin = j;
    /* test against elements after j to find the smallest */
    for (i = j + 1; i < n; i++) {
      /* if this element is less, then it is the new minimum */
      if (arr[i] < arr[iMin]) {
        /* found new minimum; remember its index */
        iMin = i;
      }
    }

    if (iMin != j) {
      Swap(arr[j], arr[iMin]);
    }
  }
  return;
}

//使用临时数组，辅助归并排序
void merge(vector<int> &arr, vector<int> &tmpArr, int lpos, int rpos, int rend) {
  int lend = rpos - 1, tmpPos = lpos, nums = rend - lpos + 1;
  while (lpos <= lend && rpos <= rend) {
    if (arr[lpos] < arr[rpos])
      tmpArr[tmpPos++] = arr[lpos++];
    else
      tmpArr[tmpPos++] = arr[rpos++];
  }
  while (lpos <= lend) {
    tmpArr[tmpPos++] = arr[lpos++];
  }
  while (rpos <= rend) {
    tmpArr[tmpPos++] = arr[rpos++];
  }
  //从临时数组拷贝到输入输出数组中
  for (int i = 0; i < nums; ++i, --rend) {
    arr[rend] = tmpArr[rend];
  }
  return;
}

//归并排序的递归算法
void mergeSort(vector<int> &arr, vector<int> &tmpArr, int left, int right) {
  int center;
  if (left < right) {
    center = (left + right) / 2;
    mergeSort(arr, tmpArr, left, center);       //左边递归调用
    mergeSort(arr, tmpArr, center + 1, right);  //右边递归调用
    merge(arr, tmpArr, left, center + 1, right);//归并
  }
}
//归并排序主程序
void mergeSort(vector<int> &arr) {
  vector<int> tmpArr = vector<int>(arr.size(), 0);
  mergeSort(arr, tmpArr, 0, arr.size() - 1);
}

//选择主元，并把无序数组分割为两个部分
int partition(vector<int> &arr, int low, int high) {
  assert(low >= 0 && low <= high && high < arr.size());
  int pivot = arr[low];
  while (low != high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && (arr[low] <= pivot)) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;

  return low;
}

//快排的递归算法
void quickSort(vector<int> &arr, int low, int high) {
  // low == high代表只有一个数了，此时退出循环
  if (low < high) {
    int idx = partition(arr, low, high);
    quickSort(arr, low, idx - 1);
    quickSort(arr, idx + 1, high);
  }
}
void quickSort(vector<int> &arr) {
  assert(arr.size() > 0);
  quickSort(arr, 0, arr.size() - 1);
}


//使用数组标示的大根二叉堆，辅助堆排序。这里选择从0开始，而不是算法导论中的从1开始。
inline int parenti(int i) { return (i - 1) >> 1; }
inline int lchildi(int i) { return (i << 1) + 1; }
inline int rchildi(int i) { return (i << 1) + 2; }

//维护二叉堆的性质
void maxHeapify(vector<int> &arr, int i, int n) {
  // int n=arr.size();
  int l = lchildi(i), r = rchildi(i);
  int m;
  if (l < n && arr[l] > arr[i])
    m = l;
  else
    m = i;
  if (r < n && arr[r] > arr[m])
    m = r;
  if (m != i) {
    Swap(arr[i], arr[m]);
    maxHeapify(arr, m, n);
  }
}

//构造二叉堆
void buildMaxHeap(vector<int> &arr) {
  // 从具有叶子节点的最后一个节点向前开始，组元素维护堆的性质。
  for (int i = (arr.size() - 2) / 2; i >= 0; --i) {
    maxHeapify(arr, i, arr.size());
  }
}

//堆排序
void heapSort(vector<int> &arr) {
  //首先构造大根堆
  buildMaxHeap(arr);
  //从叶子节点到根节点的左孩子开始循环，交换当前元素和根节点（最大值），
  //相当于把当前最大元素移动到“最后”，也就是把最大元素弹出二叉树。
  //然后维护堆的性质。
  for (int i = arr.size() - 1; i >= 1; --i) {
    Swap(arr[0], arr[i]);
    maxHeapify(arr, 0, i);
  }
}

int main() {
  vector<int> Arr = {3, 2, 1, 0, 11, 12, 13};
  {
    vector<int> arr = Arr;
    selectSort(arr);
    copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
  }
  {
    vector<int> arr = Arr;
    mergeSort(arr);
    copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
  }
  {
    vector<int> arr = Arr;
    quickSort(arr);
    copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
  }
  {
    vector<int> arr = Arr;
    heapSort(arr);
    copy(arr.begin(), arr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
  }

  return 0;
}