几个排序算法以及求数组第K大数

最近参加了一次面试，说实话，答得很糟糕，要不是有朋友内推，估计已经凉了。面试其他的问题答好答坏，都能自我安慰，不过最后问了一个“求数组第K大元素”的题，第一反应是排序完了直接取，后来反应上来用优先队列，但是STL的优先队列用多了，最大堆到底怎么实现的忘掉了。加上是第一次面试，一紧张直接只记得插入排序怎么撸……
面试的小姐姐一直很温柔，还安慰了我好几次，然而结束后我还是很郁闷，怎么连最大堆都不能手撸了呢……悲愤之下把几个常用的排序算法又手撸了一遍。在这里做个记录：

先来一段基础函数，用来生成随机数列、判断数列是否有序，打印数列。

• 基础函数

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>
//这几个头文件默认下面所有代码段都包含了

using namespace std;

void generate_rand_arr(vector<int> &arr) {
  default_random_engine e(time(NULL));
  uniform_int_distribution<int> dis(1, 512);
  int size = dis(e) % 80 + 20;
  arr.resize(size, 0);
  for (int i = 0; i != size; ++i) {
    arr[i] = dis(e);
  }
}

bool sorted(vector<int> &arr) {

  for (int i = 1; i != arr.size(); ++i) {
    if (arr[i - 1] > arr[i])
      return false;
  }
  return true;
}

void print_arr(const vector<int> &arr) {

  for (int i = 0; i != arr.size(); ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

• 插入排序

void insert_sort(vector<int> &arr) {

  for (int i = 1; i != arr.size(); ++i) {
    int j;
    int tmp = arr[i];
    for (j = i; j != 0; --j) {
      if (tmp < arr[j - 1]) {
        arr[j] = arr[j - 1];
      } else
        break;
    }
    arr[j] = tmp;
  }
}

鉴于面试官让我描述这个算法的时候，还卡了一分钟，我决定贡献一个口述版插入算法：

设现在有一堆牌（一个数组），我们手里拿着第0张牌，现在我们开始摸第1张牌（i从1开始），摸到牌以后，我们将摸到的牌与手里的牌从后到前比较（j从i到1循环），如果摸到的牌更小，则将手里的牌向后挪一个位置（为摸到的牌腾出空位），直到对比到第0张牌（说明摸到的牌是当前最小的），或者遇到一个比摸到的牌更小的牌，则将手里的牌插入该位置（插入j位置）。这样就保证手里的牌一直是有序的，当我们处理完最后一张牌时，手里的牌完全有序。

但是这种方法处理第K大问题是最慢的，因为必须整个数列有序后才能输出，也就是说假如像寻找最大数这样的题目，也要做一次完整的排序，显然还不如直接扫描一遍数组来得快。

• 冒泡排序

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

void pop_sort(vector<int> &arr) {

  int size = arr.size();
  for (int i = 0; i != size; ++i) {
    int tmp;
    for (int j = size - 1; j != i; --j) {
      if (arr[j - 1] > arr[j]) {
        swap(arr[j - 1], arr[j]);
      }
    }
  }
}

冒泡排序是交换排序的一种，需要一个swap方法来交换两个数组，同样的基于交换的排序算法还有快速排序。

冒泡排序的口述版如下：现在桌面上有一列牌，我拿起最后一张，依次向前对比，假如前面的牌比手里的牌大，那么交换这两张牌，我手里仍然握着较小的这张牌，继续向前比较，假如前面的牌比手里的牌小，那么手里的牌放到这张较小的牌的位置，手里拿起这张更小的牌，向前对比，直到第一张。这样每次就可以把最小的牌顶到最前面去，之后我们对[1~n]的序列继续重复此操作即可。

这种做法对于求第K大就友好一些，稍作变通就可以成为每次把最大的冒泡到前面去，这样求到第K个元素就可以停止了。当然，如果K > N/2，还可以将问题转变为，求第N-K小个元素。这样能好一点。

• 归并排序

void merge(vector<int> &arr, int begin, int middle, int end) {
  //将两个归并。
  int left_len = middle - begin; //不包含middle
  int right_len = end - middle;  //不包含end
  vector<int> left(arr.begin() + begin, arr.begin() + middle);
  vector<int> right(arr.begin() + middle, arr.begin() + end);
  int start = begin, i, j;
  for (i = 0, j = 0; i != left.size() && j != right.size();) {
    if (left[i] < right[j]) {
      arr[start++] = left[i];
      ++i;
    } else {
      arr[start++] = right[j];
      ++j;
    }
  }
  if (i == left.size()) {
    while (j != right.size()) {
      arr[start++] = right[j++];
    }
  } else {
    while (i != left.size()) {
      arr[start++] = left[i++];
    }
  }
}

void merge_sort(vector<int> &arr) {

  int size = arr.size();
  for (int step = 1; step < size; step *= 2) {
    for (int i = 0; i <= size; i += 2 * step) {
      if (i + step > size) { //最后剩余的连一组都不够了
        continue;
      } else if (i + step * 2 > size) {
        merge(arr, i, i + step, size);
      } else {
        merge(arr, i, i + step, i + step * 2);
      }
    }
  }
}

这个算法的缺点在于，每次归并时都需要申请两个临时数组来保存元素，会产生较大的复制开销。

口述版：我们将一堆牌分为一张一张的子序列，现在每个子序列都是有序的（因为每个子序列只有一个元素），现在我们将相邻的两个子序列合并起来，合并的方法是比较子序列的第一个元素，哪个元素小我们将这个元素从那个子序列里取出来，并从该子序列里删除这个元素（实际的操作是将下标向前移动1位），直到两个子序列合并完毕，这样我们就得到了序列长度为2的一堆有序的子序列，我们再将两个相邻子序列合并起来，如此重复直到所有子序列都合并起来。

这个做法对于求第K大来说也是必须等整个序列有序后才能求。只是排序的时间复杂度比插入排序好一点，但是因为每次都要发生临时数组的复制，在数据量不大的时候，未必好到哪里去。

• 快速排序

unsigned quick_sort_real(vector<int> &arr, unsigned begin, unsigned end) {

  default_random_engine e(time(NULL));
  unsigned middle = begin + e() % (end - begin);
  swap(arr[middle], arr[end - 1]);
  unsigned index = begin;
  for (unsigned i = begin; i != end - 1; ++i) {
    if (arr[i] < arr[end - 1]) {
      swap(arr[index], arr[i]);
      ++index;
    }
  }
  swap(arr[index], arr[end - 1]);
  return index; //就是中位数所在地
}

void quick_sort_recu(vector<int> &arr, int begin, int end) {

  if (begin >= end) {
    return;
  }
  unsigned middle = quick_sort_real(arr, begin, end);
  quick_sort_recu(arr, begin, middle);
  quick_sort_recu(arr, middle + 1, end);
}

void quick_sort(vector<int> &arr) {
  quick_sort_recu(arr, 0, arr.size());
}

口述版：

先在序列中随机选择一个数字（称为主元），将其交换到序列尾部，此时维护一个从0开始的下标i，接着从序列头部开始拿牌与主元做比较，设此时拿到第k张牌，发现比主元小，那就将这张牌与第i张牌做交换，接着将i递增，这样做的效果是不断有比主元小的元素被交换到前面去，而比主元大的元素则不断交换到后面去。等这个过程结束后，将主元与下标i处的值互换，此时主元前面的值都比主元小，主元后面的值都比主元大。再对两个子序列递归调用这种方法即可。

这种做法求第K大就靠谱一点，比如下标i刚好是K-1，那么就直接找到了第K大元素，如果i > K-1，说明要找的元素在主元前面，则问题转换为，在比主元小的元素中求第K大元素，如果i<K-1，说明要找的元素在住院后面，则问题转换为，在比主元大的元素中求第K-i大元素。这样……反正有点撞运气。但是因为问题规模不断缩小，且从统计学意义上讲我们应当期望主元实际上刚好是中位数，这样相当于二分查找，也很快能得到答案。

• 堆排序

inline unsigned LEFT(unsigned i) { return i * 2 + 1; }
inline unsigned RIGHT(unsigned i) { return i * 2 + 2; }
inline unsigned FATHER(unsigned i) { return (i - 1) / 2; }

void max_heapify(vector<int> &arr, unsigned root, unsigned heapsize) {

  unsigned left = LEFT(root);
  unsigned right = RIGHT(root);
  unsigned largest = arr[root];
  unsigned index = root;

  if (left < heapsize && arr[left] > largest) {
    largest = arr[left];
    index = left;
  }
  if (right < heapsize && arr[right] > largest) {
    largest = arr[right];
    index = right;
  }
  if (index != root) {
    swap(arr[index], arr[root]);
    max_heapify(arr, index, heapsize);
  }
}

void build_heap(vector<int> &arr) {

  unsigned root = (arr.size() - 1) / 2;
  unsigned size = arr.size();
  for (unsigned i = root + 1; i != 0; --i) {
    //我们假设的是下标最大可以到unsigned，所以不能用for(int i = root ; i <= 0 ;
    //--i) for(unsigned i = root ; i <= 0 ; --i)会无限循环，也不能用
    max_heapify(arr, i - 1, size);
  }
}

void heap_sort(vector<int> &arr) {

  build_heap(arr);
  unsigned size = arr.size();
  for (unsigned i = size; i != 0; --i) {
    swap(arr[0], arr[i - 1]);
    max_heapify(arr, 0, i - 1);
  }
}

口述版：将序列维护成一棵二叉树，该树递归满足以下性质：任何节点的左右子节点的数值都比自己小。不同于用指针指向左右子树的二叉树，最大堆用数组下标来指示左右子树，如下图：

　　　　　　　　　　　　　　　A[0]
　　　　　　　　 　Ａ[1]　　　　　　　　　Ａ[2]
　　　　　　Ａ[3]　　　　Ａ[4]　　　Ａ[5]　　　 Ａ[6] …

我们通过一种方式，让整个数列符合最大堆的性质，则可以保证A[0]是整个数列中最大的值，将其交换到序列尾部，接着对整个堆从A[0]号元素往下递归维护最大堆的性质即可，此时序列规模缩减为N-1，之后不断交换A[0]和更小规模数组的最后一个元素，直到完全有序。

设数组维度为N，那么显然，最后一个有子节点的元素应该是(N-1)/2下标处的元素，那么最开始建堆时只需要从该元素向前，维护所有节点的最大堆性质即可。

最大堆应该是求第K大元素的标准答案。可我忘了下标怎么对应的……唉……都怪STL。平常都直接写priority_queue<T,vector\<T>>，不管内部实现的。

• 计算排序

void count_sort(vector<int> &arr) {

  //假设已经得到M
  auto Mit = max_element(arr.begin(), arr.end());
  auto M = *Mit;
  vector<int> tmp(arr.begin(), arr.end());
  vector<int> count(M + 1, 0);
  for (unsigned i = 0; i != tmp.size(); ++i) {
    count[tmp[i]] += 1;
  }
  for (unsigned i = 1; i != M + 1; ++i) {
    count[i] = count[i] + count[i - 1];
  }
  for (unsigned i = tmp.size(); i != 0; --i) {
    arr[count[tmp[i - 1]] - 1] = tmp[i - 1];
    count[tmp[i - 1]] -= 1; //主要是应对相同数字
  }
}

一个比较神奇的排序方式，要求数列比较均匀且紧密。实际是直接算出来某个元素是整个序列第几大，然后将元素放到正确位置上去。

如果一个数列是均匀且紧密的，这种方法应该是最快得到第K大数的方法，时间复杂度是N的常数倍，还可以在tmp数组上使用二分查找，更快地找到第K大数。但因为对数列本身的要求较高，所以不是最大堆这种普适的方法。

• 测试主函数

int main() {

  vector<int> arr;
  generate_rand_arr(arr);
  print_arr(arr);
  ****_sort(arr);
  cout << sorted(arr) << endl;
  print_arr(arr);
  return 0;
}

• 后记

　　其实最近心情不太美丽，因为连续处在被挑选的位置，而且都不太顺利。

　　前段时间见了女友的父母，结果他们对我并不满意，不满意的理由很奇怪，是我完全想不到的点，我原以为他们想看的是我多么优秀，到现在我才发现，对于一个“霸权主义”的“准岳父”来说，其实他想看的是我有多么恭顺，你有其他的什么优点？对不起，在那么两顿饭的时间里，他们没有看到想要看到的东西，就足以将你否定，你的才华、努力、品德、学历等等，都没来得及展现就被灭杀。

　　所以从某种意义上讲，处于被挑选的位置时，运气在结果中占了很大的比重。高考也是，高考及以后的人生，现在回看处处充满了意外，仔细想想，运气占了很大的比重，不是说我很糟糕，而是说比我优秀的人很多，但因为运气不好，他们处在比我更差的位置上，而比我能力差的人也不少，但因为选择对了，运气更好，比我混的好的也比比皆是。

　　这次面试也差不太多，推荐我的朋友在闲聊时问了我一个DP，刚好最近刷题碰到的多，随口就答了，没想到面试时遇到一个很久没有手撸过的“准排序”问题，一紧张就跪了，这一方面也是运气不太凑巧。不过另一方面，也反映出我虽然手撸过很多次排序，但排序的一些基本思想仍然没有深入脑海。冒泡排序到底是如何工作的，插入排序呢？让我描述一遍还会卡，说明不扎实。

　　到现在难免感慨，男怕入错行这句话真是铁律，当年我也算是挤在全国top级的那一堆学生里面，结果到一个不喜欢的专业，去了一个不喜欢的工作环境，现在再转身去追，很多人，真的是很多很多人都已经跑到我前面去了，驷马难追啊。而即使是这样，我还算好的，至少在不喜欢的专业上拿到了专业证书认证，而且还有一丢丢的年龄优势，可以再疯狂一次，做一次破釜沉舟的转型，然而很多和我一样的人因为结婚、生育等家庭其他问题，都已经绝无转身的可能。这一切源于什么呢？我认为还是源于我们教育上的不足，很多像我一样的人在选择大学的时候，并没有做到真正意义上的选择，因为从来都只知道读书，而不知道怎么去规划自己的人生。我眼见的那些高中毕业时就知道规划自己人生的人，即使天资并不聪颖过人，也已经取得了骄人的成绩，而那些天资聪颖的，基本都已经是传奇级别的人物了，而我们却在随波逐流的岁月里逐渐沉沦下去，蹉跎至今。我想，以后的子女教育上，或许不一定要让他们成绩多么好，却一定要让他们提早认识社会，寻找自己真正的兴趣所在，提早知道规划自己的人生。

　　前几天同学聚会，见到了很多久未谋面的故友，有位同学的孩子已经四岁，我从未见过如此优秀的四岁孩子。相比于我同事的那些四岁小孩，与我同学的那个孩子相比，说是云泥之别毫不为过。以前只是听说家庭环境对孩子的影响，而这次赤裸裸地看到时，心里的震撼还是难以言表。我因此感谢我的家庭环境，能让一个在大山脚下的路边玩泥巴的孩子一路考到首都去上大学，这已实属不易，同时也深深感到自己与他人的差距，与那些从小就有这样优秀的家庭的人的差距，但愿我能不断修正自己，为将来的孩子营造一个比我的父辈能够给我营造的环境更好的家庭环境吧。