选择排序 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 啦，具体实现随便挑 :)

4chan 上有个家伙发帖说他发明了一种很牛叉的排序算法：睡眠排序（Sleep Sort）：

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

主要就是对输入的每一个数都新开一个进程，进程里用这个数进行倒数，倒数到0就输出这个数。于是较小数就先输出、较大数后输出。睡排成功～

当然啦群众的眼睛是雪亮的，纷纷指出这个会存在竞态条件，而且如果的数比较大会很悲催（比如要排的数字里有86400的话，那么至少要等86400秒，也就是一整天 =。=），时间复杂度是 O(最大的那个数)……

在这个欢乐的帖子里还看到了各种其它语言对睡眠排序的实现，包括一个 Lua 的（#165）：

#!/usr/bin/env lua
function sleepsort(arr)
    local res, thread = {}, {}
    local nthreads = #arr

    for i = 1, #arr do
        thread[i] = coroutine.create(function()
            for n=arr[i], 0, -1 do coroutine.yield() end
            nthreads = nthreads - 1
            thread[i] = nil
            res[#res+1] = arr[i]
        end)
    end
    while nthreads > 0 do
        for i = 1, #arr do
            if thread[i] then coroutine.resume(thread[i]) end
        end
    end
    return res
end

math.randomseed(os.time())
local arr = {}
for i = 1,10 do arr[i] = math.random(1,99) end
print(unpack(sleepsort(arr)))

嗯哼～ Lua 的 coroutine 还是很强大滴（<ゝω·）

p.s. 终于还是见识到了最无厘头撞大运的 Bogo 排序算法：

while not inOrder(deck) do
    shuffle(deck);