目录
前言
1，八大排序我们需要掌握八大排序的实现以及时间复杂度的的计算，稳定性，之间的对比
以下的这些排序我都以升序为例举例
2，稳定性和不稳定性：
假设a在b的前面，a = b, 排序完之后 a 还在 b 的前面(相对位置没有改变)，这就是稳定的排序
排完序之后，a跑到了b的后面，这就是不稳定的排序
排序的时间复杂度、稳定性
各排序时间复杂度和稳定性之间的比对
插入排序
直接插入排序
思想：
单趟排序的思想：
把后面的数与前一个数进行比较，如果比这个数小，就把前面的这个数往后挪动，如果比这个数大，就保持不动 (假设前面的数已经有序了)
多趟排序(整体思想)：
假设第一个数据有序，然后就进行比较，第二个数与第一个数进行比较，如果比这个数小，第一个数往后挪动，第二个数往前插入占领它的位置，这样就完成了单趟插入操作，
不断重复这种单趟的操作，从前往后不断有序，这就是直接插入排序的整体思想
单趟排序图示以及代码：
假设已经进行了很多次单趟排序，还剩最后一次单趟排序就完成了整体的排序，我这样假设是方便我们写代码，理解这个思路以及整体的思路，已经完成的单趟排序都是有序的
步骤：
①把要插入的数据存临时空间 tmp，空出来方便前面的数据往后挪
如果数据比前面的小就移动前面的数据到后面，然后再和前面的数据比较
②如果比前面的数据大，直接 break，因为单趟排序是从前往后的，前面已经有序了，可直接break
③最坏的情况下，end 直到走到 0，还没遇到比自己大的，那么这个数就是最小的，end-- 跳出循环，a[end+1] = tmp 任然满足
int end;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;整体排序以代码：
我们的 end 处于 n-1 的前一个，即 end 的位置是 end - 2，就是倒数第二个位置
所有 for循环的终止条件是 i < n - 1， i 从 0 开始插入排序，从前往后不断有序
//1,直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
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;
}
}时间复杂度
1，直接插入排序的时间复杂度：O(N*N)
单趟排序最好的情况是 O(1), 最坏的情况是 O(N), 所以时间复杂度取最坏 ：O(NxN)
2，什么情况下最好 ？
有序或者接近于有序
3，什么情况最坏？
逆序或者接近于逆序
希尔排序
希尔排序的就是直接插入排序的优化，也是建立在插入排序的基础上，所以先得了解插入排序的思想，才能更好的实现希尔排序
希尔排序的思想：
1，预排序(让数组接近有序，然后再直接插入排序)
2，直接插入排序
部分预排序的原理示意图
希尔排序是根据下面的示意图分组进行预排序
假设有n个数据， 间距为 gap = 3，
1，先对第一组的第一个元素进行排序
2，然后对第二组的第一个元素进行排序,
3，再对第三组的第一个元素排序, 看数据量的多少，我这里只分组到了第三组
根据 1 2 3的步骤 这样走完一趟是一轮，然后对每组的第二个元素进行插入排序，以此类推
希尔排序的单趟代码
希尔排序的单趟代码其实就是直接插入排序的单趟，只不过间距变成了 gap
//假设 gap = 3
int gap = 3
int end;
int tmp = a[end + gap]; // 由插入排序的 end + 1 变成了 end + gap
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end]; // 由插入排序的 end + 1 变成了 end + gap
end -= gap; //由插入排序的 end -- 变成了 end -= gap
}
else
{
break;
}
}
a[end + gap] = tmp; // 和插入排序的 end + 1 同理， end +1 变成了 end + gap
}希尔排序的完整代码
希尔的单趟排序就是直接插入排序的单趟思想，只是间距由 1 变成了 gap
1，在for循环中的结束条件是 i < n - gap, 从0 开始，最多到 n- gap的前一位
如图中的 12、3、5已经和前面的排序过了
2，为了控制 gap，我们让 gap 每次除以 3，为了让条件结束，最后要变成直接插入排序，也就是 gap = 1，所以我们每次除以 3 的时候就 加1 ，最后等于1的时候执行完成后跳出循环
//2,希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1; // gap 不断整除 3 最后加 1，最后一次就是直接插入排序
for (int i = 0; i < n - gap; ++i) // 直接插入排序的范围是 n-1,而这里就是 n-gap
{
int end = i; //end 从 0 开始，第一组的第一个，然后就是第二组的第一个，依次类推
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;
}
}
}时间复杂度
希尔排序的时间复杂度：大概等于 O(N^1.3), 要优于直接插入排序 O(N^2)
选择排序
选择排序
选择排序的思想：
每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
我们可以一次选择两个元素，提高代码的效率，每一次在待排的数据中选择最小，和最大的，最小的放到待排序列的前面，最大的放到待排序列的后面，然后不断缩小待排序范围，直到排序结束
单趟的示意图：
第一趟为例
假设max是找到最大的元素下标
min 是找到最小值的元素下标
先把这两个下标初始成第一个数的下标
然后在待排序的里面去找最大值和最小值最小值和数组的起始位置的元素交换
把最大值和数组最后一个元素交换
整体过过程及代码：
我们定义一个 begin 和 end ，begin指向数组的起始位置，end 指向数组末尾
当完成一次交换后，begin 和 end 已经找到了最大值和最小值，就缩小范围 begin++,end--
直到begin 和 end 相遇，这个和二分查找的判断条件很类似
注意：
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi, mini;
maxi = mini = begin;
for (int i = begin+1; i <= end; ++i) // 第一个位置已经给了begin，可以直接从begin+1 开始查找然后逐次比较
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}时间复杂度
选择排序的时间复杂度是: O(N*N)
最好最坏都是 O(N *N) ,不管最好还是最坏都要选择
堆排序
堆排序的实现和建堆等都在二叉树这一节已经介绍了
交换排序
冒泡排序
冒泡排序的思想：
重复地遍历要排序的数组，两个元素进行比较，如果他们的顺序错误就把他们交换过来。遍历数列是重复地进行直到没有再需要交换，也就是说该数组已经排序完成
单趟排序：
以最坏的情况逆序为例，假设有10个数，从第一个数开始和剩下的九个数进行比较，如果遇到比自己小的就交换
10个数需要比较9次，n个数需要比较 n - 1 次整体排序：
每次单趟排序结束后，就完成了一个数据的排序，每一次单趟后，要排的次数就少一个，单趟也是每次少一个
假设有10个数，第一次单趟需要走 9次，第二次单趟需要走 8 次...以此类推
10个数每次单趟完成之后都会进行交换也就是9个数都是比较后得到的结果，最后一个数不需要再比较了，大的都往后面排好了，所有10个数第一次需要走 9 次，第二次走8次...以此类推
单趟排序的示意图：
整体排序示意图：
综上所述：10个数据 第一次外层循环 9次，第二次8次，......直到为0
内层循环第一次比较 9 次，第二次比较8次....直到为0
每一层每一次执行都在减少一次，减少的原因是因为每一次都有一个数据排序完成
优化：我们可以定义一个 exchange = 0变量，如果单趟循环没有进行一次交换，可以直接break，该数组肯定有序了，只要有一次交换就不是有序的
整体代码：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//5,冒泡排序
//void BubbleSort(int* a, int n)
//{
// for (int i = 0; i < n - 1; ++i) //执行每次次数少一次
// {
// int exchange = 0;
// for (int j = 0; j < n - 1 - i; ++j) //单趟每次也少一次
// {
// if (a[j] > a[j + 1]) // 比较然后交换
// {
// Swap(&a[j], &a[j + 1]);
// exchange = 1;
// }
// }
// if (exchange == 0)
// {
// break;
// }
// }
//}
void BubbleSort(int* a, int n)
{
int end = n;
while (end > 0) // 外层循环 1 到 n 总次数第一次 n-1次，每次次数都在减少
{
int exchange = 0;
for (int i = 1; i < end; ++i) // 内层循环 1 到 end -1 总次数第一次 n-1,每次次数在减少，和上面定义的 i 和 j原理一样
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
--end;
}
}时间复杂度
冒泡排序的时间复杂度是 O(N^2)
快速排序
思路：通过找一个基准值来进行比较，把序列分成左右两个子序列，然后再进行递归处理
选择一个基准元素(key)：通常选择序列的第一个或最后一个元素作为基准元素，但也可以采用其他方法选取。
分割过程：将待排序的序列分成两个子序列，其中一个子序列的元素都比基准元素小（通常放在基准元素的左边），另一个子序列的元素都比基准元素大（通常放在基准元素的右边）。这个分割过程称为一趟排序。
递归处理：对两个子序列递归地进行快速排序，直到每个子序列中的元素都已排序。
快速排序的单趟排序有左右指针法、挖坑法、前后指针法
左右指针法
单趟排序的思想：我们定义一个key(基准元素)，如果是定义在左边，就让右边先走，如果定义在右边，就让左边先走
升序为例
以最右边的值为基准点 假设 a[end] = key (end = n-1)
1，定义两个指针 begin 和 end，
一个指向前，一个指向后
2，begin找比key小的数，end找比key大的数，找到了就停下来，没有找到就继续找3，当begin找到比key大的数，end找比key小的数就交换，直到相遇把相遇点和key进行交换(如果找到相等的数交换不交换都可以)
最后得到的结果就是确定了key的最终位置，左边的数都比key小，右边的数都比key大
为什么begin找小的数，而end找大的数
单趟排序的示意图(理想的情况下key最后落在中间位置，假设分布均匀的情况下)：
左右指针单趟排序代码：
在单趟排序的代码中 while (begin < end && a[begin] <= a[keyIndex]) ，为什么有begin < end
当我们指针相遇就停下来,防止错过，所有最多走到相遇
为什么需要判断条件需要加上begin < end 呢
//左右指针法
int PartSort1(int* a, int begin, int end)
{
int keyIndex = end; // 因为end会变化，所以我们记录 end 的下标
while (begin < end) //左右指针还没相遇
{
while (begin < end && a[begin] <= a[keyIndex]) //左边找大，只要是小的就++，找到就跳出内部的while循环，
{
++begin;
}
while (begin < end && a[end] >= a[keyIndex]) //右边找小，只要是大的就--，找到小的就跳出内部循环
{
--end;
}
Swap(&a[begin], &a[end]); //左右找到了一个大的和一个小的，进行交换
}
Swap(&a[begin], &a[keyIndex]); //两个指针相遇，和key进行交换
return begin; //返回交换后的下标
}为什么定义key在左边，就让右边先走，定义key在右边，就让左边先走？？？？
1，升序的情况下，得到的结果是：左边的数要比右边的小
2，当我们定义了右边作为key的时候，左边先走，左边找到才会停下来，然后右边去碰左边，相遇点就是比key大的值 (左边是找大,右边是找小)，左边遇到的值一定是比key大的那个数
3，为了符合最后一步与key的交换，把key和相遇点交换，这样key最后落的位置就是key的最终位置，左边的值都比key小，右边的值都比key大 (如果实在没理解可以根据画图让右边先走，慢慢就可以理解了)
为什么最后走完key最终落的位置就是这个位置呢？？？
左边找大，右边找小，最后和相遇点比key大的值交换，key的左边值比key小在遍历的过程中全部放到了左边，key的右边的值比key大都放到了右边
1，假设一个班级有60名学生，我们需要按照他们的成绩进行升序排序。假设你的成绩是第30名，也就是说，在完全排序的名单中，您的位置将是第30个。班级里的其他学生开始与你的成绩进行比较。所有成绩比你低的学生（即排名在30名之后的学生）都会移动到您的左侧，而所有成绩比你高的学生（即排名在30名之前的学生）都会移动到您的右侧。
2，这个过程就像是学生们在教室里根据成绩排队，你站在了中间，成绩比你低的学生站在了你的左边，成绩比你高的学生站在了你的右边。
3，当这个过程完成时，您的位置就固定了，因为所有比你成绩低的学生都已经站在了你的左边，所有比你成绩高的学生都已经站在了你的右边。这就像是在一个完全有序的班级名单中，你站在了第30个位置，因为前面有29名成绩比你低的学生，后面有29名成绩比你高的学生，
4，以你为媒介，分成左右区间左边都比你小，右边都比你大，再此基础上，左右两边是无序的，但是你自己是有序的,
整体思路：
我们在进行一次单趟排序后，确定了key的最终位置，理想的情况下，key在中间，分成了左右区间，左区间比key小，右区间比key大，然后不断细分。
左区间再次进行单趟排序，确定key的位置，右区间也进行单趟排序确定key的位置
再此分成左右区间，再此确定key的最后位置，不断走，直到分成不可在分割的子区间
这就像我们二叉树的后序遍历，先处理根，然后分成左右子树，再次处理根，再分
需要二叉树的基础才能更好的理解，可以多画几次图分割区间去理解代码
完整代码：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//左右指针法
int PartSort1(int* a, int begin, int end)
{
int keyIndex = end;
while (begin < end)
{
while (begin < end && a[begin] <= a[keyIndex])
{
++begin;
}
while (begin < end && a[end] >= a[keyIndex])
{
--end;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyIndex]);
return begin;
}
void QuickSort(int* a, int left, int right) //传过来的参数是 arr, 0, n-1
{
if (left >= right) // 递归的终止条件，如果是一个值不需要比较了
return;
int div = PartSort1(a, left, right); // 确定最后落的位置，排序key的位置
//[left,div-1] [div+1,right]
QuickSort(a, left, div - 1); //分割左区间
QuickSort(a, div + 1, right); //分割右区间
}优化：三数取中
最坏的情况下，当数据是有序或者接近有序的时候，每次我们找key找到的是最大的值，这样导致我们的递归树变的不平衡，导致时间复杂度是 O(N^N)
当我们每次取的是中间值的时候，递归就相对来说变得平衡，我们都知道二叉树的高度是 logN，每趟的时间复杂度是 O(N),所以最好的情况下，时间复杂度是 O(N*logN)
所以就有了三数取中，找到三个数中值为第二大的数，避免了快排的最坏情况
最坏和最好的情况如下图：
优化后得代码：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//6,快速排序
// 三数取中
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2; // 取三个数的中间下标
if (a[begin] < a[mid]) //三个数逐次比较
{
if (a[begin] > a[end])
return begin;
else if (a[mid] < a[end])
return mid;
else
return end;
}
else
{
if (a[mid] > a[end])
return mid;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
//左右指针法
int PartSort1(int* a, int begin, int end)
{
//三数取中
int midIndex = GetMidIndex(a, begin, end); // 找到三个数中第二大的数
Swap(&a[midIndex], &a[end]); //把第二大的数放到最后，作 key
int keyIndex = end;
while (begin < end)
{
while (begin < end && a[begin] <= a[keyIndex])
{
++begin;
}
while (begin < end && a[end] >= a[keyIndex])
{
--end;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[begin], &a[keyIndex]);
return begin;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int div = PartSort3(a, left, right);
//[left,div-1] [div+1,right]
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}优化：小区间优化
1，当数据量很大的时候，我们可以使用快排递归，但是当数据排序到只剩10个元素的时候(或者比较少的个数的时候)，每次递归调用函数都会建立栈桢，会带来一定的开销，所有我们可以再次优化我们的代码，使用小区间优化
2，小区间优化的就是当递归到只剩下少量元素（比如10个或更少）的子数组时，我们可以切换到直接插入排序来避免进一步的递归调用和栈空间的使用。
3，快速排序的时间复杂度是 O(N *logN)，但在处理小数据集时，递归调用和栈空间的开销可能会超过排序操作本身的开销。直接插入排序在处理小数据集时通常非常高效，其时间复杂度为 O(n^2)，但在小数据集上，这个二次复杂度通常不是问题，因为 n 的值很小。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int len = right - left + 1; //计算个数
if (len <= 10)
{
//调用直接插入排序
InsertSort(a + left, len); //调用插入排序
}
else
{
int div = PartSort3(a, left, right);
//[left,div-1] [div+1,right]
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
}
}挖坑法
单趟排序的思想：
我们在理解左右指针法的基础上，挖坑法原理和左右指针法类似
1，把右边挖坑，左边先走，左边挖坑，右边先走，和左右指针法原理一样
2，右边作坑结合示意图，左边找大填坑，右边找小填坑
3，直到两个指针相遇，直接把key填相遇点(得到的结果也是和左右指针一样，左边的比ey小，右边的比key大)
挖坑法的单趟代码：
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int midIndex = GetMidIndex(a, begin, end); //三数取中
Swap(&a[midIndex], &a[end]);
int key = a[end];
while (begin < end)
{
while (begin < end && a[begin] <= key)
++begin;
a[end] = a[begin]; //找到大的就填坑
while (begin < end && a[end] >= key)
--end;
a[begin] = a[end]; //找到小的就填坑
}
a[begin] = key; //两个指针相遇，把key填相遇点
return begin; //返回key的最后下标
}前后指针法
单趟排序的思想：
前后指针法，代码简单，理解起来也相对容易
1，先确定 key
2，定义两个指针，一个prev，一个cur，prev在cur的前面，还是升序为例，cur不断找小，如果找到小的prev就加一位，然后再进行交换，意思就相于把比key小的都往前面丢，交换的过程中比key 大的数就被换到后面去了
3，当走完所有的数都没找到小的就++prev，然后交换key
前后指针的单趟代码：
代码和画图两者结合就可以理解这段单趟排序的代码
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int keyIndex = end;
int prev = begin - 1;
int cur = begin;
while (cur < end) //当cur = end的时候跳出循环
{
if (a[cur] < a[keyIndex] && ++prev != cur) //当cur == prev 的时候不需要进行交换
Swap(&a[cur], &a[prev]);
++cur; // cur一直走，在if条件中，只要遇到小的就++prev然后交换
}
Swap(&a[++prev], &a[keyIndex]); //cur走到了末尾然后把key给++prev
return prev;
}快速排序非递归法
思路：递归改非递归，要么改成循环的实现，要么改成栈/队列实现
非递归写法就是和递归的思路是一样的
1，创建一个空栈（或队列）
将待排序数组的起始和末尾索引作为初始区间，压入栈（或队列）中。
2，当栈（或队列）非空时，执行以下步骤：
弹出栈顶的元素，这通常是一个区间（左边界和右边界）。
对这个区间进行单趟快速排序，确定key又可以继续划分区间
3，处理子区间：
划分之后又要处理子区间
如果基准值的左边还有元素（即左子区间非空），将左子区间的左右边界压入栈（或队列）中。
如果基准值的右边还有元素（即右子区间非空），将右子区间的左右边界压入栈（或队列）中。
需要注意的是，通常我们不需要对只有一个元素的区间进行排序，因此在压入栈（或队列）之前可以做一个简单的判断。
4，当栈（或队列）为空时，说明所有的子区间都已经处理完毕，此时整个数组已经有序。
5，最后使用完栈之后记得销毁栈，因为栈是 malloc 出来的，不去释放，可能会造成内存泄漏
代码实现
我们得先实现一个栈，PartSort1 调用单趟快速排序
非递归的思想和递归的思想是一样的
//快排非递归写法
void QuickSortNonR(int* a, 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 div = PartSort1(a, begin, end); //对该区间进行单趟快速排序
//左区间[begin,div-1] 右区间[div+1,end]
if (div + 1 < end) // 当只有一个元素的时候，不需要排序了，和递归的结束条件类似
{
StackPush(&st, end); //先入右区间的右下标
StackPush(&st, div+1); //再入右区间的左下标
}
if (begin < div - 1)
{
StackPush(&st, div - 1); //入左区间的右下标
StackPush(&st, begin); // 入左区间的左下标
}
}
StackDestory(&st); //销毁栈
}
时间复杂度
快速排序在最坏的情况下，时间复杂度是O(N^2)，有了三数取中之后，最坏的情况不再出现，所以时间复杂度是 O(N*logN)
归并排序
递归写法
再此之前，我们一个都做过合并两个有序数组的题目，合并的过程就和这个过程原理是类似的，如果没有做过的小伙伴可以现在再次熟悉一下
合并两个有序数组的思路：
有两个数组 num1, 和 num2，我们可以开一个临时空间 tmp，存放排好的数组，然后拷贝回去num1，这个题目有很多解法，这只是其中的一种
合并两个有序数组代码：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int*tmp = (int*)malloc(sizeof(int)*nums1Size);
int begin1 = 0, end1 = m - 1;
int begin2 = 0, end2 = n - 1;
int index = 0;
while (begin1 <= end1 && begin2 <= end2) {
if (nums1[begin1] < nums2[begin2])
tmp[index++] = nums1[begin1++];
else
tmp[index++] = nums2[begin2++];
}
while (begin1 <= end1)
tmp[index++] = nums1[begin1++];
while(begin2<=end2)
tmp[index++] = nums2[begin2++];
for(int i = 0; i<nums1Size; ++i)
{
nums1[i] = tmp[i];
}
free(tmp);
tmp = NULL;
}归并排序的思想：
归并排序是一种分治的策略算法
1，将数组分成两个数组，和合并有序数组的思路是一样的，但是现实的情况下分出来的两个数组大多数情况下都不是有序的，我们就不断分割，分成不可再分割的子数组
根据图示观察归并的过程，子数组有序了，再归并起来，上一层(图中的下一层)的子数组也有序，层层有序，最后整体也有序了
2，图例中只是整体的思想，实际操作中我们不可能开出这么多零零散散的空间
我们可以动态开辟出一个和原数组一样大小的临时空间，在这个临时空间中进行归并的实现，最后再拷贝回原数组
归并排序的过程：
在先递归分解的基础上，这只是其中一层，层层归并，这样就可以把整个数组归并完成
归并排序的代码：
//7,归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right) //只有一个数的时候结束递归条件
return;
int mid = (left + right) / 2;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
int begin1 = left, end1 = mid; //合并有序数组 / 归并
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
for (int i = left; i <= right; ++i) //拷贝回原来的数组
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n); //开一个和数组a一样大的临时空间
if (tmp == NULL)
{
return;
}
_MergeSort(a, 0, n - 1, tmp); //调用子函数，方便用子函数递归
free(tmp);
tmp = NULL;
}非递归写法
思路： 归并排序的基本思路是将数组分成两半，对每半递归地进行排序，然后将两个已排序的半部分合并成一个有序的数组。
最主要的就是我们如何分割区间
图解：
代码实现：
//归并排序非递归写法
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
int left = begin1;
int right = end2;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
for (int i = left; i <= right; ++i)
{
a[i] = tmp[i];
}
}
void MergeSortNonR(int* a, int n)
{
int* tmp = malloc(sizeof(int) * n); // 开一个临时空间归并数据，和递归写法是一样的
if (tmp == NULL)
return NULL;
int gap = 1; //控制区间个数
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n - 1;
MergeArr(a, begin1, end1, begin2, end2, tmp); //归并每次分割的区间
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}时间复杂度
归并排序的时间复杂度：O(N*logN)
计数排序
计数排序的思想：
逻辑不复杂，但是有点抽象
- 找出待排序的数组中最大和最小的元素：这一步是为了确定接下来要开辟的额外数组（称为“计数数组）的大小,也可以说是确定范围，将这些开出的空间全部初始化为0。
- 统计数组中每个值为 i 的元素出现的次数：遍历输入数组，用计数数组的第 i 项来记录值为 i 的元素出现的次数，出现一个就累加一次。
- 反向填充目标数组(排序)：从计数数组按照顺序中把元素填充回输入数组
举个简单的例子，假设有一个数组
[1, 4, 2, 2, 4, 1]，我们可以这样进行计数排序：
- 找到最大值和最小值，分别是 4 和 1。
- 初始化一个大小为 5 的计数数组（因为 4-1+1=4），并将所有元素初始化为 0。
- 遍历输入数组，统计每个元素出现的次数：计数数组变为
[0, 2, 2, 0, 2]，意思是下标为0，统计输入数组中0出现的个数，其它一样的道理。- 从输入数组第一个元素开始，根据计数数组的值依次输入到输入数组中，最终得到排序后的数组
[1, 1, 2, 2, 4, 4]。注意：假设有数组 [1000, 1005,5000,4000]，我们可以用相对位置来记录，这样可以节省一些空间，因为没有必要开辟前面的999个空间
相对位置的计算：
计数排序的代码：
//8,计数排序
void CountSort(int* a, int n)
{
// 1，找最大值和最小值，确定范围
int max = a[0];
int min = a[0];
for (int i = 0; i < n; ++i)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
// 2，开辟最大值和最小值之差的空间
int* countArr = (int*)malloc(sizeof(int) * range);
if (countArr == NULL)
{
return;
}
memset(countArr, 0, sizeof(int) * range); // 初始化里面所有的值为 0
//统计相对位置的个数，有相同的数就 ++
for (int i = 0; i < n; ++i)
{
countArr[a[i] - min]++;
}
// 3，排序
int index = 0;
for (int j = 0; j < range; ++j)
{
while (countArr[j]--)
{
a[index++] = j + min; // 下标 + 最小值，返回原数据到输入数组
}
}
free(countArr);
countArr = NULL;
}时间复杂度
标签：搞定,单趟,end,int,begin,算法,key,排序 From： https://blog.csdn.net/m0_63207201/article/details/139273391时间复杂度：O(n+k)
空间复杂度：O(k)，其中k是输入数据的范围。这是因为我们需要一个大小为k的计数数组来存储每个元素的计数。
需要注意的是，计数排序是一种非比较型整数排序算法，其时间复杂度在数据范围k不大的情况下优于其他排序算法。但是，当k很大时，计数排序的空间复杂度会非常高，因此它并不适用于所有情况。此外，计数排序还要求输入数据必须是有确定范围的整数，否则无法使用。