排序算法的简介
排序算法 （英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。
排序算法的稳定性：稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。一般来说，我们所说的稳定性是以比较为排序底层原理的。如对考试成绩进行排序，张三的成绩与李四的成绩一样，但是原本张三排在李四的前面。如果用稳定的排序算法排序，那么排序完成之后张三还是在李四的后面。但是 ，如果用不稳定的排序算法排序，那么排序完成之后张三有可能排到李四的后面。比如我们常说的sort，他的底层算法就是快速排序，快速排序就是一种不稳定的排序算法
在常见的排序算法里的稳定排序算法有：基数排序、计数排序、插入排序、冒泡排序、归并排序。
不稳定的排序算法有：选择排序、堆排序、快速排序、希尔排序。
下面是排序各种常见排序算法的简介：
- 选择排序
选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素，然后将这个元素与数组第 i 个位置上的元素交换。
稳定性：不稳定
时间复杂度：最坏情况 O(n^2)
样例代码
void selection_sort(int* a, int n) {
for (int i = 1; i < n; ++i) {
int ith = i;
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[ith]) {
ith = j;
}
}
std::swap(a[i], a[ith]);
}
}
- 冒泡排序
冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。
稳定性：稳定
时间复杂度：最坏情况下 O(n^2)
样例代码
// 假设数组的大小是 n + 1，冒泡排序从数组下标 1 开始
void bubble_sort(int *a, int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
- 插入排序
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
稳定性：稳定
时间复杂度： O(n^2)
样例代码：
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
- 计数排序（不是基数排序）
计数排序（英语：Counting sort）是一种线性时间的排序算法。
就是用一个数组累计出每个数字出现的个数，最后输出答案。
稳定性：稳定
时间复杂度： 0(n)
样例代码：
const int N = 100010;
const int W = 100010;
int n, w, a[N], cnt[W], b[N];
void counting_sort() {
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) ++cnt[a[i]];
for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}
- 基数排序
基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为 k 个关键字，逐一对各个关键字排序后完成对所有元素的排序。
如果是从第 1 关键字到第 k 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；
如果是从第 k 关键字到第 1 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。
对数字排序
#include <algorithm>
#include <stack>
#include <tuple>
#include <vector>
using std::copy; // from <algorithm>
using std::make_tuple;
using std::stack;
using std::tie;
using std::tuple;
using std::vector;
typedef unsigned int u32;
typedef unsigned int* u32ptr;
void MSD_radix_sort(u32ptr first, u32ptr last) {
const size_t maxW = 0x100000000llu;
const u32 maxlogW = 32; // = log_2 W
const u32 W = 256; // 计数排序的值域
const u32 logW = 8;
const u32 mask = W - 1; // 用位运算替代取模，详见下面的 key 函数
u32ptr tmp =
(u32ptr)calloc(last - first, sizeof(u32)); // 计数排序用的输出空间
typedef tuple<u32ptr, u32ptr, u32> node;
stack<node, vector<node>> s;
s.push(make_tuple(first, last, maxlogW - logW));
while (!s.empty()) {
u32ptr begin, end;
size_t shift, length;
tie(begin, end, shift) = s.top();
length = end - begin;
s.pop();
if (begin + 1 >= end) continue; // elements <= 1
// 计数排序
u32 cnt[W] = {};
auto key = [](const u32 x, const u32 shift) { return (x >> shift) & mask; };
for (u32ptr it = begin; it != end; ++it) ++cnt[key(*it, shift)];
for (u32 value = 1; value < W; ++value) cnt[value] += cnt[value - 1];
// 求完前缀和后，计算相同关键字的元素范围
if (shift >= logW) {
s.push(make_tuple(begin, begin + cnt[0], shift - logW));
for (u32 value = 1; value < W; ++value)
s.push(make_tuple(begin + cnt[value - 1], begin + cnt[value],
shift - logW));
}
u32ptr it = end;
do {
--it;
--cnt[key(*it, shift)];
tmp[cnt[key(*it, shift)]] = *it;
} while (it != begin);
copy(tmp, tmp + length, begin);
}
}
对字符串排序
#include <algorithm>
#include <stack>
#include <tuple>
#include <vector>
using std::copy; // from <algorithm>
using std::make_tuple;
using std::stack;
using std::tie;
using std::tuple;
using std::vector;
typedef char* NTBS; // 空终止字节字符串
typedef NTBS* NTBSptr;
void MSD_radix_sort(NTBSptr first, NTBSptr last) {
const size_t W = 128;
const size_t logW = 7;
const size_t mask = W - 1;
NTBSptr tmp = (NTBSptr)calloc(last - first, sizeof(NTBS));
typedef tuple<NTBSptr, NTBSptr, size_t> node;
stack<node, vector<node>> s;
s.push(make_tuple(first, last, 0));
while (!s.empty()) {
NTBSptr begin, end;
size_t index, length;
tie(begin, end, index) = s.top();
length = end - begin;
s.pop();
if (begin + 1 >= end) continue; // elements <= 1
// 计数排序
size_t cnt[W] = {};
auto key = [](const NTBS str, const size_t index) { return str[index]; };
for (NTBSptr it = begin; it != end; ++it) ++cnt[key(*it, index)];
for (char ch = 1; value < W; ++value) cnt[ch] += cnt[ch - 1];
// 求完前缀和后，计算相同关键字的元素范围
// 对于 NTBS，如果此刻末尾的字符是 \0 则说明这两个字符串相等，不必继续迭代
for (char ch = 1; ch < W; ++ch)
s.push(make_tuple(begin + cnt[ch - 1], begin + cnt[ch], index + 1));
NTBSptr it = end;
do {
--it;
--cnt[key(*it, index)];
tmp[cnt[key(*it, index)]] = *it;
} while (it != begin);
copy(tmp, tmp + length, begin);
}
free(tmp);
}
- 快速排序
快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法。
快速排序的工作原理是通过 分治 的方式来将一个数组排序。
快速排序分为三个过程：
1.将数列划分为两部分（要求保证相对大小关系）；
2.递归到两个子序列中分别进行快速排序；
3.不用合并，因为此时数列已经完全有序。
和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。
之后，维护一前一后两个指针 p 和 $q$，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。
其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都有不止一种实现方法。
第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。