目录ba
2.3.3 快速排序（也算是老朋友了，qsort大家应该用挺多的哈） 🚀
C语言的入门篇进阶篇和深剖篇都整理在这里了哈。然后这里是个人主页，比点头像更好找文章哈。
作者和朋友建立的社区：非科班转码社区-CSDN社区云💖💛💙
期待hxd的支持哈🎉 🎉 🎉
最后是打鸡血环节：改变的确很难，但结果值得冒险，拿出点勇气来。路还很长，现在才刚开始而已。过去无可挽回，未来可以改变。🚀 🚀 🚀
1.首先说明，代码里面有实现思想以及非常详细的解释和实现时容易遇到的误区，有理解思想或者不想看长篇大论的伙伴们可以直接尝试看代码哈。
强烈建议进收藏夹吃灰哈！
（作者后面应该还会继续补充，把平常常见的都加进来哈，比如桶排序，计数排序，基数排序等哈，因为作者作者的博客本身就是复习为主，所以家人们放心博客质量哈）
2.源代码中有测试各排序性能的代码及测试各排序的代码（test.c）
PS:本篇作图为作者好朋友可欣提供💖💛💙
1. 排序的概念及其运用 🚀
1.1 排序的概念 🚀
排序 ：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。内部排序 ：数据元素全部放在内存中的排序。外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序运用 🚀
给你一串数据，我们可以按照一些条件将数据按照递增或者递减的方式进行排列，比如计算机里面的文件：
排序在生活中还是很有用的，比如我们可以通过首字母很快找到通讯录的联系人，找到最大值和最小值，精确找到某一天的消息…
总之，有用，好好学。我们今天讲的所有排序都属于内部排序。
1.3 常见的排序算法 🚀
在这里我们可以知道，希尔排序是插入排序的优化，堆排序是选择排序的优化，快数排序是交换排序的优化。
2. 常见排序算法的实现 🚀
Sort.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<time.h> #include<assert.h> #include<stdlib.h> #include<string.h> #include"Stack.h" void Print(int* arr, int sz); //2 void InsertSort(int* arr, int sz); //3 void ShellSort(int* arr, int sz); //1 void BubbleSort(int* arr, int sz); //4 void SelectSort(int* arr, int sz); //6 void HeapSort(int* arr, int sz); //5 void QuickSort(int* arr, int begin, int end); void QuickSortNonR(int* arr, int begin, int end); //7 void MergeSort(int* arr, int begin, int end); void MergeSortNonR(int* arr, int n);Sort.c
//后面用的多,直接写成函数方便一点 void Swap(int* p, int* q) { int tmp = *p; *p = *q; *q = tmp; } void Print(int* arr, int sz) { for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); }
1W数据测试各排序时间
1000W数据测试各排序时间（去掉冒泡，插入，选择）
2.1 插入排序 🚀
2.1.1 基本思想 🚀
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列 。从右往左，找到 刚好比这本书高的书，放在它右边就行了。
2.1.2 直接插入排序 🚀
当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移
直接插入排序的特性总结：1. 元素集合越接近有序，直接插入排序算法的时间效率越高2. 时间复杂度： O(N^2)3. 空间复杂度： O(1) ，它是一种稳定的排序算法4. 稳定性：稳定2.1.3 希尔排序( 缩小增量排序 ) 🚀
希尔排序法又称缩小增量法。希尔排序法的基本思想是： 先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达 =1 时，所有记录在统一组内排好序 。
希尔排序的特性总结🚀
1. 希尔排序是对直接插入排序的优化。2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。3. 希尔排序的时间复杂度不好计算，因为 gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：《数据结构 (C 语言版 ) 》 --- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
4. 稳定性：不稳定
我们就记希尔时间复杂度是O(n^1.3)就可以了哈。
插入和希尔排序的实现 🚀
2.2 选择排序 🚀
2.2.1 基本思想 🚀
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。2.2.2 直接选择排序 🚀
在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 ) 的数据元素若它不是这组元素中的最后一个 ( 第一个 ) 元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2] （ array[i+1]--array[n-1] ）集合中，重复上述步骤，直到集合剩余 1 个元素
注意特殊情况：
此时由于max在begin位置，当min和begin互换时，max的位置其实是min，但是程序只会交换begin和end。
解决方案：
交换一次后判断max是不是begin，是的话max的值就是min。同理，反过来也成立。
直接选择排序的特性总结 🚀
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用2. 时间复杂度： O(N^2)3. 空间复杂度： O(1)4. 稳定性：不稳定2.2.3 堆排序（点我看前面堆详解博客） 🚀
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
直接选择排序的特性总结 🚀
1. 堆排序使用堆来选数，效率就高了很多。2. 时间复杂度： O(N*logN)3. 空间复杂度： O(1)4. 稳定性：不稳定
直接选择和堆排序的实现 🚀
我们这里是选了两个数，相较于选一个优化了
2.3 交换排序 🚀
2.3.1基本思想 🚀
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。2.3.2冒泡排序（属于老朋友了是哈哈） 🚀
冒泡排序的特性总结 🚀
1. 冒泡排序是一种非常容易理解的排序2. 时间复杂度： O(N^2)3. 空间复杂度： O(1)4. 稳定性：稳定2.3.3 快速排序（也算是老朋友了，qsort大家应该用挺多的哈） 🚀
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。注意，这里讲的主要是思想，图和PartSort代码没有关系，画的时候只追求了 比key大的在一边，比key小的在另一边这个条件。
这张图主要是展示边界控制的问题。
快速排序有的讲，这里有四种实现方法// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { if(right - left <= 1) return; // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = partion(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right) // 递归排[left, div) QuickSort(array, left, div); // 递归排[div+1, right) QuickSort(array, div+1, right); }上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有：1. hoare版本 🚀
为什么不能第一个开始左指针先走呢？
第一个开始左指针走之前不会有什么问题，但是到了最后一步左指针会找到比key值大的数，然后停下和key交换。
而如果是右指针的话，它找到的是比key小的数，交换不会出现任何问题。最后一个开始右指针先走同理。
2. 挖坑法 🚀
我们先看一下单次排序的动图：
顺着来就好，不像hoare版本需要考虑一些小小的细节。
3. 前后指针版本 🚀
我们先来看一下单趟动图：
这个方法的核心就是保证prev指向及prev之前的所有数据的值都小于key。
- 当cur还没遇见比key大的值的时候，prev是跟着cur一起移动的。
- 当cur第一次遇见比key大的值的时候，prev停下，此时prev包括prev前的数据都是小于key的。
- 当cur再一次遇见比key小的数据时，prev的下一个一定是比key大的数据，所以prev++和cur交换。
- 直到遍历结束。prev之前包括prev都比key小，key和prev交换。
- key之前都比key小，key之后都比key大。
然后我们来考虑一下key取最右边：
为了保证prev包括prev前的数据都是小于key的。 prev就不能从0位置开始了，万一第一个数就大于key呢？
接下来的路与取左边完全一样，直到cur在key位置的时候：
prev包括prev前的数据都是小于key的。（哇，这话我说了多少次）
- 在左边的时候prev前面有key，所以可以直接交换。
- 在右边的时候直接交换会把小的数换到右边，所以交换的时候是换prev++的位置。
4.非递归法 🚀
2.3.3 快速排序优化 🚀
1. 三数取中法选 key
2. 递归到小的子区间时，可以考虑使用插入排序（因为已经趋近有序，直接插入会非常快）
快速排序的特性总结 🚀
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫 快速 排序2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(logN)（因为是递归，所以高度是logN，而每次开辟O（1）个空间，相乘就是logN）4. 稳定性：不稳定
2.4 归并排序 🚀
2.4.1 基本思想 🚀
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
2.4.2 递归实现 🚀
2.4.3 非递归实现 🚀
归并排序的特性总结 🚀
1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。2. 时间复杂度： O(N*logN)3. 空间复杂度： O(N)4. 稳定性：稳定
3.补充非比较排序——计数排序 🚀
比如我们有个单词Hippopotomonstrosesquippedaliophobia
我们想把它的字母排个序，怎么排好呢？
根据观察，这个单词里面含有大量重复的字母，我们是不是可以数一下这些字母出现的次数， 然后按顺序写下来就好了？
计数排序的原理就是这个，它对于大量且集中的数据有奇效。
思路：
1. 统计相同元素出现次数 。
2. 根据统计的结果将序列回收到原来的序列中。
网上动图
有负数也可以哈，因为这里用的相对位置，不是绝对位置。
代码
//用相对映射，不用绝对映射 void CountSort(int* a, int n) { // 1 2 2 4 3 2 5 int min = a[0]; int max = a[0]; int i = 0; for (i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; int* countA = (int*)calloc(range,sizeof(int)); assert(countA); //计数 //5000 0 /// 100 150 200 210 250 0-151 min 100 for (i = 0; i < n; i++) { countA[a[i] - min]++; } //排序 int j = 0; for (i = 0; i < range; i++) { while (countA[i]--) { a[j++] = i + min; } } }
4.排序算法复杂度及稳定性分析 🚀
5.源代码 🚀
Sort.h 🚀
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include"Stack.h"
void Print(int* arr, int sz);
//2
void InsertSort(int* arr, int sz);
//3
void ShellSort(int* arr, int sz);
//1
void BubbleSort(int* arr, int sz);
//4
void SelectSort(int* arr, int sz);
//6
void HeapSort(int* arr, int sz);
//5
void QuickSort(int* arr, int begin, int end);
void QuickSortNonR(int* arr, int begin, int end);
//7
void MergeSort(int* arr, int begin, int end);
void MergeSortNonR(int* arr, int n);Stack.h 🚀
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDateType;
typedef struct Stack {
STDateType* arr;
int top;
int capacity;
}Stack;
//初始化
void InitStack(Stack* pst);
//入栈
void PushStack(Stack* pst, STDateType x);
//出栈
void PopStack(Stack* pst);
//取栈顶
STDateType StackTop(Stack* pst);
//判空
bool EmptyStack(Stack* pst);
//求数据个数
int StackSize(Stack* pst);
//销毁
void DestoryStack(Stack* pst);Stack.c 🚀
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void InitStack(Stack* pst)
{
//int newcapacity = pst->capacity = 0 ? 4 : pst->capacity * 2;
Stack* new = (Stack*)malloc(sizeof(Stack));
if (new == NULL)
{
perror("InitStack:");
exit(-1);
}
pst->arr = new;
pst->capacity = 1;
pst->top = 0;
}
//入栈
void PushStack(Stack* pst, STDateType x)
{
assert(pst);
if (pst->capacity == pst->top)
{
int newcapacity = pst->capacity * 2;
STDateType* new = (STDateType*)realloc(pst->arr,sizeof(STDateType) * newcapacity);
if (new == NULL)
{
perror("InitStack:");
exit(-1);
}
pst->arr = new;
pst->capacity = newcapacity;
}
pst->arr[pst->top] = x;
pst->top++;
}
//出栈
void PopStack(Stack* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//取栈顶
STDateType StackTop(Stack* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->arr[pst->top - 1];
}
//判空
bool EmptyStack(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//求数据个数
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
//销毁
void DestoryStack(Stack* pst)
{
assert(pst);
free(pst->arr);
pst->capacity = 0;
pst->top = 0;
}Sort.c 🚀
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//后面用的多,直接写成函数方便一点
void Swap(int* p, int* q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
void Print(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//思想：冒泡其实没啥说的，注意第二个循环的-1，因为我们
//这里用的是arr[j]和arr[j+1]小心越界的问题
void BubbleSort(int* arr,int sz)
{
int i = 0;
int j = 0;
for (i = 0; i < sz; i++)
{
for (j = 0; j < sz-i-1; j++)
{
if (arr[j] > arr[j + 1])
Swap(&arr[j], &arr[j + 1]);
}
}
}
//思想：开始让第一个数有序，然后从后一个数插入，
//如果后一个数小于前面的数，前面的数就往后挪动
//注意不管是哪种情况退出，最后都是把数据放到
//end+1，所有干脆我们就放在外面
void InsertSort(int* arr, int sz)
{
for(int i = 0; i < sz - 1;i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
//思想：先对数组进行预排序，预排序是为了
//直接插入更快，越有序，直接插入就越快，这
//也是希尔快的原因，预排序完了就直接插入排序
//预排序：分组(离相同gap)为一组进行插入排序
void ShellSort(int* arr, int sz)
{
// 1、gap > 1 预排序
// 2、gap == 1 直接插入排序
int gap = sz;
while (gap>1)
{
//保证最后为直接插入排序
gap = gap / 3 + 1;
//这里i++是使多组预排序同时进行
for (int i = 0; i < sz - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
//思路:选两个值的下标,开始都在左边，然后用一个记录下标的cur去遍历数组，
// 一个记录最大(maxi)，一个记录最小(mini)，然后遍历数组把最小的放
// 在左边，最大的，放在右边，直到left,right相遇
void SelectSort(int* arr, int sz)
{
int left = 0;
int right = sz - 1;
while (left<right)
{
int cur = left+1;
int mini = left;
int maxi = left;
//这里注意要等于哈，不然最后一个值就比掉了
//作者开始写的时候就画图搞了半天QAQ
while (cur <= right)
{
if (arr[cur] > arr[maxi])
{
maxi = cur;
}
if (arr[cur] < arr[mini])
{
mini = cur;
}
cur++;
}
Swap(&arr[left], &arr[mini]);
//如果left==maxi left就会
//和mini交换，要更新maxi
if (left == maxi)
{
maxi = mini;
}
Swap(&arr[right], &arr[maxi]);
left++;
right--;
}
}
//hoare
//思路：左边为key，右边先走，找小，左边再走，找大，然后左右交换
//一直循环直到相遇，因为是右边先走，左边已经是找小
//停住了，所有能保证相遇位置大于等于a[jeyi]，然后
//交换a[keyi]和相遇位置的值，这样a[keyi]左边值就
//比他小，右边值就比他大
int PartSort1(int* arr, int left, int right)
{
int keyi = left;
while (left < right)
{
//右找小 注意：keyi在左边就右边先走
//要注意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;
}
//挖坑法
//思路:左边为key，先存起来，变成坑，左右两边一个变量
//右边先走，找小，然后交换，左边找大，然后交换
//最后把key的值给相遇位置
int PartSort2(int* a, int left, int right)
{
int pi = left;
int qi = right;
int key = a[left];
while (pi < qi)
{
//右找小
while (a[qi] > key && pi < qi)
{
qi--;
}
a[pi] = a[qi];
//左找大
while (a[pi] < key && pi < qi)
{
pi++;
}
a[qi] = a[pi];
}
a[qi] = key;
return qi;
}
int GetMidIndex(int* a, int left, int right)
{
//int mid = (left + right) / 2;
int mid = left + (right - left) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//前后指针法
//左边为keyi，用两个变量存储left和left+1，cur去找小，
//找到了prev++再交换然后cur++，没有找到就cur++,
//这样可以保证让prev到cur的值都大于等于a[keyi]
//最后交换a[keyi]和a[prev]
int PartSort3(int* a, int left, int right)
{
//yysy，自己实现不加也行
//下面这两句也是优化，处理了有序O(N^2)的情况
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int cur = left + 1;
int prev = left;
int keyi = left;
while (cur <= right)
{
//这一步很巧哈，可以多理解一下
//注意是前置++
if (a[cur] < a[keyi] && a[++prev] != a[cur])
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
//递归
void QuickSort(int* arr, int begin, int end)
{
// 子区间相等只有一个值或者不存在那么就是递归结束的子问题
if (begin >= end)
return;
//小区间优化
// 小区间直接插入排序控制有序
//yysy，自己实现不加也行
if (end - begin + 1 <= 10)
{
InsertSort(arr + begin, end - begin + 1);
}
else
{
int keyi = PartSort3(arr, begin, end);
// [begin, keyi-1]keyi[keyi+1, end]
QuickSort(arr, begin, keyi - 1);
QuickSort(arr, keyi + 1, end);
}
}
//非递归
void QuickSortNonR(int* arr, int begin, int end)
{
Stack st;
InitStack(&st);
PushStack(&st, begin);
PushStack(&st, end);
while (!EmptyStack(&st))
{
int right = StackTop(&st);
PopStack(&st);
int left = StackTop(&st);
PopStack(&st);
//left keyi-1 keyi+1 right
int keyi = PartSort1(arr, left, right);
if (left < keyi-1)
{
PushStack(&st, left);
PushStack(&st, keyi-1);
}
if (keyi + 1 < right)
{
PushStack(&st, keyi + 1);
PushStack(&st, right);
}
}
}
//升序建大堆
先找左右小的孩子
//再和root的比 比root小就交换
//root等于那个要交换的孩子 孩子再选 然后迭代
void AdjustDown(int* arr,int root,int sz)
{
//默认左孩子
int child = root * 2 + 1;
int parent = root;
while (child<sz)
{
1、选出左右孩子中大的那个
if (child + 1 < sz && arr[child + 1] > arr[child])
child++;
//2、如果孩子大于父亲，则交换，并继续往下调整
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//思想：用向下调整算法建大堆(升序)，然后把堆顶的数据
//换到最后，然后缩小数据范围，再次向下调整，反复如此
void HeapSort(int* arr, int sz)
{
//向下调整--建大堆 O(N)
int curpos = (sz - 1 - 1) / 2;
while (curpos >= 0)
{
AdjustDown(arr, curpos, sz);
curpos--;
}
//end为最后一个元素下标
int end = sz - 1;
while (end >0)
{
Swap(&arr[0], &arr[end]);
//每次从0开始向下调
AdjustDown(arr, 0, end);
end--;
}
}
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
if (begin >= end)
return;
//先分后合
//为了防止数据溢出
int mid = begin + (end - begin) / 2;
//注意这里我们分成 begin - mid 和 mid+1 - end
//分成 begin - mid-1 和 mid - end 有bug (1,2)会死循环
int begin1 = begin; int end1 = mid;
int begin2 = mid+1; int end2 = end;
_MergeSort(arr, tmp, begin1, end1);
_MergeSort(arr, tmp, begin2, end2);
//printf("begin1:%d end1:%d \nbegin2:%d end2:%d\n", begin1, end1, begin2, end2);
//开始归
int i = begin;
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++];
//注意第三个参数是字节大小.....开始还以为是上面错了，找半天
//注意要加上begin 因为并不是每次都是初始位置
memcpy(arr + begin, tmp + begin, (end - begin + 1)*sizeof(int));
}
//思想：先分再合
//注意我们要先把排号的数据先放进tmp数组，
//然后把数组的数据拷回arr
void MergeSort(int* arr, int begin, int end)
{
int* tmp = (int*)malloc((end-begin+1) * sizeof(int));
assert(tmp);
//避免重复开辟空间就用副本函数
_MergeSort(arr, tmp, begin, end);
free(tmp);
}
//思想：不分，直接和，注意和快排转非递归不一样，快排是前序，
//所以转非递归用栈和队列都可以，但是后续不好那么搞，
//我们直接暴力求
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(n * sizeof(int));
assert(tmp);
int gap = 1;
int begin1 = 0; int end1 = 0;
int begin2 = 0; int end2 = 0;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
begin1 = i; end1 = i + gap - 1;
begin2 = i + gap; end2 = i + 2 * gap - 1;
//如果 end1 越界
if (end1 >= n)
end1 = n - 1;
//如果 begin2 越界 end2 越界
if (begin2 >= n && end2 >= n)
{
begin2 = n;
end2 = n - 1;
}
//如果 end2 越界
if (begin2 < n && end2 >= n)
end2 = n - 1;
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
while (begin1 <= end1)
tmp[index++] = arr[begin1++];
while (begin2 <= end2)
tmp[index++] = arr[begin2++];
}
memcpy(arr,tmp,n*sizeof(int));
gap *= 2;
}
free(tmp);
}
test.c 🚀
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void TestOP()
{
srand((unsigned int)time(0));
const int N = 10000000;
int* a1 = (int*)malloc(sizeof(int) * N);
assert(a1);
int* a2 = (int*)malloc(sizeof(int) * N);
assert(a2);
int* a3 = (int*)malloc(sizeof(int) * N);
assert(a3);
int* a4 = (int*)malloc(sizeof(int) * N);
assert(a4);
int* a5 = (int*)malloc(sizeof(int) * N);
assert(a5);
int* a6 = (int*)malloc(sizeof(int) * N);
assert(a6);
int* a7 = (int*)malloc(sizeof(int) * N);
assert(a7);
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, 0, N-1);
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("BublleSort:%d\n", end7 - begin7);
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("MergeSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
void test1()
{
int arr[] = { 1,7,2,5,3,4,9,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
//InsertSort(arr, sz);
//BubbleSort(arr, sz); //1
//SelectSort(arr, sz);
//QuickSort(arr, 0,sz-1);
//QuickSortNonR(arr, 0, sz - 1);
//HeapSort(arr, sz);
//ShellSort(arr, sz);
//MergeSort(arr, 0, sz-1);
//MergeSortNonR(arr, sz);
Print(arr, sz);
}
int main()
{
//test1();
TestOP();
return 0;
}补充内容🚀
有些初学的小伙伴在私信问作者平时在哪里刷题，这里作者推荐牛客网哈，当然也有小伙伴说leetcode呢，yysy呀，对新手不太友好。作者当时刚开始学C语言的时候，就是在牛客网把那基础题140道刷完了，很有帮助哈。
最后的最后，创作不易，希望读者三连支持💖
赠人玫瑰，手有余香💖
转载自CSDN-专业IT技术社区
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_62700590/article/details/124291850
