1. 冒泡排序：O(N^2)
逻辑解析： 冒泡排序并没有什么实际意义，但是有教学意义，相信大部分小白在学习的初期第一个接触的排序就是冒泡排序。那么接下来我们了解一下他的底层逻辑：
冒泡排序顾名思义就是将最大（小）的值像一个一个小气泡一样逐渐运动到最上层，也就是将一串数字从头开始两两比较，逐步将最值移动到最尾端，最终实现排序。其时间复杂度为O(N^2)。
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//冒泡排序O(N^2)
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
if (a[i] > a[j])
{
Swap(&a[i], &a[j]);
flag = 1;
}
}
//已经排好序，所以第一次遍历没有调整，直接退出
if (flag == 0)
{
break;
}
}
}2. 插入排序：O(N^2)
逻辑解析： 插入排序就是设置一个end，假设区间[0,end]都是有序的，此时取出第end+1个数字插入到前面的有序数列，以此类推，最值end到尾端，此时整个数列就是一个有序数列。时间复杂度为：O(N^2)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//插入排序O(N^2)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
//默认[0,end]的区间是有序的，取a[end+1]插入前面的区间
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
3. 希尔排序：O(N^1.3)
逻辑解析：希尔排序与插入排序的共同点是，希尔排序共进行多次，最后一次时的gap=1，也就是插入排序，在前面的时候先将gap置为n，也就是数组元素个数，这时每次对gap/3后+1，使gap/3递减的同时始终满足gap最小值为1，即保证最后一趟一定是插入排序。在插入排序之前要保证数组分为不相邻的gap组，保证每个组都是有序的，然后在最后一次插入排序使整个数组有序即可。时间复杂度为：O(N^1.3)
//希尔排序O(N^1.3)
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
4. 堆排序：O(N*logN)
逻辑解析：堆排序是基于堆的逻辑结构设计的，所以了解堆排序首先要知道堆的相关知识，详情移步堆的相关知识 ，关于堆排序实质就是对数组的一些操作，即首先根据升（降）序来决定创建大（小）堆，然后生成一个堆。这时就直接将根节点与最后的叶子结点交换，再向下调整即可。即将数组的首尾交换后进行操作。时间复杂度为：O(N*logN)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序O(N*logN)
void HeapSort(int* a, int n)
{
// 降序，建小堆
// 升序，建大堆
// 向上调整建堆 O(N*logN)
// 向下调整建堆 O(N)
//从离叶子结点最近的上一层根节点开始
//n-1代表最末尾的叶子结点，那么((n - 1) - 1) / 2就是该叶子结点的根结点
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
//交换根叶结点后向下调整
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}5. 选择排序： O(N^2)
逻辑解析： 选择排序和冒泡排序一样都没有什么实践意义，同样也没有什么教学意义，所以一般只做了解即可。关于选择排序，大体思路十分简单，就是将最大值与最小值下标都初始置为第一个元素的下标，然后从数组首尾分别向中间遍历，将最大值放在末尾，最小值放在首位，然后缩小遍历区间，再寻找该区间的最大值与最小值，放在两端，以此类推，直到遍历完整个数组即可。
//选择排序
//在[begin,end]范围内选择最值放到两边
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int min = begin;
int max = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
}
if (begin == max)
{
max = min;
}
Swap(&a[begin], &a[min]);
Swap(&a[end], &a[max]);
begin++;
end--;
}
}6. 快速排序（递归实现）：O(N*logN)
1.霍尔方法实现
逻辑解析： 首先讲解一下霍尔发明的排序方法，就是初始时刻将数组最左边的元素置为 key 元素，然后设置两个标识 begin 与 end ，起初 begin 在最左边，end 在最右边，然后向中间遍历，如果 a[begin] 遇到比 a[key] 小的值就向后遍历，同理 a[end] 遇到比 a[key] 大的值就向前遍历，直到遇见不符合的情况，然后将 a[begin] 与 a[end] 交换，直到 begin == end ，这时将 a[key] 与 a[begin] 交换（与 a[end] 也可以） ，目的就是保证 key 元素的左边元素均小于它本身，右边元素都大于它本身，然后递归实现第一次排序后 key 元素的左右部分即可。
//快排的注意一点就是以一个端点为 key 开始端，那么另一个端点就先开始动
//即上述以左边为 key ,就是右边先开始动，直到 begin 和 end 遇见，此时的
//相遇点一定要小于 a[key] 的值
//快速排序优化
void QuickSort(int* a, int left, int right)
{
//当只有一个数字就返回
if (left >= right)
{
return;
}
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
//这里 a+left = a[left]，即从a[left]开始插入排序
InsertSort(a + left, right - left + 1);
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int begin = left;
int end = right;
int key = left;
while (begin < end)
{
//右找小
//从最右边开始找出比a[key]小的值
while (begin < end && a[key] <= a[end])
{
end--;
}
//左找大
//从最左边开始找出比a[key]大的值
while (begin < end && a[key] >= a[begin])
{
begin++;
}
//将左边比a[key]大的与右边比a[key]小的交换
//保证begin == end 的位置左边的数字全部比a[key]小
//同理，右边的数字全部比a[key]大
Swap(&a[begin], &a[end]);
}
//当begin == end ，即两个目标相遇时就交换相遇的位置与a[key]的位置
//然后以新的 key 为割点分为左部分与右部分，再对两部分依次递归
Swap(&a[begin], &a[key]);
key = begin;
//递归实现，使第一次遍历后 key 位置的左右部分有序即可
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
}2. 双指针方法实现
逻辑解析：双指针就是初始化两个指针 cur 与 prev ，初始时刻 prev 指向开头，cur 指向 prev 的下一个位置，设置 key 元素为开头元素。然后 cur 向后遍历，遇到比 key 小的就让 prev++，然后交换 cur 与 prev 元素，遍历到 cur 指向元素末端之后结束，然后交换 prev 与 key 元素，然后递归对 key 元素的左右部分进行排序即可。
//快速排序优化
void QuickSort(int* a, int left, int right)
{
//当只有一个数字就返回
if (left >= right)
{
return;
}
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
//这里 a+left = a[left]，即从a[left]开始插入排序
InsertSort(a + left, right - left + 1);
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int begin = left;
int end = right;
int key = left;
while (begin < end)
{
//右找小
//从最右边开始找出比a[key]小的值
while (begin < end && a[key] <= a[end])
{
end--;
}
//左找大
//从最左边开始找出比a[key]大的值
while (begin < end && a[key] >= a[begin])
{
begin++;
}
//将左边比a[key]大的与右边比a[key]小的交换
//保证begin == end 的位置左边的数字全部比a[key]小
//同理，右边的数字全部比a[key]大
Swap(&a[begin], &a[end]);
}
//当begin == end ，即两个目标相遇时就交换相遇的位置与a[key]的位置
//然后以新的 key 为割点分为左部分与右部分，再对两部分依次递归
Swap(&a[begin], &a[key]);
key = begin;
//递归实现，使第一次遍历后 key 位置的左右部分有序即可
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
}
//单趟排序
int QSort2(int* a, int left, int right)
{
int mid = GetMid(a, left, right);
Swap(&a[left], &a[mid]);
int key = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[key]);
return prev;
}
//快速排序双指针实现形式
void QuickSortDouble(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int key = QSort2(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key, right);
}7. 快速排序（非递归实现）：O(N*logN)
逻辑解析： 虽然是非递归实现，但是其思路还是递归的思路，我们在递归版本的代码实质就是在对待排序数组的某些区间进行操作，所以非递归版本就沿用这个思路，依旧是对待排序数组的区间进行一系列操作，这里是通过栈来实现，即在栈中依次存入 begin 与 end 两个值，这两个值就是初始时刻待排序数组的全部区间，然后进行一趟排序，找到 key 元素，此时要排序的区间就分为了左区间 [begin,key - 1] 与右区间 [key + 1,end]，这时就依次先对右区间再对左区间进行入栈操作，主要是因为栈遵循先进后出的原则，相关文章：暴力数据结构之栈与队列（栈的相关操作）
然后利用 while 循环实现不断分区间的操作即可，大体思路与递归相似。
//快速排序非递归实现（借助栈实现）
//主要是对区间进行操作，逐步二分，相当于深度优先遍历
void QuickSortNR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//取完栈为空，跳出while循环
//单次排序
//其中包含取中操作
int key = QSort2(a, begin, end);
if (key + 1 < end)
{
STPush(&st, end);
STPush(&st, key + 1);
}
if (key - 1 > begin)
{
STPush(&st, key - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
8. 归并排序（递归实现）：O(N*logN)
逻辑解析：归并排序就是首先两两比较再四四比较以此类推，直到排序完成，代码实现的思路是，创建一个新的数组，然后将原数组分为两个区间，左区间与右区间，然后分别对左右区间不断细分直到左右区间都只有一个数据，这时就对他们比较，将较小的值放在新数组，以此类推。概括起来就是不断二分直到不可再分为止，然后利用新开的数组再进行归并，最终实现有序。递归版本是先实现单趟排序的逻辑，再进行递归实现整个数组排序的实现。
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin == end)
{
return;
}
//如果[begin,mid][mid+1,end]有序就直接合并即可
int mid = (begin + end) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
//归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//归并排序（递归实现）时间复杂度:O(N*logN)
//分为左右区间，分别排序再合并到新数组即可
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc error");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}9. 归并排序（非递归实现）: O(N*logN)
逻辑解析： 非递归版本就是首先进行一一比较，即第一个与第二个比较，第二个与第三个比较，以此类推，直到遇见末尾，然后再两两比较，即第一与第二个为一组，第二与第三个为一组，两组之间比较，然后存入新数组中，以此类推直到原数组分组到不可再分，代码实现就是使用 gap 进行分组，然后循环进行比较，注意不能越界，所以在越界时就要进行改正操作，最后排序完毕将新数组中已排序好的数据存入原数组即可。
//归并排序（非递归实现）
void MergeSortNR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc error");
return;
}
//gap表示每一组归并的数据个数
int gap = 1;
while (gap < n)
{
//i表示每次归并的起始位置
for (int i = 0; i < n; i += gap * 2)
{
//[begin1,end1][begin2,end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 第二组都越界不存在，这一组就不需要归并
if (begin2 >= n)
break;
// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
if (end2 >= n)
end2 = n - 1;
//归并左右区间
int j = i;
while (begin1 < end1 && begin2 < end2)
{
//取出较小的值存入新建的数组
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
//如果原区间剩余部分数据则直接尾插入新建数组
while (begin1 < end1)
{
tmp[j++] = a[begin1];
}
while (begin2 < end2)
{
tmp[j++] = a[begin2];
}
//每次排序后都要拷贝一遍
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
