Sorting Algorithms

用到排序算法的时候，还是用STL比较方便，而且能保证最优的O(nlogn)的复杂度。 STL的排序算法sort实现的是快速排序（经过优化的），因此是不稳定的，即是说不能保证相等的元素在排序后仍然保持原始的先后次序。为了实现稳定的排序，需要使用stable_sort，他使用的是归并排序，因此是可以做到稳定的。

vector<T> v;
bool less(const T &t1, const T &t2);
sort(v.begin(), v.end(), less);
stable_sort(v.begin(), v.end(), less);

基于比较的排序算法的复杂度（比较次数）下届为nlogn。因为n个数据的可能排序有n!种，而每一次比较可以将可能性减少一半，因此需要log(n!)次比较，近似为nlogn。

快速排序

快速排序是将某一个元素（通常是第一个，后者最后一个，也可以随机选取一个）作为基准，将待排序数组划分为小于该元素和大于该元素的两部分，然后递归的对两部分进行快速排序。在最坏情形的效率是 $n^2$ ，比如元素本来就是有序的，总选择第一个元素进行划分，每次都会得到最差的划分。

quick_sort(a[], lo, hi)
  if (lo >= hi) then return
  pivot = a[lo]
  p = lo
  for i = lo...hi
    if (a[i] < pivot) then swap(a[i], a[++p])
  end-for
  swap(a[lo], a[p])
  quick_sort(a, lo, p)
  quick_sort(a, p + 1, hi)

归并排序

归并排序是将待排序数组等分为两段，递归的排好两段后，进行合并。因此，该方法有稳定的时间效率，但是要占用额外的线性数量的空间。归并排序通常是不能原地(in-place)完成的，in-place版本的归并排序效率为 $O(n\log^2 n)$ 。

merge_sort(a[], lo, hi)
  if (lo >= hi) then return a[lo...hi]
  m = (lo + hi) / 2
  merge_sort(a, lo, m)
  merge_sort(a, m + 1, hi)
  b = copy(a)
  p = lo
  q = m + 1
  for i = lo...hi
    if (q > hi || b[q] > b[p]) then 
      a[i] = b[p++] 
    else 
      a[i] = b[q++]
    end-if
  end-for

堆排序

堆排序是一种in place的高效排序方式，具有最坏情况O(nlogn)的时间复杂度。堆是一种满二叉树，可以使用数组进行方便的存储和访问。堆有一个约束：每个树节点要大于等于（对于最大堆）它的子节点。维护这个约束的方法叫做下筛(sift down)：假设只有根元素不满足堆约束，那么，就可以逐层向下调整该元素，使得最终堆约束得到满足。这一过程的复杂度是O(log n)，即堆的层数。从数组开始初始化一个堆，只要从堆的底层元素开始，逐层向上进行下筛调整，就可以使得整个堆满足约束。

从堆中弹出根元素（最大堆的最大元素），也仅需要一次调整。即用堆数组的最后一个元素替换根元素，然后进行下筛调整。因此，堆常常被用于高效的优先级队列。利用这个特性，依次将堆中的所有元素弹出，并放置在堆后面，就可以实现排序。

heap_sort(a[])
  n = a.size
  for i = (n - 2) / 2 downto 0
    sift_down(a, i, n)
  end-for
  for i = n - 1 downto 1
    swap(a[0], a[i])
    sift_down(a, 0, i)
  end-for
sift_down(a[], i, n)
  while i <= (n - 2) / 2
    l = i * 2 + 1
    r = i * 2 + 2
    if (a[l] >= a[i] && (r >= n || a[l] >= a[r])) then
      swap(a[l], a[i])
      i = l
    else if (r < n && a[r] >= a[i]) then
      swap(a[r], a[i])
      i = r
    else
      break
    end-if
  end-while

冒泡排序

冒泡排序通过比较和交换相邻元素实现排序。

bubble_sort(a[], n)
  for i = 1...n-1
    for j = 0...n-1-i
      if a[j+1] > a[j] then swap(a[j+1], a[j])
    end-for
  end-for

希尔排序

希尔排序是插入排序的一种。由于插入排序在接近有序的数据上具有较好的性能，因此，希尔排序通过进行有间隔(gap)的插入排序，来逐步将数据调整到有序。间隔通常是一组不断缩小的序列，当缩小为1时，希尔排序就是执行插入排序，但是此时由于数据已经接近有序，因此可以期望有较好的性能。希尔排序的优点是：原地排序，不需要额外的空间（归并需要线性的空间，快速排序需要对数级别的栈空间），实现的代码比较简单。

shell_sort(a[], n)
  gaps = [701, 301, 132, 57, 23, 10, 4, 1]
  for gap in gaps
    for i = gap...n-1
      temp = a[i]
      j = i
      while (j >= gap && a[j - gap] > temp)
        a[j] = a[j - gap]
        j = j - gap
      end-while
      a[j] = temp
    end-for
  end-for

桶排序和基数排序

桶排序的方法是先将数据按照顺序大致分在若干桶里面，然后对桶内的数据再执行排序。如果桶的数量是2，桶内递归的执行桶排序，那么就演变为快速排序。

基数排序主要用于排序字符串或者表示为字符串的整数。排序的方法是逐位数字执行桶排序。