排序：所谓排序，就是使一组杂乱无章的数据，按照其中的一定的规律或某些关键字
(如价格，销量，好评率，排名等)的大小，递增或递减地排列起来的操作。
为了方便，我们这里讲的排序和有序指的都是升序，降序反过来就行了。
1.插入排序
1.1直接插入排序
核心思想：
把一个数插入一个有序区间。
实现方法：假设0—end是已经有序的区间，我们用x存储end后面一个位置的元素，表示要把x存储到0—end的有序区间中。
如果end所指元素比x大，就把end所指的元素赋给后面一个位置的元素（相当于把end所指元素往后移动一个格子），然后end=end-1使end指向前一个元素，继续比较；
1.1.1单趟插入排序：（把x插入一个有序数组）
//单趟排序：（把x插入一个有序数组）
// 1 2 3 5 9 10 12 x=4
void InsertSort(int* arr, int sz)
{
int end;
int x;
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = x;//插入在最头上和插入在中间都在这里处理
}整个数组排序，如何控制呢？我们把上面的x赋值给arr[ end +1 ] 然后重复插入就是这样：
1.1.2完整插入排序代码：
void InsertSort(int* arr, int sz)
{
assert(arr != NULL);
for (int i = 0;i <= sz - 2;i++)
{
int end = i;//把数组第一个元素当作有序，想打扑克牌摸牌排序一样
int x = arr[end + 1];
//x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在n-2
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = x;
}
}为了验证代码，我们像以前一样分文件写，先把部分Sort.c和Test.c放出来，后面再把完整的放出来
#include"Sort.h"
先写打印数组函数和交换函数（后面排序使用）
void printArr(int* arr, int sz)
{
for (int i = 0;i <= sz - 1;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
printArr(arr, sz);
InsertSort(arr, sz);
printArr(arr, sz);
//输出：0 1 2 3 4 5 6 7 8 9
return 0;
}1.1.3插入排序复杂度分析：
直接插入排序最坏情况是逆序（每插入一个都要移动,从第二个元素开始，第二个元素需要移动1次，第三个元素需要移动2次，…，第n个元素需要移动n-1次）
取最大项就是O(N^2).
最好情况是已经有序或者基本有序，就只需要遍历一次数组（有序）或者偶尔几个元素需要移动几次格子再插入其他的直接插入在end所指元素后面就行（基本有序），故最好情况下时间复杂度是O(N)。
没有开辟额外的空间所以：插入排序的空间复杂度是O（1），时间复杂度是O（N^2）
我们之前写过冒泡排序
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，
它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，
移动次数上都是原本数据的逆序度。
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，
冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，
所以总的交换次数冒泡排序大于插入排序。
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，
如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，
但是我们实际使用中还是优先选择插入排序。
对于插入排序还是可以优化的，对了，没错，就是下面的希尔排序
这里先说插入排序是比冒泡排序好的排序。（铺垫）
（我在最后的八大排序完整代码中放入了测试效率的测试，想测任何排序的时候可以去看看）
这里想到方便对比，所以讲完八大排序后再统一讲完八大排序的复杂度
1.2希尔排序
插入排序面对逆序或不太有序的情况下效率比较低，但是面对基本有序的情况它是非常棒的排序
（基本有序的话时间复杂度是O(N)，是算法>排序算法的天花板，没有一个算法>排序算法能比O(N)快）。
为了优化直接插入排序，一个叫希尔的人想出来了一种排序（希尔排序），核心思想：
希尔排序就是在直接插入排序上优化，既然对基本有序的情况直接插入排序很棒，
那我先分成gap组进行一个预排序（这个过程可以使数组基本有序），
然后再进行一个直接插入排序，那么怎么样进行预排序呢？
预排序步骤：
1.2.1单趟预排序：
按gap（缺口，缝隙，差距）分组，分成gap组，gap>1，对每个组进行插入排序，
使总体数组看起来接近有序
实际上就是把0，0+gap，0+2gap…视为一组，1，1+gap，1+2gap…视为一组...
对每一组进行直接插入排序，这样每一组都是有序的了，总体数组就比之前有有序多了。
那么对0,0+gap,0+2gap…这一组预排序的单趟排序代码如下（这里gap取3）：
//分组的单趟和前面单趟插入排序一样，间距是gap，前面可以认为gap=1
//按gap分组进行预排序
int gap = 3;
int end = 0;
int x = arr[end + gap];
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = x;1.2.2对所有组的预排序：
//依次排完gap组
int gap = 3;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = x;
}
}上面的代码虽然清楚，但是不够简洁，我们可以对多组同时进行预排序，
就好像把多组同时一锅炖了一样。对单趟多组预排序的代码改造如下：
1.2.3预排序代码简化：
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (arr[end] > x)
{
//如果end所指的元素比x大
//就把end所指元素往后移动，空出一个格子
arr[end + gap] = arr[end];
end -= gap;
}
else
{
//否则就跳出去，
//这样可以同时处理end小于0的情况（插入在最头上的情况）
break;
}
}
arr[end + gap] = x;
}怎么取gap呢？讨论一下预排序的时间复杂度
与直接插入排序类似，最好情况是已经有序的时候，是O(N)（遍历一遍就行了）
最坏情况：每一组都是逆序的，每一组的元素个数是[N/gap]，这样的总共需要的循环次数是：gap*(1+2+3+…+[N/gap]-1)（套用最糟糕情况直接插入排序的循环次数，gap组）。
观察这个总共需要的循环次数的函数，发现:
gap越大 预排越快(gap=N，O(N)) ,但是因为分的组数太多了，排完后越接近无序；
gap越小 预排越慢(gap=1，O(N^2)),分的组数少排完后越接近有序。
多趟分组预排序与最后的直接插入排序
为了让最后进行插入排序的时候数组能更接近有序一些，我们可以加一个循环控制gap不断变化进行多趟分组预排序，并且把gap=1时，也就是最终进行直接插入排序耦合到while循环里，代码如下：
1.2.4完整希尔排序代码：
void ShellSort(int* arr, int sz)
{
int gap = sz;
//多次预排序(gap > 1)+直接插入排序(gap == 1)
while (gap > 1)//gap进去以后才除所以大于1就行
{
//两种取gap的方法：
//gap = gap / 2;//一次跳一半
gap = gap / 3 + 1;
//加一是为了保证最后一次gap小于3的时候
//能够有gap等于1来表示直接插入排序
//多组同时搞：
for (int i = 0; i < sz - gap; i++)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = x;
}
}
}代码测试（依然输出0 1 2 3 4 5 6 7 8 9）
#include"Sort.h"
int main()
{
int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
printArr(arr, sz);
//InsertSort(arr, sz);
ShellSort(arr, sz);
printArr(arr, sz);
return 0;
}2.选择排序
2.1选择排序
在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
第二次从下一个数开始遍历 n-2个数，找到最小的数和第二个数交换。
重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。
2.1.1选择排序代码：
void SelectSort(int* arr, int sz)
{
//先假设第一个元素最小
for (int i = 0; i < sz; i++)
{
int begin = i;
int minindex = i;
while (begin < sz)
{
if (arr[begin] < arr[minindex])
{
minindex = begin;
}
begin++;
}
Swap(&arr[minindex], &arr[i]);
}
}2.1.2选择排序代码优化：
我们可以定义一个begin变量，一个end变量，用来记录数据首和尾的下标，我们一个可以找出两个值，一个最大值，一个最小值，最小值放在a[begin]中，最大值放在a[end]中，这样我们就比上面的快多了
void SelectSort(int* arr, int sz)
{
int begin = 0;
int end = sz - 1;
while (begin < end)
{
int mini = begin;
int maxi = end;
int i = 0;
for (i = begin;i <= end;i++)
{
//选出[begin,end]中最大和最小的
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[begin], &arr[mini]);
//这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动
if (begin == maxi)
{
maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置
}
Swap(&arr[end], & arr[maxi]);
begin++;
end--;
}
}2.2堆排序
要学习堆排序，首先要学习基础的二叉树结构，学习堆的向下调整算法，使用堆排序之前，
我们得先建一个堆出来，堆的向下调整算法的前提是：根节点的左右子树均是大堆或小堆。
由于堆排序在向下调整的过程中，需要从孩子中选择出较大或较小的那个孩子，
父亲才与孩子进行交换，所以堆排序是一种选择排序。
堆排序的详解请移至博客：
比特数据结构与算法（第四章_中_续①）堆排序（详解）_GR C的博客-CSDN博客
2.1.1堆排序代码：
void justDown(int* arr, int sz, int father_idx)
{
int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
{
if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
{ // 如果右孩子存在且右孩子比左孩子大
child_idx = child_idx + 1;// 让其代表右孩子
}
if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质）
{
Swap(&arr[child_idx], &arr[father_idx]);
father_idx = child_idx; // 更新下标往下走
child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲
}
else // 如果孩子的值小于父亲的值（符合大堆的性质）
{
break;
}
}
}
//完整堆排序_升序
void HeapSort(int* arr, int sz)
{
//创建大堆，选出最大的数，时间：O(N)
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0)
{
justDown(arr, sz, father);
father--;
}
//交换后调堆 时间：O(N * logN)
int end = sz - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
justDown(arr, end, 0);
end--;
}
}3.交换排序
交换排序分为冒泡排序和快速排序，冒泡排序我们写过很多次了这里放个动图就不讲了。
3.1.1冒泡排序代码：
void BubbleSort(int* arr, int sz)
{
int i = 0;
int j = 0;
for (i = 0;i < sz - 1;i++)
{
int flag = 1;
for (j = 0;j < sz - 1 - i;j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
}
flag = 0;
}
if (flag)
{
break;
}
}
}3.1.2 快速排序
3.1.2.1 Hoare法快速排序
Hoare法快速排序的思想
快速排序的单趟：key放到它正确的位置上(整体排完序后最终放的位置)，
key的左边的值比key小，key右边值比它大
单趟排完，再递归让key左边区间有序，key的右边区间有序，整体就有序了
我们先写出单趟排序PartSort(int* arr,int left,int right)；因为是递归式的二叉树结构。
1.先选出一个key，一般是最左边或者最右边的。
2.定义left和right，left向右遍历序列，right向左遍历序列（如果定义最左边的那个元素为key,那么right先走，若定义最右边的那个元素为key，则left先走）。
3.在走的过程中，若R遇到小于key的数则停下，到L开始走，直到L遇到比key大的数时，L也停下，将下标为left，right的数据交换，直到L与R相撞，最后把它们相遇的位置和a[keyi]交换，返回L与R相遇的位置。
4.经过一次单趟排序，最终使得key左边的数据都小于key，右边的数据都大于key。
5.然后我们再将key的左序列和右序列再次进行这种单趟排序，每进行一次单趟排序就可以确定一个数据的排序位置，如此递归操作下去，直到最后左右序列只有一个数据或没有数据，则层层返回，此时序列就排好啦。
int PartSort1(int* arr, int left, int right)
{
int keyi = left;
//左边做key
while (left < right)
{
//右边先走 找小 控制不要错开不要越界
while (left < right && arr[right] >= arr[keyi])
{
--right;
}
//左边再走 找大 控制不要错开不要越界
while (left < right && arr[left] <= arr[keyi])
{
++left;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);//交换相遇的地方和关键字的位置
return left;//返回关键字的位置
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = PartSort1(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}3.1.2.2 挖坑法快速排序
挖坑法 只是比Hoare法 好理解一点，并没有实质的改变
1.利用优化后的选key逻辑：三数取中， 选出key变量作为坑位，保存作为坑位的值
（保存起来就可以覆盖了，就相当于坑位）。
2.定义一个L，一个R，L从左向右走，R从右向左走
（若在最左边挖坑，则R先走；若在最右边挖坑，则L先走）。
3.假设我们定义最左边为坑位，在R走的过程中，若R遇到小于key的数，则将这个数抛入坑位，
然后这个数原来的位置变成坑位，然后L向右走走，若遇到大于key的数则停下，将这个数抛入坑位，
这个数的位置又形成新的坑位，如此循环下去，直到最终L与R相遇，
最后再将key抛入最后形成的坑位。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
/*3.假设我们定义最左边为坑位，在R走的过程中，若R遇到小于key的数，则将这个数抛入坑位，
然后这个数原来的位置变成坑位，然后L向右走走，若遇到大于key的数则停下，将这个数抛入坑位，
这个数的位置又形成新的坑位，如此循环下去，直到最终L与R相遇，
最后再将key抛入最后形成的坑位。*/
int PartSort2(int* arr, int left, int right)
{
int pit = left;
int key = arr[pit];
while (left < right)
{
while (left < right && arr[right] >= key)
{
right--;
}
arr[pit] = arr[right];
pit = right;
while (left < right && arr[left] <= key)
{
left++;
}
arr[pit] = arr[left];
pit = left;
}
arr[pit] = key;
return pit;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//int keyi = PartSort1(arr, left, right);
int keyi = PartSort2(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}3.1.2.3 前后指针法快速排序
前后指针法比前面两种方法更简洁,理解后不易错
1.用三数取中法，选出一个key（后面讲，这里先选最左边的）。
2.刚开始prev指向序列开头，cur指向prev+1的位置。
3.若cur指向的值比key小，则cur停下来，++prev，交换prev和cur位置上的数据，然后cur继续往后++，prev紧跟cur，但若cur指向的数据大于等于key，则cur继续++，但prev不动，如此规律进行下去，直到cur越界，跳出循环，最后将prev指向的数据和keyi指向的数据交换即可。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
int PartSort3(int* arr, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
/*while (cur <= right && arr[cur] >= arr[keyi])
{
cur++;
}
if (cur <= right)
{
prev++;
Swap(&arr[cur], &arr[prev]);
cur++;
}*/
if (arr[cur] < arr[keyi] && ++prev != cur)//反正都要cur++，注意这里prev已经++了
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
return prev;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//int keyi = PartSort1(arr, left, right);
//int keyi = PartSort2(arr, left, right);
int keyi = PartSort3(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}3.1.3 快速排序的两个优化
3.1.3.1 三数取中
快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，
我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：
若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，
那么快速排序的时间复杂度就是O(NlogN)。
可是谁能保证你每次选取的key都是正中间的那个数呢？当待排序列本就是一个
有序（或者接近有序）的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，
那么快速排序的效率将达到最低
可以看到，这种情况下，快速排序的时间复杂度退化为O(N2)。其实，
对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则效率越高。
为了少出现上面的情况，有人提出随机选key,但还是会出现极端情况，
为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。
三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。
这就确保了我们所选取的数不会是序列中的最大或是最小值了。
所以说加入三数取中后才认为快速排序的时间复杂度是O(NlogN)。
int GetMidIndex(int* arr, int left, int right)
{
int mid = left + (right - left) / 2;
if (arr[mid] > arr[left])
{
if (arr[mid] < arr[right])
return mid;
else if (arr[left] > arr[right])
return left;
else
return right;
}
else
{
if (arr[mid] > arr[right])
return mid;
else if (arr[left] > arr[right])
return right;
else
return left;
}
}3.1.3.2 小区间优化
随着递归深度的增加，递归次数以每层2倍的速度增加，这对效率有着很大的影响。
为了减少最后几层递归，我们可以设置一个判断语句，
当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。
小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，
而且待排序列的长度越长，该效果越明显。
这时我们前面讲的对于小区间快速且简单的几个排序中的选择排序就派上用场（呼应铺垫）
虽然减少了80%以上的递归，但是现在编译器对递归的优化已经很大了，
所以小区间优化并没有三数取中对快排的优化大。
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 < 19)//可以自己取，官方是十几
{
InsertSort(arr + left, right - left + 1);
}
else
{
//int key = PartSort1(arr, left, right);
//int key = PartSort2(arr, left, right);
int keyi = PartSort3(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}3.1.4 快速排序非递归版
递归版的致命问题就是递归层次太深可能会导致栈溢出，因为栈是不大的
所以对应大多数递归我们都要掌握改非递归的能力。树的递归改非递归有点难，后面再学。
递归改非递归有两种方法
直接改循环。比如斐波那契数列，还有后面的归并排序
递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。
一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。
非递归快排的基本思想：
1. 申请一个栈，存放排序数组的起始位置和终点位置。
2. 将整个数组的起始位置和终点位置入栈。
3. 由于栈的特性是：后进先出，right后进栈，所以right先出栈。
定义一个end接收栈顶元素，出栈操作、定义一个begin接收栈顶元素，出栈操作。
4. 对数组进行一次单趟排序，返回key关键值的下标。
5. 这时候需要排基准值key左边的序列。
如果只将基准值key左边序列的起始位置和终点位置存入栈中，等左边排序完将找不到后边的区间。
所以先将右边序列的起始位置和终点位置存入栈中，再将左边的起始位置和终点位置后存入栈中。
6.判断栈是否为空，若不为空 重复4、5步、若为空则排序完成。
这时我们把以前写的栈拷贝来：（后面会放完整八大排序和栈的代码）
比特数据结构与算法（第三章_上）栈的概念和实现（力扣：20. 有效的括号）_GR C的博客-CSDN博客
void QuickSortNonR(int* arr, int left, int right)
{
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 = PartSort3(arr, begin, end);
//区间被成两部分了 [begin,keyi-1] [keyi+1,end]
if (keyi + 1 < end)//先处理右
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if(begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}4.归并排序
4.1 归并排序递归版
归并排序，从其思想上看就很适合使用递归来实现，并且用递归实现也比较简单。
其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，
合并完毕后再将数据拷贝回原数组。
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时（认为有序）
{
return;
}
int mid = left + (right - left) / 2;
//[left,mid] [mid+1,right] 分治递归，让子区间有序
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//将两段子区间进行归并，归并结果放在tmp中
int left1 = left, right1 = mid;
int left2 = mid + 1, right2 = right;
int i = left;
while (left1 <= right1 && left2 <= right2)
{
//将较小的数据优先放入tmp，放入后++
if (arr[left1] < arr[left2])
{
tmp[i++] = arr[left1++];
}
else
{
tmp[i++] = arr[left2++];
}
}
//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
while (left1 <= right1)//有一个while循环条件肯定不满足，不用管
{
tmp[i++] = arr[left1++];
}
while (left2 <= right2)
{
tmp[i++] = arr[left2++];
}
//归并完后，拷贝回原数组
//for (int j = left; j <= right; j++)
//{
// arr[j] = tmp[j];
//}
memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//申请一个与原数组大小相同的空间
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(arr, 0, sz - 1, tmp);//函数前加_用来表示其子函数，常用来递归
free(tmp);
tmp = NULL;
}4.2 归并排序非递归版
前面快排的非递归里讲过递归的缺点， 归并排序递归改非递归的两种方法中不用数据结构的栈，
而是直接使用循环。我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：
由于我们操纵的是数组的下标，所以我们需要借助数组，来帮我们存储上面递归得到的数组下标，
和递归的区别就是，递归要将区间一直细分，要将左区间一直递归划分完了，再递归划分右区间，
而借助数组的非递归是一次性就将数据处理完毕，并且每次都将下标拷贝回原数组
归并排序的基本思路是将待排序序列a[0…n-1]看成是n个长度为1的有序序列，
相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，
得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列
当然，以上例子是一个待排序列长度比较特殊的例子，
（以上只适用于数组个数为2的次方，否则会越界）
我们若是想写出一个广泛适用的程序，必定需要考虑到某些极端情况：
情况一：
当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够gap个，
这时我们需要在合并序列时，对第二个小区间的边界进行控制。
情况二：
当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。
情况三：
当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够gap个，此时也不需要对该小组进行合并。（可与情况二归为一类）
void MergeSortNonR(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;
while (gap < sz)
{
for (int i = 0; i < sz; i += 2 * gap)//控制每次参与合并的元素个数
{
// [i, i + gap - 1] [i + gap, i + 2 * gap - 1]
int left1 = i, right1 = i + gap - 1;
int left2 = i + gap, right2 = i + 2 * gap - 1;
// 防止越界核心思想：right1、left2、right2都有可能越界
if (right1 >= sz || left2 >= sz)// right1越界 或者 left2 越界都不需要归并
{
break;
}
else if (right2 >= sz)// right2 越界，需要归并，修正right2
{
right2 = sz - 1;
}
int n = right2 - left1 + 1;//记录要拷贝的个数
int j = left1;
while (left1 <= right1 && left2 <= right2)
{
if (arr[left1] < arr[left2])
{
tmp[j++] = arr[left1++];
}
else
{
tmp[j++] = arr[left2++];
}
}
while (left1 <= right1)
{
tmp[j++] = arr[left1++];
}
while (left2 <= right2)
{
tmp[j++] = arr[left2++];
}
// 把归并小区间拷贝回原数组
for (int k = i; k <= right2; k++)
{
arr[k] = tmp[k];
}
//memcpy(arr + i, tmp + i, sizeof(int) * n);
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}5.计数排序
八大排序最后一个排序：计数排序，又叫非比较排序，非比较排序只适用于整数。
顾名思义，该算法不是通过比较数据的大小来进行排序的，
而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。
非比较排序还有桶排序和基数排序，但校招不考，用处也不大，只是计数排序的思想比较好，
所以这里只讲计数排序。
计数排序动图：
上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，
但这样会造成空间浪费。例如，我们要将数组：1020,1021,1018，进行排序，
难道我们要开辟1022个整型空间吗？
若是使用计数排序，我们应该使用相对映射，简单来说，数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组：1020,1021,1018，我们就只需要开辟用于储存4个整型的空间大小了，此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。（负数也能排）
计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费。
5.1 计数排序代码：
oid CountSort(int* arr, int sz)
{
int min = arr[0];
int max = arr[0];
for (int i = 0; i < sz; i++)//找出数组中的最大值和最小值,为了后面开辟数组
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0
if (count == NULL)
{
printf("calloc fail\n");
exit(-1);
}
for (int i = 0; i < sz; i++)//统计相同元素出现次数（相对映射）
{
count[arr[i] - min]++;
}
int i = 0;
for (int j = 0; j < range; j++)//根据统计结果将序列回收到原来的数组中
{
while (count[j]--)
{
arr[i++] = j + min;
}
}
free(count);
count = NULL;
}6.前七大排序复杂度和稳定性分析
由于计数排序只适用于整数等各种原因，我们这里只讨论前七大排序。
6.1稳定性的概念：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，
若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，
而在排序后的序列中，r[i]仍在r[j]之前，则称这种算法>排序算法是稳定的；否则称为不稳定的。
算法>排序算法的稳定性通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序
与排序后它们两个先后位置顺序相同。
我们对冒泡排序很熟悉
冒泡排序是把大的元素往后调，小的元素往前调。比较都发生在相邻的两个元素之间，如果两个元素相等，是不会发生交换的，所以相同元素的前后顺序没有改变，所以冒泡排序是稳定的排序。
再说选择排序，选择排序最重要的思想，就是假设某个数是最小的or最大的，
它是给某个位置选择无序区元素中最小的那个。可以先举个例子，比如5 2 5 4 1 这个序列，
选择排序会假设2是最小的，然后拿他和别的数去比，找到一个最小的，放到2所在的位置。
所以在这个排序中，第一趟的时候5会和1交换，两个5的相对位置就发生了改变，
有些资料说选择排序是稳定的，这是错的，选择排序是不稳定的排序。
学了这么久了，下面直接给出一张图，可以自己先试着写一遍，不要背，理解了才是最好的
6.2对比图
图中希尔排序最坏的情况也达不到O（N^2），所以只需记平均的就好，
快速排序加上三数取中的优化后出现时间最坏的概率几乎没有。
7.内排序和外排序（了解）
内部排序：数据元素全部放在内存中的排序。
外部排序：是因排序的数据很大，一次不能容纳全部的排序记录，
在排序过程中还需要访问外部存储器的排序。
我们通常所说的算法>排序算法往往指的是内部算法>排序算法，即数据记录在内存中进行排序。
我们前面比较的七大排序中都能用于内排序，归并排序在内排序和外排序都能用。
假设现在有10亿个整数（4GB）存放在文件A中，需要我们进行排序，
而内存一次只能提供512MB空间，归并排序解决该问题的基本思路如下：
1、每次从文件A中读取八分之一，即512MB到内存中进行排序（内排序），并将排序结果写入到一个文件中，然后再读取八分之一，重复这个过程。那么最终会生成8个各自有序的小文件（A1~A8）。
2、对生成的8个小文件进行11合并，最终8个文件被合成为4个，然后再11合并，就变成2个文件了，最后再进行一次11合并，就变成1个有序文件了。
注意：这里将两个文件进行11合并，并不是先将两个文件读入内存然后进行合并，因为内存装不下。这里的11合并是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另一个文件中去，那么此时这个文件又是一个有序的文件了。
8.八大排序完整代码
Sort.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
void printArr(int* arr, int sz);
void Swap(int* p1, int* p2);
void InsertSort(int* arr, int sz);
void ShellSort(int* arr, int sz);
void SelectSort(int* arr, int sz);
void HeapSort(int* arr, int sz);
void BubbleSort(int* arr, int sz);
void QuickSort(int* arr, int left, int right);
void QuickSortNonR(int* arr, int left, int right);
void MergeSort(int* arr, int sz);
void MergeSortNonR(int* arr, int sz);
void CountSort(int* arr, int sz);Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
#include "Stack.h"
void printArr(int* arr, int sz)
{
for (int i = 0;i <= sz - 1;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* arr, int sz)
{
assert(arr != NULL);
for (int i = 0;i <= sz - 2;i++)
{
int end = i;//把数组第一个元素当作有序，想打扑克牌摸牌排序一样
int x = arr[end + 1];
//x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在sz-2
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = x;
}
}
void ShellSort(int* arr, int sz)
{
int gap = sz;
//多次预排序(gap > 1)+直接插入排序(gap == 1)
while (gap > 1)//gap进去以后才除所以大于1就行
{
//两种取gap的方法：
//gap = gap / 2;//一次跳一半
gap = gap / 3 + 1;
//加一是为了保证最后一次gap小于3的时候
//能够有gap等于1来表示直接插入排序
//多组同时搞：
for (int i = 0; i < sz - gap; i++)
{
int end = i;
int x = arr[end + gap];
while (end >= 0)
{
if (arr[end] > x)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = x;
}
}
}
//时间复杂度O(N^2)
//直接选择排序
void SelectSort0(int* arr, int sz)
{
//先假设第一个元素最小
for (int i = 0; i < sz; i++)
{
int begin = i;
int minindex = i;
while (begin < sz)
{
if (arr[begin] < arr[minindex])
{
minindex = begin;
}
begin++;
}
Swap(&arr[minindex], &arr[i]);
}
}
void SelectSort(int* arr, int sz)
{
int begin = 0;
int end = sz - 1;
while (begin < end)
{
int mini = begin;
int maxi = end;
int i = 0;
for (i = begin;i <= end;i++)
{
//选出[begin,end]中最大和最小的
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
Swap(&arr[begin], &arr[mini]);
//这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动
if (begin == maxi)
{
maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置
}
Swap(&arr[end], & arr[maxi]);
begin++;
end--;
}
}
void justDown(int* arr, int sz, int father_idx)
{
int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大）
while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子）
{
if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
{ // 如果右孩子存在且右孩子比左孩子大
child_idx = child_idx + 1;// 让其代表右孩子
}
if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质）
{
Swap(&arr[child_idx], &arr[father_idx]);
father_idx = child_idx; // 更新下标往下走
child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲
}
else // 如果孩子的值小于父亲的值（符合大堆的性质）
{
break;
}
}
}
//完整堆排序_升序
void HeapSort(int* arr, int sz)
{
//创建大堆，选出最大的数，时间：O(N)
int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲
while (father >= 0)
{
justDown(arr, sz, father);
father--;
}
//交换后调堆 时间：O(N * logN)
int end = sz - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
justDown(arr, end, 0);
end--;
}
}
void BubbleSort(int* arr, int sz)
{
int i = 0;
int j = 0;
for (i = 0;i < sz - 1;i++)
{
int flag = 1;
for (j = 0;j < sz - 1 - i;j++)
{
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
}
flag = 0;
}
if (flag)
{
break;
}
}
}
//三数取中
int GetMidIndex(int* arr, int left, int right)
{
int mid = left + (right - left) / 2;
if (arr[mid] > arr[left])
{
if (arr[mid] < arr[right])
return mid;
else if (arr[left] > arr[right])
return left;
else
return right;
}
else
{
if (arr[mid] > arr[right])
return mid;
else if (arr[left] > arr[right])
return right;
else
return left;
}
}
int PartSort1(int* arr, int left, int right)
{
int keyi = left;
//左边做key
while (left < right)
{
//右边先走 找小 控制不要错开不要越界
while (left < right && arr[right] >= arr[keyi])
{
--right;
}
//左边再走 找大 控制不要错开不要越界
while (left < right && arr[left] <= arr[keyi])
{
++left;
}
Swap(&arr[left], &arr[right]);
}
Swap(&arr[left], &arr[keyi]);//交换相遇的地方和关键字的位置
return left;//返回关键字的位置
}
int PartSort2(int* arr, int left, int right)
{
int pit = left;
int key = arr[pit];
while (left < right)
{
while (left < right && arr[right] >= key)
{
right--;
}
arr[pit] = arr[right];
pit = right;
while (left < right && arr[left] <= key)
{
left++;
}
arr[pit] = arr[left];
pit = left;
}
arr[pit] = key;
return pit;
}
int PartSort3(int* arr, int left, int right)
{
int prev = left;
int cur = left + 1;
int key = left;
while (cur <= right)
{
/*while (cur <= right && arr[cur] >= arr[key])
{
cur++;
}
if (cur <= right)
{
prev++;
Swap(&arr[cur], &arr[prev]);
cur++;
}*/
if (arr[cur] < arr[key] && ++prev != cur)//反正都要cur++，注意这里prev已经++了
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[key]);
return prev;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 < 19)//可以自己取，官方是十几
{
InsertSort(arr + left, right - left + 1);
}
else
{
//int key = PartSort1(arr, left, right);
//int key = PartSort2(arr, left, right);
int keyi = PartSort3(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}
void QuickSortNonR(int* arr, int left, int right)
{
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 = PartSort3(arr, begin, end);
//区间被成两部分了 [begin,keyi-1] [keyi+1,end]
if (keyi + 1 < end)//先处理右
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if(begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时（认为有序）
{
return;
}
int mid = left + (right - left) / 2;
//[left,mid] [mid+1,right] 分治递归，让子区间有序
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//将两段子区间进行归并，归并结果放在tmp中
int left1 = left, right1 = mid;
int left2 = mid + 1, right2 = right;
int i = left;
while (left1 <= right1 && left2 <= right2)
{
//将较小的数据优先放入tmp，放入后++
if (arr[left1] < arr[left2])
{
tmp[i++] = arr[left1++];
}
else
{
tmp[i++] = arr[left2++];
}
}
//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
while (left1 <= right1)//有一个while循环条件肯定不满足，不用管
{
tmp[i++] = arr[left1++];
}
while (left2 <= right2)
{
tmp[i++] = arr[left2++];
}
//归并完后，拷贝回原数组
//for (int j = left; j <= right; j++)
//{
// arr[j] = tmp[j];
//}
memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));
}
void MergeSort(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);//申请一个与原数组大小相同的空间
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(arr, 0, sz - 1, tmp);//函数前加_用来表示其子函数，常用来递归
free(tmp);
tmp = NULL;
}
void MergeSortNonR(int* arr, int sz)
{
int* tmp = (int*)malloc(sizeof(int) * sz);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(tmp, 0, sizeof(int) * sz);
int gap = 1;
while (gap < sz)
{
for (int i = 0; i < sz; i += 2 * gap)//控制每次参与合并的元素个数
{
// [i, i + gap - 1] [i + gap, i + 2 * gap - 1]
int left1 = i, right1 = i + gap - 1;
int left2 = i + gap, right2 = i + 2 * gap - 1;
// 防止越界核心思想：right1、left2、right2都有可能越界
if (right1 >= sz || left2 >= sz)// right1越界 或者 left2 越界都不需要归并
{
break;
}
else if (right2 >= sz)// right2 越界，需要归并，修正right2
{
right2 = sz - 1;
}
int n = right2 - left1 + 1;//记录要拷贝的个数
int j = left1;
while (left1 <= right1 && left2 <= right2)
{
if (arr[left1] <= arr[left2])//加个等于就是稳定的（后面会讲稳定性）
{
tmp[j++] = arr[left1++];
}
else
{
tmp[j++] = arr[left2++];
}
}
while (left1 <= right1)
{
tmp[j++] = arr[left1++];
}
while (left2 <= right2)
{
tmp[j++] = arr[left2++];
}
// 把归并小区间拷贝回原数组
//for (int k = i; k <= right2; k++)
//{
// arr[k] = tmp[k];
//}
memcpy(arr + i, tmp + i, sizeof(int) * n);
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
void CountSort(int* arr, int sz)
{
int min = arr[0];
int max = arr[0];
for (int i = 0; i < sz; i++)//找出数组中的最大值和最小值,为了后面开辟数组
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0
if (count == NULL)
{
printf("calloc fail\n");
exit(-1);
}
for (int i = 0; i < sz; i++)//统计相同元素出现次数（相对映射）
{
count[arr[i] - min]++;
}
int i = 0;
for (int j = 0; j < range; j++)//根据统计结果将序列回收到原来的数组中
{
while (count[j]--)
{
arr[i++] = j + min;
}
}
free(count);
count = NULL;
}Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
// 测试排序的性能对比
void TestOP()
{
srand(time(0));
const int N = 10000;//可以改N和屏蔽效率低的排序来测试
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
printArr(arr, sz);
//InsertSort(arr, sz);
//ShellSort(arr, sz);
//SelectSort(arr, sz);
//HeapSort(arr, sz);
//BubbleSort(arr, sz);
//QuickSort(arr, 0, sz - 1);
//QuickSortNonR(arr, 0, sz - 1);
//MergeSort(arr, sz);
//MergeSortNonR(arr,sz);
CountSort(arr,sz);
printArr(arr, sz);
//TestOP();
return 0;
}Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int StackDataType;
typedef struct Stack
{
StackDataType* array; //数组
int top; //栈顶
int capacity; //容量
} Stack;
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
bool StackEmpty(Stack* ps);
void StackPop(Stack* ps);
StackDataType StackTop(Stack* ps);
int StackSize(Stack* ps);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void StackInit(Stack* ps)//初始化
{
assert(ps);
ps->array = NULL;
ps->top = 0; // ps->top = -1
ps->capacity = 0;
}
void StackDestroy(Stack* ps)//销毁
{
assert(ps);
free(ps->array);
ps->array = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, StackDataType x)//进栈
{
assert(ps);
if (ps->top == ps->capacity)
{
int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);
if (tmp_arr == NULL)
{
printf("realloc failed!\n");
exit(-1);
}
// 更新
ps->array = tmp_arr;
ps->capacity = new_capacity;
}
ps->array[ps->top] = x;// 填入数据
ps->top++;
}
bool StackEmpty(Stack* ps)//判断栈是否为空
{
assert(ps);
return ps->top == 0; //等于0就是空，就是真
}
void StackPop(Stack* ps)// 出栈
{
assert(ps);
//assert(ps->top > 0); //防止top为空
assert(!StackEmpty(ps));
ps->top--;
}
StackDataType StackTop(Stack* ps)//返回栈顶数据
{
assert(ps);
//assert(ps->top > 0); //防止top为空
assert(!StackEmpty(ps));
return ps->array[ps->top - 1];
}
int StackSize(Stack* ps) //计算栈的大小
{
assert(ps);
return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}本章完。
本篇是最长的一篇博客了吧，数据结构暂时告一段落了，
