0. 交换两个变量中的值(辅助函数)
最简单的，利用一个临时变量：
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
还有其他办法么？答案是使用异或(XOR或^)。但是为什么呢？
假设a为二进制数01，b为二进制数10，a^b的结果为11并将其存储在变量c中。
11^01=10
11^10=01
// 转换成我们的变量
c^a = b;
c^b = a;
我们发现，将两数异或的结果与其中一数再进行异或，可以得到另一个数。
原理：两数异或的结果保存了两个数上每一个二进制位不同或相同的信息。如果相应的二进制位不同，就标志为1，如果相同，则标志为0。
a和c进行异或，相当于把c中和a相同的部分抵消掉，就可以得到b。
b和c进行异或，相当于把b中和a相同的部分抵消掉，就可以得到a。
void swap(int *a, int *b)
{
int c = *a ^ *b;
*a = c ^ *a;
*b = c ^ *b;
}
但代码上看着还是需要一个临时变量？
简单分析一下，就可以发现，c中信息丰富，可以说保存了a和b的信息，我们可以把a变成c，信息是没有损失的。
void swap(int *a, int *b)
{
*a = *a ^ *b; // 相当于c，保存了a和b的信息
*b = *a ^ *b; // 相当于c^b，可以得到a
*a = *a ^ *b; // 虽然看着是a^b，但现在a=c，b=a，实际是c^a，可以得到b
}
当然，如果你很骚(想装逼)，也可以写得更简洁：
void swap(int *a, int *b)
{
*a^=*b^=*a^=*b;
}
1. 冒泡排序
核心思想：
把最后的位置留给最大元素。下次循环的时候就可以少遍历一个数。
通过不断交换，把较大的数往后挪。
过程：
- 从头开始遍历，结束遍历的时候，末尾的就是最大的元素。
- 下一个最大元素只需要从n-1个数字中确定，再从n-2个数字中确定，...，最后到0。
- 当前元素 > 后一个元素，则交换两个元素位置，最大元素就后移了。
- 也就是说，每次遍历较大的数字一定会逐渐后移。但遇到更大的数时，更大的数开始后移，所以最后一定是最大的数放在最后。
void BubbleSort(int *arr, int n)
{
for (int i = n - 1; i > 0; i--) // 预留位置索引
for (int j = 0; j < i; j++) // 当前元素和后一个元素比较，预留索引的比较通过j+1实现
if (arr[j] > arr[j+1]) // 当前元素 > 后一个元素，则交换两个元素位置，最大元素就后移了。
swap(&arr[j], &arr[j+1]);
}
2. 选择排序
核心思想：
把最前面的位置留给最小元素。下次循环的时候就可以少遍历一个数。
找到目标索引，最后进行交换。
过程：
- 从当前位置开始到最后一个元素，找到最小的元素索引。
- 找到最小元素的索引，如果和当前位置不一样，就交换两个元素。
void SelectionSort(int *arr, int n)
{
int i, j, idx;
for (i = 0; i < n - 1; i++) { // 预留位置索引
// 1.从当前位置开始到最后一个元素，找到最小的元素索引
idx = i;
for (j = i + 1; j < n; j++) // 当前位置不用比较，从下一个位置开始
if (arr[j] < arr[idx])
idx = j;
// 2.找到最小元素的索引，如果和当前位置不一样，就交换两个元素
if (idx != i)
swap(&arr[i], &arr[idx]);
}
}
2.1 比较冒泡和选择排序
都是预留一个位置给目标元素，但是又有些不同。
冒泡排序会不断交换元素。
选择排序只会在最后判断是否需要交换。
当然预留位置是最前还是最后都可以实现对应的算法。
比如冒泡算法，如果预留的位置是最前也可以做，但可能就不叫冒泡算法了。
冒泡算法：水中底部压力大，气泡较小，随着气泡上升，压力变小，气泡变大。
void BubbleSort2(int *arr, int n)
{
for (int i = 0; i < n - 1; i++) // 预留位置索引
for (int j = n - 1; j > i; j--) // 当前元素和前一个元素比较，结束位置为预留位置的后一个位置
if (arr[j] < arr[j-1]) // 当前元素 < 前一个元素，则交换两个元素位置，最小元素就前移了。
swap(&arr[j], &arr[j-1]);
}
同样，选择排序也可以预留最后的位置。
void SelectionSort2(int *arr, int n)
{
int i, j, idx;
for (i = n - 1; i > 0; i--) { // 预留位置索引
// 1.从最后一个元素开始向前查找，找到最大的元素索引
idx = i;
for (j = i - 1; j >= 0; j--) // 当前位置不用比较，从前一个位置开始
if (arr[j] > arr[idx])
idx = j;
// 2.找到最大元素的索引，如果和当前位置不一样，就交换两个元素
if (idx != i)
swap(&arr[i], &arr[idx]);
}
}
3. 插入排序
类似于链表的头插法，我们把数组分为已排序部分和未排序部分。
你可以想象你正在摸扑克牌，你现在手中有一张拍，然后继续摸牌，摸牌的同时对你手中的牌进行排序(插入到合适的位置)。
- 第一张牌，索引0不需要排序。
- 继续摸牌，找到合适的位置i，将i后的牌后移。(给这张牌滕出位置)
- 插入摸到的这张牌。
void InsertionSort(int *arr, int n)
{
int i, j, tmp;
for (i = 1; i < n; i++) { // 第一张牌，索引0不需要排序，直接跳过从1开始
tmp = arr[i]; // 摸到的下一张牌，即未排序部分的开头
for (j = i; j >= 1 && arr[j-1] > tmp; j--) // 从后往前遍历，将更大的牌后移(前面的是排序过的，是从小到大排列的)
arr[j] = arr[j-1];
arr[j] = tmp; // 循环将比摸到的牌更大的牌后移了，结束的位置就是插入牌的位置
}
}
4. 希尔排序
其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。
插入排序过程中：
- 如果新摸到的是较大的牌，不需要滕位置，或者只需要滕很少的位置，就行了。
- 如果新摸到的是较小的牌，每次要滕位置的时候，只能一个位置一个位置地挪，是非常低效的。
希尔排序通过增量进行了分组(分治)，比较的是arr[j-increment]和arr[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。
- 也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。
void ShellSort(int *arr, int n)
{
int i, j, tmp, increment;
for (increment = n/2; increment > 0; increment /= 2) { // 增量变化
for (i = increment; i < n; i++) { // 增量是increment，不同增量分组时，第一张摸到的牌
tmp = arr[i]; // 摸到的下一张牌，即未排序部分的开头
for (j = i; j >= increment && arr[j - increment] > tmp; j -= increment) // 从后往前遍历，将更大的牌后移(前面的是排序过的，是从小到大排列的)
arr[j] = arr[j - increment];
arr[j] = tmp; // 循环将比摸到的牌更大的牌后移了，结束的位置就是插入牌的位置
}
}
}
当increment等于1的时候就和插入排序一模一样了。
需要注意的是：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
5. 堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为，它也是不稳定排序。
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
或者
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
如下图：
大顶堆、小顶堆
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：
数组表示
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆： arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆： arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是：
- 用待排序序列构造一个大顶堆。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
- 如此反复执行，便能得到一个有序序列了。
我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：
利用堆结构特性，不断选出最大值，放到最后。
// 左儿子索引
#define LeftChild(i) (2 * (i) + 1)
/// 为目标节点找到合适的位置
/// @param arr 数组
/// @param i 当前要调整的节点索引
/// @param n 节点总数
void FormatHeap(int *arr, int i, int n) {
int child, tmp;
tmp = arr[i]; // 目标节点
for (; LeftChild(i) < n; i = child) { // 从当前节点开始，不断遍历子节点
child = LeftChild(i); // 获取左儿子
// 左儿子如果是n-1就没有右儿子了，右儿子如果比左儿子大，就选右儿子
if (child != n-1 && arr[child + 1] > arr[child])
child++;
// 如果子节点比目标节点大，则子节点上移覆盖父节点，滕出位置给目标节点，否则结束排序
if (tmp < arr[child])
arr[i] = arr[child];
else
break;
}
arr[i] = tmp; // 当前节点填入目标节点
}
void HeapSort(int *arr, int n) {
int i;
// 通过可能有值的父节点n/2-1开始，倒序遍历所有子节点
// 也就是说，先排好下层节点，再排上层节点，所以FormatHeap的内遍历深度只会向下1层
for (i = n/2 - 1; i >= 0; i--)
FormatHeap(arr, i, n);
// 构建好大顶堆后开始排序
for (i = n-1; i > 0; i--) { // 预留位置索引(最后)
swap(&arr[0], &arr[i]); // 将堆顶的最大元素，和预留位置元素交换
// 现在只有栈顶的元素没有被放到合适的位置，所以是0
// 预留位置已经填入了合适的值，所以总的个数现在是预留位置索引
FormatHeap(arr, 0, i);
}
}
6. 归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。
将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。
归并排序
进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。
6.1 递归写法
/// 治，缝合，把结果存入b数组
/// @param a 数组a
/// @param b 数组b
/// @param lb 左边开始的索引
/// @param center 中间的索引
/// @param rEnd 结束的索引
void Merge(int *a, int *b, int lb, int center, int rEnd)
{
int i, rb, count;
i = lb; // 遍历开始
rb = center + 1; // 右边开始的索引
count = rEnd - lb + 1; // 缝合需要缝合的总数
while (lb <= center && rb <= rEnd) // 把两个部分按大小存入临时数组b
if (a[lb] < a[rb])
b[i++] = a[lb++];
else
b[i++] = a[rb++];
while (lb <= center) // 如果左半部分还有剩，则全部接到数组b后面
b[i++] = a[lb++];
while (rb <= rEnd) // 如果右半部分还有剩，则全部接到数组b后面
b[i++] = a[rb++];
for (int i = 0; i < count; i++, rEnd--) // 将b中的结果，回填到数组a中
a[rEnd] = b[rEnd];
}
/// 分治
/// @param a 数组a
/// @param b 数组b
/// @param l 开始索引
/// @param r 结束索引
void RecursionMergeSort(int *a, int *b, int l, int r)
{
if (l < r) { // 递归结束条件，结束时每个元素都变成单个的了
int center = (l + r) >> 1 // 找到中心位置
RecursionMergeSort(a, b, l, center); // 分成左半部分
RecursionMergeSort(a, b, center + 1, r); // 分成右半部分
Merge(a, b, l, center + 1, r); // 合并
}
}
void MergeSort(int *arr, int n)
{
int *b = malloc(n * sizeof(int)); // 临时数组，用于存放缝合结果
if (b) {
RecursionMergeSort(arr, b, 0, n-1);// 分治
free(b);
}
else
FatalError("No space for temp array!")
}
6.2 循环写法
/// 治，缝合，把结果存入b数组
/// @param a 数组a
/// @param b 数组b
/// @param lb 左边开始的索引
/// @param center 中间的索引
/// @param rEnd 结束的索引
void Merge(int *a, int *b, int lb, int center, int rEnd)
{
int i, rb, count;
i = lb; // 遍历开始
rb = center + 1; // 右边开始的索引
count = rEnd - lb + 1; // 缝合需要缝合的总数
while (lb <= center && rb <= rEnd) // 把两个部分按大小存入临时数组b
if (a[lb] < a[rb])
b[i++] = a[lb++];
else
b[i++] = a[rb++];
while (lb <= center) // 如果左半部分还有剩，则全部接到数组b后面
b[i++] = a[lb++];
while (rb <= rEnd) // 如果右半部分还有剩，则全部接到数组b后面
b[i++] = a[rb++];
for (int i = 0; i < count; i++, rEnd--) // 将b中的结果，回填到数组a中
a[rEnd] = b[rEnd];
}
void LoopMergeSort(int *a, int *b, int n)
{
int i, l, center, r, size;
size = 1; // 每组里面的元素数量
while (size < n) {
for (i = 0; i < n;) {
l = i; // 左边开始索引
center = l + size - 1; // 中点索引
r = center + size; // 右边结束索引
r = r < n - 1 ? r : n - 1; // 右边部分可能没有那么多
Merge(a, b, l, center, r); // 合并两个部分
i = r + 1; //下一组的开始索引
}
size *= 2; // 合并的总大小翻倍
}
}
void MergeSort(int *arr, int n)
{
int *b = malloc(n * sizeof(int)); // 临时数组，用于存放缝合结果
if (b) {
LoopMergeSort(arr, b, n);
free(b);
}
else
FatalError("No space for temp array!")
}
7. 快速排序
快速排序是对冒泡排序的一种改进。
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序过程：
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
- 此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
7.1 递归写法
int QuickSortKeyIndex(int *arr, int left, int right)
{
int i = left; // 开始的索引
int j = right; // 结束的索引
int key = arr[left]; // 分界值
while (i < j) { // 把比分界值大的放右边，比分界值小的放左边
while (i < j && key <= arr[j]) //从右往左，跳过比分界值大的部分
j--;
arr[i] = arr[j]; // 把比分界值小的值放到i对应的索引
while (i < j && key >= arr[i]) //从左往右，跳过比分界值小的部分
i++;
arr[j] = arr[i]; // 把比分界值大的值放到j对应的索引
}
arr[i] = key; // 在组内找完一遍以后就把分界值key回归
return i;
}
void RecursionQuickSort(int *arr, int left, int right)
{
if (left < right) { // 递归结束条件
int i = QuickSortKeyIndex(arr, left, right); // 确定分界值的位置，然后分界值不再参与排序
RecursionQuickSort(arr, left, i - 1); // 分为左半部分再来一遍
RecursionQuickSort(arr, i + 1, right); // 分为右半部分再来一遍
}
}
void QuickSort(int *arr, int n) {
RecursionQuickSort(arr, 0, n-1);
}
7.2 循环写法
利用栈结构辅助，将栈帧记录的数据，存入自己的栈结构。
int QuickSortKeyIndex(int *arr, int left, int right)
{
int i = left; // 开始的索引
int j = right; // 结束的索引
int key = arr[left]; // 分界值
while (i < j) { // 把比分界值大的放右边，比分界值小的放左边
while (i < j && key <= arr[j]) //从右往左，跳过比分界值大的部分
j--;
arr[i] = arr[j]; // 把比分界值小的值放到i对应的索引
while (i < j && key >= arr[i]) //从左往右，跳过比分界值小的部分
i++;
arr[j] = arr[i]; // 把比分界值大的值放到j对应的索引
}
arr[i] = key; // 在组内找完一遍以后就把分界值key回归
return i;
}
void LoopQuickSort(int *arr, int n)
{
int top = -1;
int *stack = (int *)malloc(sizeof(int) * (n + 4));
stack[++top] = 0;
stack[++top] = n - 1;
int left, i, right;
while (top > -1) {
right = stack[top--];
left = stack[top--];
i = QuickSortKeyIndex(arr, left, right);
if (left < i-1){
stack[++top] = 0;
stack[++top] = i-1;
}
if (i+1 < right) {
stack[++top] = i+1;
stack[++top] = right;
}
}
}
void QuickSort(int *arr, int n) {
LoopQuickSort(arr, n);
}
