目录
常见的排序算法有四种
1、插入排序：
常见有直接插入排序和希尔排序，插入排序的思想就是，把[0,end]位置的数据看成是有序的，将end+1位置的数据暂存到tmp中，然后让end往前找，一直找到end位置比tmp要小（或者大）。将tmp插入到end的后面。
2、选择排序：
常见有选择排序和堆排序，选择排序的思想就是，一趟排序选出最大/最小值，将它交换到数组的首/尾，然后更新首尾的值
3、交换排序
常见有冒泡排序和快速排序，交换排序的思想就是，每一趟排序将数据交换到它应该处在的位置范围。
4、归并排序
常见有归并排序，归并排序的思想是，将一段数据均匀分成两份，先将这两份进行排序，然后才排序这两份有序序列。
插入排序：
直接插入排序
第一趟插入排序是先让end的值为0（表示[0,0]位置的值是有序的，也就是第一个数据有序），取end后一位的值插入到[0,end]这个有序序列之中，如果tmp的值小于end的值，就让end往前，找到更小的值。退出循环后（要么是end走到前面越界了，要么是end位置比tmp小）将tmp的值赋值给end+1的位置。
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;//end表示[0,end]的位置是有序的
int tmp = a[end + 1];//存起来
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;//end往前找
}
else {
break;
}
}
a[end + 1] = tmp;
}
}如图：黄色部分代表[0,end]的有序序列，绿色部分代表被挤到end+1位置的end的值，红色部分代表需要插入的值。
希尔排序
希尔排序是建立在插入排序的思想之上的排序，它的逻辑更加抽象：
当一个数据是完全倒序的时候，插入排序的时间复杂度就会为O(N^2)，（从1到n-1的等差数列），为了避免这种不利情况，让插入排序更加高效，在进行插入排序之前先进行预排序，使得数据更加接近有序。
如图：设gap为3的时候，由于不会重复预排序同一个位置，所以我们分为三组数据（红、绿、蓝），gap的值由大变小，一直到1。
int gap = 3;
for (int j = 0; j < gap; j++)
{
for (size_t i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}这种写法是将三组（红绿蓝）分开处理了，第一次处理起点为0的组（end从0开始，每次加gap），第二次处理起点为1的组（end从1开始，每次加gap）...
有一种更简单的写法是将相同gap的组同时进行处理：
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;//更新gap
for (int i = 0; i < n - gap; i++)//必须小于n-gap否则会越界
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;//更新end
}
else {
break;
}
}
a[end + gap] = tmp;//tmp始终要插入到end后面一个位置
}
}如图：
这种逻辑就是把0到n-gap-1的位置当做end的起点（end从0开始每次加1），然后保证end小于n-gap，里面的逻辑和上一种写法差不多，都是把它当做一组来预排序，每次end往回退gap个位置，找更小的值。
选择排序：
选择排序
选择排序比较好理解，这里就不画图了，唯一需要注意的一点是，交换最小值和头位置再交换最大值和尾位置的逻辑，如果头位置存放的是最大值的话，此时把它和最小值的位置交换，下次尾位置交换最大值的时候找到的就不是原来的最大值，而是最小值了，所以这里需要判断一下。
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
// 选择排序
void SelectSort(int* a, int n)
{
//从左到右选出最大的和最小的值交换到首尾，更新首尾的值
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
//要是begin位置原本存的是max，这样交换走，原本maxi位置的值就成了最小值
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}堆排序
之前介绍堆的时候有讲过堆排序，堆排序的思想就是选出最大/最小值到堆顶，排升序建大堆，排降序建小堆，将数据交换到堆尾，然后向下调整，并将堆尾往前调。
// 堆排序
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
//找出左右孩子中较大的那个
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapSort(int* a, int n)
{
//先向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
//交换堆顶和堆尾
int end = n - 1;
while (end >= 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}交换排序：
冒泡排序
一趟排序将最大的值交换到末尾，然后接着下一趟排序。如果某一趟冒泡排序一次都没交换过，说明已经有序了可以退出循环。
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}快速排序
快速排序的思想就是，选择一个key值，一趟排序之后能够保证key的左边都是小于它的值，key的右边都是大于它的值，所以我们需要一个begin变量和一个end变量，右边找小，左边找大。
由于最后左右两个指针必然会相遇，我们要将key的值交换到他们相遇的位置，由于我们选择了左边的值作为key，那么他们相遇位置的值必须小于等于key。为此我们必须让右边的先出发，当他们两个相遇的时候，只有两种情况：1、左往前碰到右（此时右站着的位置是刚刚找到的比key小而停下的位置）2、右往前碰到左（此时左站的位置是刚刚右交换给它的比key小的值，或者左干脆在原地没动）。如此一来就能保证相遇位置小于等于key。
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
//选择最左边作为key值，要求一次排序完后keyi左边是小于它的，右边是大于它的
int key = a[left];
int begin = left;//保证能找到left和right
int end = right;
while (begin < end)
{
//右边先出发，因为选择了左边作为key值，所以停下的位置（因为要交换到左边），要小于key值。
//右边找小
while (begin < end && a[end] >= key)
{
end--;
}
while (begin < end && a[begin] <= key)//如果等于不跳过的话，会把开头的位置交换
{
begin++;
}
Swap(&a[begin], &a[end]);
}
//交换停下的位置和key的位置
Swap(&a[left], &a[begin]);
int keyi = begin;
return keyi;
}挖坑法：
如果选择最左边的值作为key，存下这个值，此时这里形成了一个坑位，右边开始找小于key的值填入那个坑位。然后左边找大的值填入右边的坑位。这个写法天然就是右边先开始找。
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int begin = left;
int end = right;
while (begin < end)
{
//右边找大
while (begin < end && a[end] >= key)
{
end--;
}
a[begin] = a[end];
//这里不能写begin++当begin和end相遇时，如果begin++，那么接下来begin就不代表key应该待的位置了
while (begin < end && a[begin] <= key)
{
begin++;
}
a[end] = a[begin];
}
a[begin] = key;
return begin;
}前后指针法：
前指针停在大于key的位置，后指针停在小于key的位置，在cur和prev拉开距离之前，不会进行交换，因为此时prev停的位置还不是大于key的位置。（cur指向位置大于key时，cur走而prev不走，这样就能拉开距离）
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
int key = a[left];
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < key && (prev+1) != cur)//当cur指向的位置的值比key要小，并且cur和prev的距离大于1（没拉开差距说明前面都是小于key的值）
{
perv += 1;
Swap(&a[cur], &a[prev]);
}
cur++;//循环结束是cur走到越界的位置了也没发现下一个比key要小的值，prev此时所处的位置的值小于等于key
}
Swap(&a[prev], &a[left]);
return prev;
}快速排序非递归实现：
利用栈的后进先出的原则，每次出栈的时候入数据，然后取出数据...
快速排序的递归顺序类似二叉树的前序遍历，先操作当前数据，再入栈右树，再入栈左树，出栈的时候自然会先出左树再出右树。出了左树后依然先遍历左树的左树...
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
//快速排序法递归的本质就是每次left和right的值不一样，但是执行的都是partsort（a,left,right)
//如果能用循环的方式，让每一次的left和right是递归执行的顺序，就完成了快速排序的非递归
//快速排序的left和right的顺序就是，[left,right][left,keyi - 1][keyi + 1,right]
// 这里类似前序遍历
//由于每次partsort都返回一个keyi的值，可以循环判断这个值是否满足条件，然后利用栈的后进先出的性质。
//首先创建一个栈
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
}归并排序：
归并排序的思想就是牺牲空间来换取时间，归并排序是个严格的logN*N的时间复杂度，先排序左右两份数据，再排序这些有序的序列。
创建一个临时数组，遍历两组有序数据，从小到大依次写入tmp数组中，再写回原数组。
为此在每次递归的时候，我们都需要知道当前数据的左右边界。为了能够区分当前数据的左右两组，又需要begin1和end1变量，和begin2和end2变量。
void _MergeSort(int* a, int* tmp, int left, int right)
{
if (left >= right)
return;
int mid = (left + right) / 2;//mid应该是(left+right)/2 而不是(right-left)/2
_MergeSort(a, tmp, left, mid);
_MergeSort(a, tmp, mid + 1, right);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
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 + left, tmp + left, sizeof(int)*(right - left + 1));//memcpy计算字节数
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}归并排序的非递归实现
创建一个gap变量，代表此时每一组有几个数据，还是使用begin1和begin2来区分每一组。
遍历每一组数据，将数据从小到大写入tmp数组中，得到有序序列再重新写回原数组。
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;//每组一个数据
while (gap < n)
{
//n个数据归并排序，先按每组为1排序，再按每组为2排序，4,8...
//先写第一趟排序
for (int i = 0; i < n; i += gap * 2)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = end1 + 1, end2 = i + 2 * gap - 1;
//不是什么情况都要排序
if (begin2 >= n)//当第二组数据越界，不用排序了
{
break;
}
if (begin2 < n && end2 >= n)//只是end2越界就调整end2的值
{
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, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
}
计数排序：
计数排序的思想就是，记录每个大小的数据的个数到新的数组中，再遍历新数组取出这些数据。
// 计数排序
void CountSort(int* a, int n)
{
//找出最大值最小值
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int* tmp = calloc((max - min + 1), sizeof(int));
for (int i = 0; i < n; i++)
{
tmp[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < (max - min + 1); i++)
{
while (tmp[i] > 0)
{
a[j++] = i + min;
tmp[i]--;
}
}
}