【数据结构初阶八大排序】---冒泡、选择、插入、希尔、堆排、快排、归并、计数
常见的七大排序算法
1.冒泡排序
冒泡排序的思路是：
- 从数列的第一个元素开始，依次对相邻的两个元素进行比较。如果对于升序排序，前一个元素大于后一个元素(或对于降序排序，前一个元素小于后一个元素 )，就交换这两个相邻元素的位置。
- 对数列中的每一对相邻元素都执行上述比较和交换操作，这样经过一轮比较交换后，数列中最大（升序时）或最小（降序时）的元素就会“浮”到数列的末尾。
- 重复步骤1和步骤2，但每一轮比较时，参与比较的元素个数会依次减少1（因为上一轮已经把最大或最小的元素移到了合适位置，无需再参与比较）。
- 持续进行上述操作，直到整个数列都有序，即没有元素需要交换位置为止。
（2个数的数组需要走一趟，n个数的数组需要走n-1趟）
动图如下：
参考代码如下：
//冒泡排序（升序）
void BubbleSort(int* arr, int n)
{
for (int j = 0; j < n - 1; j++)
{
//flag用于做标记
int flag = 0;
//i=n-1,i+1=n
for (int i = 0; i < n - 1 - j; i++)
{
if (arr[i] > arr[i + 1])
{
//交换
Swap(&arr[i], &arr[i + 1]);
flag = 1;//这一趟有进行交换，标记赋值为1
}
}
//如果标记依旧为0，说明这一趟没有进行交换，即数组有序
if (flag == 0)
break;
}
}
通过以上代码我们会发现在最坏的情况下冒泡排序的执行次数是(n-1)+(n-2)+…+2+1,总共也就是n^2/2-n/2,所以时间复杂度是O(N*N)，我们这里也并没有额外开很多空间，所以空间复杂度是O(1)
最好的情况也就是待排序序列已经是有序序列了，此时我们循环执行的此时仅为n-1次，因此冒泡排序的时间复杂度在最好的情况下是O(N),不过这种情况概率极低。
2.选择排序
选择排序的思路是：
1.选择排序会将整个待排序序列分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个序列。
2.每一轮排序会从未排序部分中找出最小（升序排序）或最大（降序排序）的元素，然后哦将其与未排序部分的第一个元素交换位置，这样子未排序部分一个元素就加入到了未排序部分，未排序部分的元素数量-1。
3.重复这个过程，直到未排序部分为空，此时整个序列就完成了排序
动图如下：
当然这是传统的选择排序的思想，我这里会将其稍微优化一下，从上面这个动图上我们看到每一轮排序只会选出最小的元素，然后将其与左侧的元素位置进行交换，这样子每次未排序部分的元素数量只-1。
我们将其优化一下，每一轮排序我们选出两个未排序元素，一个是未排序部分中最小的元素，一个是未排序部分中最大的元素，然后将两者分别与两侧元素的位置进行交换，这样子我们的效率就变成了原先的两倍。
参考代码如下：
//选择排序（升序）
void SelectSort(int* arr, int n)
{
//最左侧和最右侧元素下标
int left = 0;
int right = n - 1;
while (left < right)
{
int mini = left;
int maxi = left;
//[left,right]
for (int i = left + 1; i <= right; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[left], &arr[mini]);
//因为先把最小的放到左边，但如果左边的是最大的数，这样交换完后，maxi下标原本所指向的数据跑到mini下标处了
if (maxi == left)
{
maxi = mini;
}
Swap(&arr[right], &arr[maxi]);
left++;
right--;
}
}
通过以上代码我们可以计算出选择排序的运算次数为：n/2，所以选择排序的时间复杂度是O(N^2),同样我们没有额外创建很多空间，因此空间复杂度是O(1)
但我们会发现因为选择排序每次都只选出1或2个元素，并不关心序列是否依然有序，所以选择排序在任何情况下的时间复杂度皆为O(N)
3.插入排序
插入排序的思想是：
1.插入排序把待排序的序列分成两部分：已排序部分和未排序部分。初始时，已排序部分只包含序列最左侧的一个元素，未排序部分包含其余元素。
2.接着，我们从未排序部分中依次取出元素并插入到已排序部分中的合适位置，使得排入元素后已排序部分的元素依旧有序。
3.不断重复第2个操作直到未排序部分为空，此时整个序列就完成了排序。
动图如下：
参考代码如下：
//插入排序（升序）
void InsertSort(int* arr, int n)
{
//i=n-1时，end+1=n越界
for (int i = 0; i < n - 1; i++)
{
int end = i;
int temp = arr[end + 1];
while (end >= 0 && arr[end] > temp)
{
arr[end + 1] = arr[end];
--end;
}
arr[end + 1] = temp;
}
}
通过以上代码我们可以得出插入排序在最坏的情况下的执行次数为:1+2+3+…+(n-2)+(n-1),即n^2/2-n/2，因此插入排序的时间复杂度是O(N*N),不过插入排序每一轮都将元素插入已排序部分最左侧的概率很小，所以其实际效率是小于N方的，同样空间复杂度为O(1)
4.希尔排序
希尔排序是对插入排序的改进，希尔排序的思想是：
1.定义了一个增量gap，初始时gap较大，假如待排序序列的元素个数为n，则初始增量gap = n / 3 + 1
2.接着我们按增量对待排序序列进行分组，一共gap组，然后对每组使用插入排序使其有序。
如下图，我们假设gap=3，每种颜色为一组，每组相邻的两个元素在原序列中的间隔为gap，然后我们分出了图中3组增量数组：{2，1，6}，{5，2，8}，{7，3}
3.不断缩小增量gap (gap = gap / 3 + 1)，然后继续重复步骤2，让序列逐渐有序
4.增量gap=1时，对整体进行普通的插入排序即可完成排序。
希尔排序的优点
希尔排序虽然是依靠插入排序进行实现的，但其效率却远高于插入排序。
我们先来说说插入排序，以下图为例，如果我们使用插入排序进行排序，如果我们想让下方序列变为升序，我们就要将0放置到第一个位置，但依照插入排序的思想，我们需要往前一个一个进行比较，那么假如我们有n个数，我们想将最后一个元素放入第一个元素的位置我们将比较n-1次。
如果我们使用的是希尔排序，我们假设gap=3，0所在的一组的是不是{5，0}，那么我们想让这一组有序是不是只用比较1次就变成了{0，5}，虽然0依旧没有放入合适位置，但我们发现它距离合适位置是不是很近。
也就是说希尔排序相较于插入排序的优点是：运行元素在较大间隔上进行比较交换，能让元素快速移动到接近其最终位置，减少了元素移动和比较的次数，从而提高了排序效率。
参考代码如下：
//希尔排序（升序）
void ShellSort(int* arr, int n)
{
int gap = n;
//gap=1时就相当于插入排序
while (gap > 1)
{
//gap=2时，gap = gap / 3 + 1 = 1,此时相当于插入排序
gap = gap / 3 + 1;
//i=n-gap,end=n-gap,end+gap=n
for (int i = 0; i < n - gap; i++)
{
int end = i;
int temp = arr[end + gap];
//升序
while (end >= 0 && arr[end] > temp)
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = temp;
}
}
}
希尔排序的时间复杂度很难进行计算，其时间复杂度大约是O(N^1.3)，其空间复杂度是O(1)
其大概计算如下：
1.假设初始gap = n / 3，我们忽略+1（方便计算）
2.这样初始每组元素个数 = n / gap = 3
3.最坏情况下，第一趟预排序的消耗是(1 + 2) * n/3 , 即比较次数之和×组数
4.第二趟时，组数 = n / 9， 每组9个元素，最坏情况下预排序的消耗是(1 + 2 + 3 + …+ 8) * n / 9 = 4*n
…
5.最后一趟，gap = 1，此时序列已经很接近有序了，就相当于直接插入排序的消耗：大约是n
6.然后我们将这些消耗加起来，最后得出时间复杂度大约O(N^1.3)
5.堆排序
堆排序的思想是：
升序：建大堆，降序：建小堆。
以升序为例子，堆其实就是一颗二叉树，大堆的任意一个节点，其孩子节点的值都小于自己，也就是说大堆的堆顶元素是所有节点中值最大的。
所以我们的思想是：
1.我们将大堆的堆顶元素与堆的最后一个元素进行交换。（如下图）
那我们是不是就相当于将最大的元素放入了合适的位置,这个元素也就进入了已排序部分，其余的元素属于未排序部分。
2.交换完后我们这个堆不是大堆，我们要将堆顶元素进行向下调整，然后形成新的大堆。
3.形成新的大堆后，堆顶元素又是未排序部分的最大元素，我们重复步骤1、2，直到堆变成空堆，排序也就完成了
如果对堆和二叉树不熟悉的可以前往小编之前写的一篇博客中进行了解，链接如下：
链接: 二叉树和堆
参考代码如下：
//向下调整
void AdjustDown(int* arr, int n, int parent)//parent是父亲节点下标
{
//假设法，先假设左孩子是较大的那个
int child = parent * 2 + 1;
//child>n,说明没有孩子了
while (child < n)
{
//右孩子存在
if (child + 1 < n && arr[child + 1] > arr[child])
{
++child;
}
if (arr[parent] < arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
//arr[parent] >= arr[child],排好了
else
{
break;
}
}
}
//堆排序（升序）
void HeapSort(int* arr, int n)
{
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
//升序，建大堆
AdjustDown(arr, n, i);//元素个数，父亲节点下标
}
int end = n - 1;
while (end > 0)
{
//交换首尾元素,然后将第一个元素向下调整
Swap(&arr[0], &arr[end]);//end是最后一个元素下标
AdjustDown(arr, end, 0);//end是元素个数
--end;
}
}
6.快速排序
6.1快速排序(hoare版本)
hoare版本的快速排序的思想是：
hoare版本的快速排序，其核心在于选择一个基准值（key），以升序为例，通过一趟排序使得基准值左边部分的所有元素小于基准值，右边部分的所有元素大于或等于基准值，然后递归对左右两部分进行相同步骤排序，最终整个序列有序。
具体步骤：
1.设置一个基准值（key），通常是序列最左边的元素。
2.设置两个标记变量，一个变量left指向序列的第一个元素，另一个变量right指向序列的最后一个元素。
3.移动标记：以升序为例，right先向左移动寻找比key小的元素，找到后停下，在right找到合适的元素后，left开始向右移动寻找比key大的元素，找到后停下。
4.交换两标记变量的元素，left和right都找到合适元素后交换left和right的值。
5.重复步骤3、4，直到left和right相遇，相遇后交换key和相遇点的元素。
6.此时序列被分成三个区域：[0,key-1]key[key+1,end],使用递归将key左右的两个区域进行相同步骤使其有序。
动图如下：
参考代码如下：
//快速排序
void QuickSort1(int* arr, int left, int right)
{
//区域中只有一个元素或者区域不存在
if (left >= right)
return;
int key = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边找小
while (begin < end && arr[end] >= arr[key])
{
end--;
}
//左边找大
while (begin < end && arr[begin] <= arr[key])
{
begin++;
}
//找到后交换
Swap(&arr[begin], &arr[end]);
}
//begin和end相遇，交换key与相遇位置
Swap(&arr[key], &arr[begin]);
key = begin;
//区间变成[left,key-1],key[key+1,right]
QuickSort1(arr, left, key - 1);
QuickSort1(arr, key + 1, right);
}
三数取中
上面代码有个缺陷，就是如果序列近似有序序列的时候，程序会栈溢出，为什么呢？
我们都知道函数递归会创造栈帧，递归过多会导致栈溢出，如果序列近似有序的时候会出现以下情况：
我们看到如果是有序序列的时候，right一直先左移动寻找合适的元素，但是直到与left相遇依旧没有找到，然后就是不断的递归，递归后right依旧会一直向左移动寻找合适元素，但是结果是相同的，最终因为递归一直进行着又没有销毁导致栈溢出。
为了尽可能避免以上情况的发生，我们要想出一个解决办法，出现这个问题的原因是是基准值（key）选的不对，导致最左侧元素是最大值或者最小值，因此我们想出了一个办法，这个办法就是三数取中。
我们从序列左侧元素、右侧元素以及中间元素着三个元素中找到大小处于中间的那个元素，然后将这个元素与序列最左侧元素进行交换，这时候我们再将左侧元素作为基准值的时候就尽可能的避免了其是最大值或者最小值的可能性。
参考代码如下：
//三数取中
int GetMidi(int* arr, int left, int right)
{
int mid = (left + right) / 2;
if (arr[left] < arr[mid])
{
//arr[left] < arr[mid] <arr[right]
if (arr[mid] < arr[right])
{
return mid;
}
//arr[left] < arr[mid],arr[right] <= arr[mid]
//arr[mid]是最大的
else if (arr[left] < arr[right])
{
return right;
}
else
{
return left;
}
}
//arr[left] >= arr[mid]
else
{
if (arr[mid] > arr[right])
{
return mid;
}
//arr[left] >= arr[mid],arr[right] >= arr[mid]
//arr[mid]是最小的
else if (arr[left] < arr[right])
{
return left;
}
else
{
return right;
}
}
}
//快排函数中
int mid = GetMidi(arr, left, right);
Swap(&arr[mid], &arr[left]);
int key = left;
小区间优化
我们看看以下这个图，我们看到虽然学列只有10个元素，但竟然递归了这么多次，这样有必要吗？是不是没有必要呀，在处理少量元素的时候，虽然占空间的使用量不大，但对于小规模数据来说，这额外的空间开销相对就比较明显了，这就意味着在处理小规模数据时，快速排序的性能会急剧下降。
我们再来看看以下这图，最坏情况下快速排序的形式其实与满二叉树类似，而我们满二叉树最后一层都是叶子节点，也就相当于我们快速排序一直递归至只有一个元素，而最后一层占满二叉树节点个数的50%左右，倒二层占25%左右，倒三层占12.5%左右。
那么如果我们这个待排序序列有大量元素，使用快速排序的时候我们这个排序递归到后面就会出现很多小区间，这些小区间将会是一大笔消耗。
于是我们就在想，如果递归到后面，要排序的元素较少时，我们不再采用递归实现排序，转而使用插入排序实现排序，为什么选择插入排序，而不是冒泡？不是选择？不是堆排？不是希尔排序？不是归并排序？
因为冒泡排序和选择排序的效率没插入高。堆排需要建堆，但是我们元素少，建堆不值得。而希尔排序是为了让元素更快的跳到合适位置才设置的增量数组，但我们现在统共就几个元素，没有必要。而归并排序我还没有介绍，不过归并排序的思想也是递归，所以不适合。
所以采用插入排序进行小区间优化是比较合适的。
参考代码如下：
//快速排序，优化版（三数取中，最后10个数不用递归，使用插入提高效率）
void QuickSort2(int* arr, int left, int right)
{
if (left >= right)
return;
//小区间优化，小于10个数的时候采用插入排序
if ((right - left + 1) < 10)
{
//注意是从arr+left开始的right-left+1个数
InsertSort(arr + left, right - left + 1);
}
//三数取中
int mid = GetMidi(arr, left, right);
Swap(&arr[mid], &arr[left]);
int key = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边找小
while (begin < end && arr[end] >= arr[key])
{
end--;
}
//左边找大
while (begin < end && arr[begin] <= arr[key])
{
begin++;
}
//找到后交换
Swap(&arr[begin], &arr[end]);
}
//begin和end相遇，交换key与相遇位置
Swap(&arr[key], &arr[begin]);
key = begin;
//区间变成[left,key-1],key[key+1,right]
QuickSort2(arr, left, key - 1);
QuickSort2(arr, key + 1, right);
}
以下是优化前和优化后快速排序的效率，在vs2022（debug版本）下，这边我们给出了500万个数，我们可以看没有优化前快排的速度大概是是880ms左右，加上三数取中和小区间优化后的速度大概是840ms左右，效率有所提升。
6.2快速排序(挖坑法)
挖坑法的思想是：
1.从待排序序列中选择一个元素当作基准值，一般是左侧第一个元素，再设置一个临时变量key用于保存基准值，然后把这个基准值所在的位置视为一个“坑”，此时序列中该位置就空出来了。
2.设置两个标记变量，一个变量left指向左侧第一个元素，另一个变量right指向右侧最后一个元素。
3.以升序排序为例，right先先左侧移动寻找比key小的值，找到后停下，将right位置的元素填入到“坑”位置，然后这个right这个位置变成新的“坑”。
4.right位置是新“坑”后，left向右移动寻找比key大的元素，找到后停下，将left位置元素填入到“坑”位置，然后left位置就变成新“坑”。
5.重复步骤3、4,直到left和right相遇，将key变量保存的基准值填入坑中，此时key左侧元素都比key小，右侧元素都大于或者等于key。
6.与hoare版本一样形成三个区间[0,key-1]key[key+1,end]，然后递归将左右区间进行排序。
参考代码如下：
int PartSort2(int* arr, int begin, int end)
{
//begin是坑
int key = arr[begin];
while (begin < end)
{
//右边找小
while (begin < end && arr[end] >= key)
--end;
//end给begin这个坑，end就变成新的坑
arr[begin] = arr[end];
//左边找大
while (begin < end && arr[begin] <= key)
++begin;
//begin给end，begin成为新的坑
arr[end] = arr[begin];
}
arr[begin] = key;
return begin;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1) < 10)
{
InsertSort(arr + left, right - left + 1);
}
else
{
int key = PartSort2(arr, left, right);
//[left,key-1]key[key+1,right]
QuickSort(arr, left, key - 1);
QuickSort(arr, key + 1, right);
}
}
6.3快速排序(前后指针法)
前后指针法的思想是：
1.设置一个基准值（key），一般是左侧第一个元素。
2.设置两个标记变量，一个prev指向第一个元素，一个cur指向prev的下一个元素。
3.以升序例，cur向右移动，如果cur位置的元素比key小，prev向后移一位，如果prev移动后的位置不是cur所在位置，就将prev和cur的元素进行交换。如果cur位置的元素比key大，prev不向后移动，cur继续向后找。
4.当cur走完了整个序列，交换key和prev位置的元素。
5.形成三个区间[0,key-1]key[key+1,end],与上面一样，递归将左右两个区间进行排序。
动图如下：
参考代码如下：
//前后指针法
int PartSort3(int* arr, int left,int right)
{
int mid = GetMidi(arr, left, right);
Swap(&arr[mid], &arr[left]);
int key = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
//cur位置的值比key位置的值小，并且prev和cur不是紧挨着的
if (arr[cur] < arr[key] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
++cur;
}
Swap(&arr[prev], &arr[key]);
return prev;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1) < 10)
{
InsertSort(arr + left, right - left + 1);
}
else
{
int key = PartSort3(arr, left, right);
//[left,key-1]key[key+1,right]
QuickSort(arr, left, key - 1);
QuickSort(arr, key + 1, right);
}
}
6.4快速排序(非递归实现)
非递归的思想是：
借助栈来实现快速排序。
具体步骤：
1.初始化栈，先将整个序列的起始位置（通常为0）和结束位置（数组长度-1）这两个数压入栈中。
2.从栈中弹出一个区间（起始位置和结束位置）
3.对弹出的这个区间使用上面的排序（hoare方法/挖坑法/前后指针法），将区间分成三个部分[left，key-1]key[key+1,right]，然后将右区间和左区间的起始位置和结束位置入栈。
4.不断重复2、3步骤直到栈为空，说明排序完成。
参考代码如下：
//hoare方法
int PartSort1(int* arr, int left, int right)
{
int mid = GetMidi(arr, left, right);
Swap(&arr[mid], &arr[left]);
int key = left;
int begin = left;
int end = right;
while (begin < end)
{
//右边找小
while (begin < end && arr[end] >= arr[key])
{
--end;
}
//左边找大
while (begin < end && arr[begin] <= arr[key])
{
++begin;
}
//找到后交换
Swap(&arr[begin], &arr[end]);
}
//交换key与相遇位置
Swap(&arr[key], &arr[begin]);
return begin;
}
//快速排序非递归实现
void QuickSortNonR(int* arr, int left, int right)
{
ST s;
STInit(&s);
//将区间入栈，入两个数，拿的时候也拿两个数
STPush(&s, right);
STPush(&s, left);
while (!STEmpty(&s))
{
int left = STTop(&s);
STPop(&s);
int right = STTop(&s);
STPop(&s);
//快排单趟排序
int key = PartSort1(arr, left, right);
//[left,key-1]key[key+1,right]
//将个数大于1的区间入栈，先将右区间入栈再入左区间
if (key + 1 < right)
{
STPush(&s, right);
STPush(&s, key + 1);
}
if (left < key - 1)
{
STPush(&s, key - 1);
STPush(&s, left);
}
}
STDestory(&s);
}
7.归并排序
7.1归并排序递归实现
归并排序的思想是：
1.分解序列：计算序列的中间位置mid，将数组分为左右两部分[left,mid][mid+1,right]
2.对左右两部分分别递归进行分解操作，即不断重复步骤1，直到子序列的长度为1
3.当子序列长度为1时，认为其已经有序，开始进行合并操作。以升序为例，比较左右子序列的第一个元素，将较小的元素放入一个临时序列中，并将元素所在的子序列的指针后移一位。
4.重复上述比较和移动的操作，直到其中一个序列的元素全部放入临时数组中，然后将另一个子序列的剩余元素全部放入临时数组中。
5.将临时数组的元素复制回原数组的对应位置，完成一次合并操作
6.不断重复合并操作，直到整个序列有序
动图如下：
参考代码如下：
//子函数
void _MergaSort(int* arr, int* tmp, int left, int right)
{
//只有一个数据就不用再继续分割了
if (left >= right)
return;
int mid = (left + right) / 2;
//区间分割成[left,mid],[mid+1,right]
//一直分割，直到只有一个数，然后一个数与一个数排序，然后归并回去
_MergaSort(arr, tmp, left, mid);
_MergaSort(arr, tmp, mid + 1, right);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
//合并
while (begin1 <= end1 && begin2 <= end2)
{
//升序
if (arr[begin1] <= arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
//两组数据必有一组没有入完
while (begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
//排好两组数据后将tmp数组中排好的这几个归并回原数组对应位置
memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
//归并排序递归实现
void MergaSort(int* arr, int n)
{
//额外申请一个数组tmp，排好序后归并回原数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("MergaSort():malloc fail!");
return;
}
//子数组递归实现逻辑
_MergaSort(arr, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
7.2归并排序非递归实现
非递归的思路是：
1.将数组中的每个元素看作是一个长度为 1 的有序子数组。
2.合并子数组：设定子数组的初始长度 gap 为 1，每次合并相邻的两个长度为 gap 的子数组，将它们合并成一个长度为 2 * gap 的有序子数组。
3.在合并过程中，使用两个指针分别指向两个待合并的子数组，比较指针所指元素的大小，将较小的元素放入临时数组中，然后移动指针，继续比较和放入，直到其中一个子数组的元素全部放入临时数组。
4.将另一个子数组中剩余的元素全部放入临时数组。
5.将临时数组中的元素复制回原数组对应的位置，完成一次合并操作。
6.增加子数组长度：将子数组的长度 gap 乘以 2，继续进行下一轮合并，重复步骤 2，直到子数组的长度大于或等于数组的长度，此时整个数组已排序完成。
参考代码如下：
void _MergaSortNonR(int* arr, int* tmp, int n)
{
//11归并，22归并，44归并，88归并
//gap是每组的数据个数
int gap = 1;
while (gap < n)
{
//i是要进行排序的两组数组的前一组的下标
for (int i = 0; i < n;i += 2*gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//除了begin1，其余都存在越界情况
//第二个数组越界不存在，第一个数组有序，不需要排序
if (begin2 >= n)
break;
//第二个数组部分越界，调整一下,然后继续排序
if (end2 >= n)
end2 = n - 1;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
//升序
if (arr[begin1] <= arr[begin2])
tmp[j++] = arr[begin1++];
else
tmp[j++] = arr[begin2++];
}
//还有一组不为空
while (begin1 <= end1)
tmp[j++] = arr[begin1++];
while (begin2 <= end2)
tmp[j++] = arr[begin2++];
//归并回原数组
memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
}
//两组数据必有一组没有入完
while (begin1 <= end1)
tmp[i++] = arr[begin1++];
while (begin2 <= end2)
tmp[i++] = arr[begin2++];
//排好两组数据后将tmp数组中排好的这几个归并回原数组对应位置
memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
//归并排序非递归实现
void MergaSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("MergaSortNonR():malloc fail");
return;
}
_MergaSortNonR(arr, tmp, n);
free(tmp);
tmp = NULL;
}
8.计数排序
计数排序的思想是：
1.遍历一遍数组，找出数组中的最大值max和最小值min，从而确定出数组中的元素范围int range = max - min + 1;
2.根据范围中元素的个数开辟出以一个额外的数组count用于统计数组中每个元素出现的次数。
3.遍历待排序数组，统计每个元素出现的次数count[arr[i] - min]++;
4.额外数组的下标+数组中的最小值表示元素的值arr[j++] = i + min;出现几次就赋值几次。
参考代码如下：
//计数排序
void CountSort(int* arr, int n)
{
int min = arr[0];
int max = arr[0];
for (int i = 0; i < n; i++)
{
if (min > arr[i])
min = arr[i];
if (max < arr[i])
max = arr[i];
}
//计算范围
int range = max - min + 1;
//申请空间、初始化
int* count = (int*)calloc(range, sizeof(int));
//统计出现次数
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
//返回原数组
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
arr[j++] = i + min;
}
}