学习总结第三十一天——快速排序与union-find算法

快速排序，听起来很高大上，其实快速排序并不总是能够实现最快的排序。但在大多数情况下，快速排序是一个优秀的排序算法，可以实现O(nlgn)（线性对数级别）的时间复杂度。

快速排序的中心思想，也是分治法，其内容为：在这组数据中选取一个基准，将一组数据中大于这个基准的数作为一组，其余为另一组，再分别对两组数据进行排序。最后就可以得到已排序的数组。
快速排序在开始时，与归并排序一样需要许多额外的空间来分别存放大于基准的数和小于基准的数。后来人们提出了一个改进方法，将其可以成为一个原地算法，于是其优势便得以展现出来了，下面是一个原始版本的快速排序：
#include

using namespace std;

template <typename T> void quick_sort(T *datas, int size)
{
  if (size < 2)
  {
    return;
  }
  T before[size], after[size], mid;//这里创建了两个数组
  int before_index = 0, after_index = 0, index = 0;
  mid = datas[index++];
  while (index<size) {
    if (mid>datas[index])
    {
      before[before_index++] = datas[index++];
    }
    else
    {
      after[after_index++] = datas[index++];
    }
  }
  quick_sort(before, before_index);
  quick_sort(after, after_index);
  index = 0;
  //int i = 0;
  for (int i = 0;i<before_index;i++)
  {
    datas[index++] = before[i];
  }
  datas[index++] = mid;
  for (int i = 0;i<after_index;i++)
  {
    datas[index++] = after[i];
  }
  return;
}

int main(int argc, char const *argv[]) {
  int a[]={234,234,61,12,5,31,6,3,2354,1,1243,63};
  quick_sort(a, sizeof(a)/sizeof(int));
  for (auto i:a)
  {
    std::cout << i << ' ';
  }
  std::cout << std::endl;
  return 0;
}

可以看到这个版本使用了两个数组，导致这个算法要求的空间复杂度很高，于是就有了下面这种原地版本的改进：

template <typename T>void swap(T &a, T&b)
{
  T temp = a;
  a = b;
  b = temp;
}

template <typename T> void quick_sort_inplace(T *datas, int size)
{
  if (size < 2)
  {
    return;
  }
  int before_index = 0;
  int mid = datas[size-1];
  for (int i = 0;i<size-1;i++)
  {
    if (datas[i] > mid)
    {
      swap(datas[before_index++], datas[i]);
    }
  }
  swap(datas[before_index], datas[size-1]);
  quick_sort_inplace(datas, before_index);
  quick_sort_inplace(datas+before_index+1, size-before_index-1);
  return;
}

int main(int argc, char const *argv[]) {
  int a[]={234,234,61,12,5,31,6,3,2354,1,1243,63};
  quick_sort_inplace(a, sizeof(a)/sizeof(int));
  for (auto i:a)
  {
    std::cout << i << ' ';
  }
  std::cout << std::endl;
  return 0;
}

其不同之处就是，并不是使用创建两个新数组的方式来记录比基准大与比基准小的数值，而是选择最后一个数作为基准，然后将较大的值用交换的方法放在数组的前面，并用一个整型变量来记录这个值的大小。下图为一个原地版快速排序的图解：