常用排序算法
分类：技术
选择排序 Selection sort
每次从尚未排好的数组范围里选出一个最小的放到正确的位置。
C 语言版本：
void selection_sort(int array[], int size)
{
int lhs, rhs;
int min;
for (lhs = 0; lhs < size - 1; lhs++) {
min = lhs;
for (rhs = lhs + 1; rhs < size; rhs++) {
if (array[rhs] < array[min])
min = rhs;
}
swap(array, lhs, min);
}
}
C++ 版本：
template <typename Iter, typename Compare>
void selectionSort(Iter begin, Iter end, Compare compare)
{
for (auto iter = begin; iter != end; ++iter) {
std::iter_swap(iter, std::min_element(iter, end, compare));
}
}
快速排序 Quicksort
从数组里选出一个基准元素，通过交换位置让它前面的元素都比它小、后面的元素都比它大，最后分而治之。
C++ 版本：
template <typename Iter, typename Compare>
void quickSort(Iter begin, Iter end, Compare compare)
{
auto distance = std::distance(begin, end);
if (distance > 1) {
auto const pivot = std::next(begin, distance / 2);
std::nth_element(begin, pivot, end, compare);
quickSort(begin, pivot, compare);
quickSort(pivot, end, compare);
}
}
插入排序 Insertion sort
每次从尚未排好的数组范围取出一个元素，放到已排好的数组范围中的正确位置。（现实生活中排序时一般用的就是类似这种算法）
C 语言版本：
void insertion_sort(int array[], int size)
{
int lhs, rhs;
int cur;
for (rhs = 1; rhs < size; rhs++) {
cur = array[rhs];
for (lhs = rhs - 1; (lhs > 0) && (array[lhs] > cur); lhs--)
array[lhs + 1] = array[lhs];
array[lhs] = cur;
}
}
C++ 版本：
template <typename Iter, typename Compare>
void insertionSort(Iter begin, Iter end, Compare compare)
{
for (auto iter = begin; iter != end; ++iter) {
std::rotate(std::upper_bound(begin, iter, *iter, compare),
iter,
std::next(iter));
}
}
堆排序 Heapsort
保持未排数组为堆积树，每次摘取根结点，即可取出当前未排范围中的最大/最小值放入正确位置。
C 语言版本：
void sift_down(int heap[], int root, int end)
{
int l_child = root * 2 + 1;
int r_child = root * 2 + 2;
int max = root; // max heap
if (l_child <= end && heap[l_child] > heap[max])
max = l_child;
if (r_child <= end && heap[r_child] > heap[max])
max = r_child;
if (max != root) {
swap(heap, max, root);
sift_down(heap, max, end);
}
}
void heapsort(int array[], int size)
{
int i;
// from last parent node
for (i = (size - 2) / 2; i >= 0; i--)
sift_down(array, i, size - 1);
for (i = size - 1; i > 0; i--) {
swap(array, 0, i);
sift_down(array, 0, i - 1);
}
}
C++ 版本：
template <typename Iter, typename Compare>
void heapSort(Iter begin, Iter end, Compare compare)
{
std::make_heap(begin, end, compare);
std::sort_heap(begin, end, compare);
}
嗯，基本上常用的就是这些啦~
什么，没有冒泡排序？好吧，我至今都想不明白像冒泡排序这样写起来没有选择排序方便、想起来没有插入排序方便的排序算法是怎么成为教科书中的天字第一号排序算法的。嗯……连奥巴马都知道不能用冒泡排东西。
最后，别忘了还有睡眠排序这样神奇的存在 :)
p.s. 代码里的交换两个元素的值，美观起见就直接写 swap 啦，具体实现随便挑 :)
