广西防城港建设厅网站,什么是响应网站设计,网站建设展板,网页设计网站免费【数据结构基础】之八大排序(C语言实现#xff09; #x1f427; 冒泡排序♈️ 冒泡排序原理及代码实现♈️ 稳定性分析 #x1f427; 选择排序♈️ 选择排序原理及代码实现♈️ 稳定性分析 #x1f427; 插入排序♈️ 插入排序的原理及代码实现♈️ 稳定性分析 #x1f4… 【数据结构基础】之八大排序(C语言实现 冒泡排序♈️ 冒泡排序原理及代码实现♈️ 稳定性分析 选择排序♈️ 选择排序原理及代码实现♈️ 稳定性分析 插入排序♈️ 插入排序的原理及代码实现♈️ 稳定性分析 希尔排序♈️ 希尔排序的原理及其代码实现♈️ 希尔排序的时间复杂度分析♈️ 稳定性分析 堆排序♈️ 稳定性分析 归并排序♈️ 归并排序递归版本♈️ 归并排序非递归版本♈️ 归并排序的时间复杂度和空间复杂度分析♈️ 稳定性分析 快速排序♈️ 快速排序递归实现(Hoare版本-----多坑版)♈️ 快速排序递归实现挖坑法♈️ 快速排序递归实现前后指针法♈️ 快速排序非递归实现♈️ 快速排序的三个优化 三数取中 小区间优化 三路划分加随机取数 ♈️ 快速排序时空复杂度分析♈️ 稳定性分析 计数排序♈️ 原理及代码♈️ 时空复杂度♈️ 稳定性分析 内排序与外排序 性能测试与排序正确性测试♈️ 正确性测试 冒泡排序 选择排序 插入排序 希尔排序 堆排序 快速排序 归并排序 计数排序 ♈️ 性能测试 前言算法和数据结构是有一定的关联的八大排序算法在数据结构里算是比较重要的一个部分今天本篇博客将介绍八大排序算法的原理和实现。 可视化工具及动画演示----旧金山大学usfca数据结构可视化工具 博客主页 小镇敲码人 热门专栏数据结构与算法 欢迎关注点赞 留言 收藏 任尔江湖满血骨我自踏雪寻梅香。 万千浮云遮碧月独傲天下百坚强。 男儿应有龙腾志盖世一意转洪荒。 莫使此生无痕度终归人间一捧黄。 ❤️ 什么你问我答案少年你看下一个十年又来了 冒泡排序
♈️ 冒泡排序原理及代码实现 冒泡排序应该我们大家绝大部分人都接触过因为很简单所以常常出现在教科书中用来启发学生它重复地访问要排序的元素序列依次比较两个相邻的 元素如果顺序如从大到小、首字母从Z到A错误就把他们交换过来。访问元素的工作是重复地进行直到没有相邻元素需要交换也就是说该元素序列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到序列的顶端升序或降序排列就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样故名“冒泡排序”。----部分节选自百度百科 冒泡排序可视化演示及工具 代码实现
// 冒泡排序
void BubbleSort(int* a, int n)
{int flag 0;//设置标志变量优化for (int i 0; i n - 1; i)//排序n个数需要n-1趟{flag 0;for (int j 0; j n-i-1; j){if (a[j] a[j 1])//如果满足交换条件交换{flag 1;//如果存在交换将flag设置为1Swap(a[j], a[j 1]);}}if (flag 0)//如果这一趟没有数交换说明已经有序结束排序{break;}}
}冒泡排序排n个数升序每一趟排完后最大的数剩下的数里面都到了正确的位置所以不用管了。只需要n-1个是因为后面的数都到了正确的位置那剩下一个数也一定在正确的位置。 时间复杂度ON^2
♈️ 稳定性分析
冒泡排序是一种稳定的算法排序首先解释下什么叫做稳定性稳定性就是在排序中相同的元素在排序后仍然保持之前的相对位置就好比1 2 1 4 3使用冒泡排序升序排列后那两个1的相对位置会发生变化吗答案是不会冒泡排序是相邻的元素你大于我或者你小于我就会交换等于是不会交换的所以冒泡排序是一种稳定的排序。 选择排序
♈️ 选择排序原理及代码实现 选择排序的工作原理升序是每次从剩下的元素序列里面找到最小的元素放到已经有序的序列后面直到没有元素。选择排序可视化演示及工具 代码实现
// 选择排序
void SelectSort(int* a, int n)
{int i 0;int j 0;int mini 0;//创建变量保存当前最小值的下标for (i 0; i n-1; i)//n-1趟就排完了{mini i;for (j i; j n; j){if (a[mini] a[j])//找出目前最小的元素下标{mini j;}}if(mini ! i)//如果这个下标不是i位置就交换Swap(a[mini], a[i]);}
}选择排序的时间复杂度也是O(N^2)。
♈️ 稳定性分析
选择排序不是一个稳定的排序会改变相同元素的相对位置升序排序序列3 2 3 1 4我们将1和位置0的3交换改变相同元素3的相对位置破坏了稳定性不稳定。插入可视化演示及工具
代码实现
// 插入排序
void InsertSort(int* a, int n)
{//0~end有序int end 0;int i 0;while (end n - 1){int tmp a[end 1];for (i end; i 0; i--){if (a[i] tmp){a[i 1] a[i];}else{break;}}a[i 1] tmp;end;}
}插入排序
♈️ 插入排序的原理及代码实现 插入排序又称为直接插入排序顾名思义核心思想肯定是围绕着插入展开它的原理是前n-1个元素已经有序的情况下我将第n个元素正确插入进去就能保证前n个元素是有序的就这样走n-1躺就可以将元素序列排成有序。 代码实现
// 插入排序
void InsertSort(int* a, int n)
{//0~end有序int end 0;int i 0;while (end n - 1){int tmp a[end 1];//插入位置的元素for (i end; i 0; i--)//调整其到正确位置将大于tmp的都往整体后挪动一位然后插入tmp{if (a[i] tmp){a[i 1] a[i];}else{break;}}a[i 1] tmp;end;}
}时间复杂度是O(N^2)。注意当数组是一个有序序列的时候插入一个数据的时间复杂度就是ON。
♈️ 稳定性分析 插入排序是稳定的排序算法因为我们只有大于待插入的值才会将其往后挪动覆盖小于等于就结束挪动了没有改变相同元素的相对位置。 希尔排序
♈️ 希尔排序的原理及其代码实现 希尔排序是插入排序的一种在性能上比直接插入排序更为优秀又称“缩小增量排序”Diminishing Increment Sort它的原理是预处理直接插入排序。希尔排序可视化演示及工具 下面我们来具体分析一下希尔排序的原理 我们一步步来下面我们实现gap为2时的多组排序。 //gap为2时的预处理int gap 2;for (int i 0; i gap; i)//一共有gap组{int end i;//将end赋值为这组的初始位置下标while (end n - gap)//这是一组的直接插入排序多组的在外面套一个循环就行{int tmp a[end gap];int j 0;for (j end; j 0; j - gap){if (a[j] tmp){a[j gap] a[j];}else{break;}}a[j gap] tmp;end gap;}}仔细比对gap等于1时这个就是我们的直接插入排序。很多教材上也会这样去写这两种代码的实际效果是等价的。这个就相当于上一组的直接插入排序还没排完就来排另外一个只不过调换了下顺序。 int gap 2;for (int end 0; end n-gap; end)//多组同时插入排序{int tmp a[end gap];int j 0;for (j end; j 0; j - gap){if (a[j] tmp){a[j gap] a[j];}else{break;}}a[j gap] tmp;}这个实现了我们来探讨一下gap到底应该取多少 最终的希尔排序代码
// 希尔排序
void ShellSort(int* a, int n)
{int gap n;//令gap等于nint i 0;//i为控制每次插入排序的开始的位置的变量int j 0;//j为每次直接插入排序的变量while (gap 1){gap gap / 3 1;//gap不为一个固定的值预处理多次让我们的分组插入的效果更加好降低后面直接插入的时间for (i 0; i n - gap; i)//gap为某一个值时的分组插入这里我们使用多组同时走插入排序{int end i;int tmp a[end gap];for (j end; j 0; j - gap){if (tmp a[j])//小于就把大的值往后移{a[j gap] a[j];}else//找到了break{break;}}a[j gap] tmp;//将tmp赋值给正确位置}}
}♈️ 希尔排序的时间复杂度分析 根据大量的实验算出希尔排序算法的时间复杂度是约为N^1.3约差于N*logN但是已经比直接插入排序好太多了看来预处理虽然看起来复杂还是很有必要的。 下面我们来画图分析一下它的时间复杂度的计算 ♈️ 稳定性分析 希尔排序是不稳定的排序直接插入排序是稳定的排序但是希尔排序的预处理是分组直接插入排序可能会改变相同元素的相对顺序是不稳定的排序。 堆排序 堆排序我们在数据结构堆中已经具体的介绍过这里不再重复叙述。堆排序可视化演示及工具 代码实现
// 堆排序
void AdjustDown(int* a, int n, int root)
{int child root * 2 1;while (child n){if (child 1 n a[child] a[child1])//找出最大的孩子{child child 1;}if (a[root] a[child])//如果根节点的值比最大的孩子小就交换{Swap(a[root], a[child]);root child;child root * 2 1;}else//否则调整完成{break;}}
}
//堆排序,向下调整
void Heapsort(int* a, int n)
{assert(a);for (int i (n-1-1)/2; i 0; i--)//我们向上调整原地建一个大堆{AdjustDown(a,n,i);}//将大堆最大的和最后一个元素交换并向下调整for (int end n - 1; end 0; --end){Swap(a[0], a[end]);//将堆顶元素放到堆最后面去AdjustDown(a,end,i);//此时的end就代表我们的元素个数}
}堆排序的时间复杂度O(NlogN)。建堆的消耗是O(N)排序的过程是NlogN。
♈️ 稳定性分析 堆排序不是一个稳定的算法我们使用下面的例子来解释一下。 归并排序 归并排序的原理在于两个字归和并也对应两个操作步骤递归和合并其中递归也包含着分治的思想 即把一个相同的问题划分为很多一样的子问题来解决下面我们来归并排序的归并排序可视化演示及工具 ♈️ 归并排序递归版本
画图分析 我们在写递归代码的时候应该申请一个和原数组一样大小的tmp数组用于辅助合并因为两个子数组比较之后需要把小的那个值放到一个地方如果放到原先的数组里面就可能会覆盖我们的值合并完之后在把left~right这段区间排好的值拷贝到原数组好进行下一大组的比较。
代码实现
void MergeSort1(int* a, int* tmp, int left,int right)
{if (left right)//如果左边界大于右边界就可以返回了没有划分的余地了但是要考虑一种特殊情况就是只有一个数据的情况return;int mid left (right - left) / 2;MergeSort1(a, tmp, left, mid);//分割左子数组MergeSort1(a, tmp, mid 1, right);//分割右子数组//左右两边的数组已经有序我们进行合并操作int idx left;int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[idx] a[begin1];}else{tmp[idx] a[begin2];}}//处理还没有遍历完的数组把他们加到数组的后面while (begin1 end1){tmp[idx] a[begin1];}while (begin2 end2){tmp[idx] a[begin2];}memcpy(a left, tmp left, sizeof(int) * (right - left 1));//将已经排好序的再拷贝到原数组
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);//开一个辅助数组用于辅助我们的合并操作if (tmp NULL)//如果申请空间失败直接返回{perror(malloc failed);exit(-1);}MergeSort1(a,tmp,0,n-1);//递归进行归并排序free(tmp);//释放空间tmp NULL;//置空
}♈️ 归并排序非递归版本 我们写了递归的版本就应该思考一下如何写出它的非递归版本。 代码实现
void MergeSort2(int* a, int* tmp, int n)
{int gap 1;//一路开始是11合并while (gap n){for (int i 0; i n; i gap * 2)//每次要合并的元素是gap*2假设有这么多元素{//定义两个合并区间的左右边界int begin1 i;int end1 i gap-1;int begin2 i gap;int end2 i 2 * gap - 1;if (end1 n || begin2 n)//如果已经没有两个区间合并那么就无法合并了跳出循环{break;}if (end2 n)//如果只是第二个区间的右边界超出范围那么就仍然可以合并将其右边界设置为数组的最后一个值的下标就行{end2 n - 1;}int idx i;//开始合并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[idx] a[begin1];}else{tmp[idx] a[begin2];}}while (begin1 end1)//哪个还有剩余就把哪个加到tmp中对于这段区间的后面{tmp[idx] a[begin1];}while (begin2 end2){tmp[idx] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//将已经排好序的这段区间重新拷贝到原数组区间准备下一次合并}gap * 2;//开始下一轮合并}
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int)*n);//创建辅助数组存某一段区间排好序的数据if (tmp NULL)//如果申请空间失败就退出程序{perror(malloc failed);exit(-1);}MergeSort2(a, tmp,n);//进入归并排序free(tmp);//释放空间tmp NULL;//置空
}♈️ 归并排序的时间复杂度和空间复杂度分析
归并排序不像希尔排序存在前面的预处理对后面的分组排序是有优化的问题时间复杂度非常好算我们画图来分析
♈️ 稳定性分析 先说结论归并排序是一个稳定的排序。 快速排序 快速排序和它的名字一样它确实很快。它是冒泡排序算法的改进通过多次比较和交换来实现。下面我们来具体介绍一下它的原理和代码实现。快速排序可视化演示及工具 ♈️ 快速排序递归实现(Hoare版本-----多坑版) 快速排序是Hoare这个人在1962年提出的一种二叉树结构的交换排序算法我们先来学习一下这个经典的版本。 它的思想是这样的 代码实现(递归)
int PartSort1(int* a, int left, int right)
{int keyi left;//记录关键元素的位置方便最后的交换while (left right)//如果left right就退出循环{while (left right a[right] a[keyi])//先找小严格找小也要加上left right的条件防止越界 {right--;}while (left right a[left] a[keyi])//再找大严格找大同样的越界条件要加上{left;}Swap(a[left], a[right]);//找到了交换}Swap(a[keyi], a[left]);//最后交换keyi元素和最后一个小的元素的位置这样单趟就排完了keyi位置的元素到了正确位置不用管它了return left;
}void QuickSort(int* a, int left, int right)
{if (left right)//一个元素或者区间不存在的情况递归就结束return;int mid PartSort1(a, left, right);//[leftmid-1] mid [mid1,right]QuickSort(a, left, mid - 1);//继续递归左边执行相同的单趟排序的思路QuickSort(a, mid 1, right);//继续递归右边执行相同的单趟排序的思路
}为什么说Hoare版本的快速排序存在着很多坑呢我们画图来分析一下 递归的这个过程我们也浅浅的画个图来分析一下吧。 我们来解释一下这里为什么一定要右边先找比key小的值 ♈️ 快速排序递归实现挖坑法 前面我们介绍了Hoare版本的快速排序但是坑比较多后面有人对其在思路上做了优化更好理解了。 我们画图来介绍一下 代码实现
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int key a[left];//保存left位置的值int hole left;//保存坑位的下标while (left right)//结束条件{while (left right a[right] key)//严格找小{right--;}a[hole] a[right];//把小的值放到坑位hole right;//更新坑位while (left right a[left] key)//严格找大{left;}a[hole] a[left];//把大的值放到坑位hole left;//更新坑位}a[hole] key;//把key值赋给相遇时的坑位return hole;//返回最后key值的下标
}
void QuickSort(int* a, int left, int right)
{if (left right)//一个元素或者区间不存在的情况递归就结束return;int mid PartSort2(a, left, right);//[leftmid-1] mid [mid1,right]QuickSort(a, left, mid - 1);//继续递归左边执行相同的单趟排序的思路QuickSort(a, mid 1, right);//继续递归右边执行相同的单趟排序的思路
}♈️ 快速排序递归实现前后指针法 前后指针法也是快速排序的一种实现思路我们也来介绍一下。 画图分析 代码实现
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int keyi left;//保存key值的下标int prev left;//prev指向小于等于key的指针int cur prev 1;//cur找小找到了交换没找到后移while (cur right)//这是程序继续的条件{if (a[cur] a[keyi] prev ! cur)//防止相同的值交换{Swap(a[cur], a[prev]);}cur;//不管哪种情况cur都要}Swap(a[prev], a[keyi]);//最后别忘了把key值和pre交换return prev;//返回key的正确下标
}♈️ 快速排序非递归实现 下面我们来看一下快速排序的非递归如何实现递归有栈溢出的风险所以一个优秀的程序员应该具备把递归转为非递归的能力。 老规矩画图分析 代码实现
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{Stack ps;//创建栈对象StackInit(ps);//初始化栈对象StackPush(ps, right);//入根节点的区间值先入右再入左这样我们拿的时候就可以先拿到左StackPush(ps, left);while (!StackEmpty(ps))//如果栈为空排序完成{int left1 StackTop(ps);//拿到栈顶区间的左边边界StackPop(ps);//pop掉左边边界int right1 StackTop(ps);//拿到栈顶区间的左边边界StackPop(ps);//pop掉右边边界int mid PartSort3(a, left1, right1);//走一趟快速排序哪个版本都可以这里我们用的前后指针if (right1 mid 1)//先入右边区间如果右边区间存在且长度不为1的话{StackPush(ps,right1);StackPush(ps, mid 1);}if (left1 mid - 1)//再入左边区间如果左边区间存在且长度不为1的话{StackPush(ps, mid-1);StackPush(ps, left1);}}StackDestroy(ps);//销毁栈
}♈️ 快速排序的三个优化 三数取中 正常情况下我们单趟排序排完最理想的情况是那个key值每一次都是中位数这样左右两边就均衡了递归的最深层数是logN但是如果数组是一个有序数组呢那每一次key值如果选第一个递归的层数不就是N层了每一次调整要O(N)那么就是O(N^2)的时间复杂度太慢了我们使用三数取中来优化一下。 三数取中就是在left、right、mid三个位置取一个中位数然后把它和left位置的值交换让它来作为key值这样就不害怕有序的情况了。
代码实现
int get_mid(int* a, int left, int right)
{int mid (left right) / 2;//中间下标的数if (a[left] a[mid])//如果left位置的值小于mid位置的值{if (a[mid] a[right])//如果right位置的值大于mid位置的值那么mid位置的值就是第2大的中位数{return mid;}else if (a[left] a[right])//left位置的值大于right位置的值mid是最大的{return left;}elsereturn right;}else//a[left] a[mid]{if (a[mid] a[right])//mid位置的值大于right位置的值return mid;else if (a[left] a[right])//left不是最大的return left;elsereturn right;}
}加在单趟里面是这样的
int PartSort1(int* a, int left, int right)
{int mid get_mid(a, left, right);//三数取中找中位数Swap(a[mid], a[left]);//交换int keyi left;//记录关键元素的位置方便最后的交换while (left right)//如果left right就退出循环{while (left right a[right] a[keyi])//先找小严格找小也要加上left right的条件防止越界 {right--;}while (left right a[left] a[keyi])//再找大严格找大同样的越界条件要加上{left;}Swap(a[left], a[right]);//找到了交换}Swap(a[keyi], a[left]);//最后交换keyi元素和最后一个小的元素的位置这样单趟就排完了keyi位置的元素到了正确位置不用管它了return left;
}小区间优化 这里我们使用插入排序因为插入排序每一次排序执行的次数不是完整的等差数列它比冒泡排序和选择排序都要优秀希尔排序在数据量小的情况下和插入排序差不多归并排序有空间消耗堆排序需要建堆综合考虑我们使用插入排序来进行小区间优化。
//快速排序小区间优化
void QuickSort(int* a, int left, int right)
{if (right - left 1 10)//区间长度大于10去走递归{int mid PartSort1(a, left, right);//[leftmid-1] mid [mid1,right]QuickSort(a, left, mid - 1);//继续递归左边执行相同的单趟排序的思路QuickSort(a, mid 1, right);//继续递归右边执行相同的单趟排序的思路}else//区间长度小于10去走插入排序{InsertSort(a left, right - left 1);}
}这里为什么是aleft呢因为每个大区间不断的去分割在很多位置都会产生长度小于10的区间 排序这个小区间的数组需要传它初始值的地址。 三路划分加随机取数 但是即使我们做了上面两种优化也仍旧不够下面的OJ题使用我们的优化版本就过不了。 912.排序数组 这里我们几乎上面的所有优化都用到了提交看看结果如何 这种重复值的情况确实让我们的快排很难受因为时间复杂度会到O(N^2)下面我们介绍第三种优化 三路划分。
画图分析 代码实现
//三路划分
void QuickSort1(int* a, int left, int right)
{if (left right)return;int mid get_mid(a, left, right);//三数取中找中位数Swap(a[mid], a[left]);//把那个中位数放到最左边int key a[left];int begin left;//保存左边界int end right;//保存右边界int cur left 1;//定义cur用于遍历while (cur right){if (a[cur] key)//如果小于key{Swap(a[cur], a[left]);cur;left;}else if (a[cur] key)//如果大于key{Swap(a[cur], a[right]);right--;}else{cur;}}QuickSort1(a, begin, left - 1);//递归左边区间QuickSort1(a, right 1, end);//递归右边区间
}提交结果 可以看到还是过不了所有用例的都通过了但是加起来时间仍然太长了这个时候我们可以猜到力扣对快速排序做了一些针对我们对三数取中部分继续优化
因为我们三数取中取mid、left、right三个位置数中的中位数如果测试用例故意针对每次让我们取到次小的数那么我们递归的深度还是会很大所以我们需要优化mid不在取中间位置的数而是取left~right区间的随机下标这样它就无法针对我们了。
三数取中优化
int get_mid(int* a, int left, int right)
{int mid leftrand()%(right-left1);//left~right随机下标的数if (a[left] a[mid])//如果left位置的值小于mid位置的值{if (a[mid] a[right])//如果right位置的值大于mid位置的值那么mid位置的值就是第2大的中位数{return mid;}else if (a[left] a[right])//left位置的值大于right位置的值mid是最大的{return left;}elsereturn right;}else//a[left] a[mid]{if (a[mid] a[right])//mid位置的值大于right位置的值return mid;else if (a[left] a[right])//left不是最大的return left;elsereturn right;}
}我们再加上随机数种子这题就可以过了 加上小区间优化会更快。
♈️ 快速排序时空复杂度分析
快速排序由于我们可以进行一系列的优化像三路划分、三数取中随机数、小区间优化等来避免最坏的情况让树的高度控制在ogN内又因为每趟排序的时间复杂度是O(N),所以每层的也是ON,最远是logN层所以时间复杂度是N*logN。至于空间复杂度递归是会消耗栈空间的同样的经过优化可以到logN级别。
♈️ 稳定性分析
快速排序不是不稳定的排序。因为它的性能很快牺牲了稳定性我们以Hoare版本来举个例子 计数排序 计数排序是一个特殊的排序它在有时候性能很优秀我们有必要去了解一下它。计数排序可视化工具及演示 ♈️ 原理及代码
我们还是画图来分析 代码实现
// 计数排序
void CountSort(int* a, int n)
{int max a[0];int min a[0];for (int i 0; i n; i)//找最大最小值{if (max a[i]){max a[i];}if (min a[i]){min a[i];}}int range max - min 1;//求出元素的范围int* count (int*)malloc(sizeof(int) * range);//动态申请空间if (count NULL)//如果申请失败{perror(malloc failed);exit(-1);}memset(count, 0, sizeof(int) * range);//初始化count数组for (int i 0; i n; i)//遍历数组计数{count[a[i] - min];}int index 0;for (int i 0; i range; i)//映射覆盖元素{while (count[i]--){a[index] i min;}}free(count);//释放堆上的空间count NULL;//指针置空
}♈️ 时空复杂度 我们看一个算法的时空复杂度不能简单的看它套了几层循环像刚刚的那个计数排序的时间复杂度就是O(Nrange).其中range代表数组中元素的范围。 这里range不能忽略因为不知道元素的范围和N比谁大当range N时这个算法还算可以但是当range N这个算法的性能就不行了。而且计数排序只能排整数。空间复杂度是O(range)。所以计数排序只适用于小数据范围的排序。是小数据范围而不是小数据规模。
♈️ 稳定性分析 计数排序是稳定的排序在排结构体时如果是排的是其中一个整形数据是可以做到让其它结构体成员稳定的具体大家可以看看这篇技术博客写的不错博主就不在这里分析了。 内排序与外排序 内排序是指在内存中排序外排序是指的是可以在磁盘中排序。 性能测试与排序正确性测试
♈️ 正确性测试
借助这个OJ题来测试一下我们七大排序算法的正确性 冒泡排序 这里我们的冒泡排序过了9组测试用例说明其排序的功能没啥问题就是太慢了。 选择排序 选择排序也是同样的效果。 插入排序 同为一个量级的排序算法我们的插入排序居然过了11组数据 希尔排序 我们的希尔排序直接狠狠拿下了果然O(N*logN)级别的排序算法就是不一样崇拜。 堆排序 堆排序也直接过了 快速排序 这里我们快速排序被针对了导致很慢还是我们优化了很多地方才过的。 归并排序 归并排序也过了 计数排序 可以看到我们计数排序的实力还是杠杠的当然这是因为力扣的测试用例没有针对计数排序如果将数据范围搞的很极端计数排序的性能就更不上了。
♈️ 性能测试
我们使用下面的代码来测试一下八大排序的性能测性能的时候我们要调到Release版本下优化更好。
void TestOP()
{int N 10000;printf(N: %d\n, N);int* a1 (int*)malloc(sizeof(int) * N);if (a1 NULL){printf(a1 malloc failed\n);exit(-1);}int* a2 (int*)malloc(sizeof(int) * N);if (a2 NULL){printf(a2 malloc failed\n);exit(-1);}int* a3 (int*)malloc(sizeof(int) * N);if (a3 NULL){printf(a3 malloc failed\n);exit(-1);}int* a4 (int*)malloc(sizeof(int) * N);if (a4 NULL){printf(a4 malloc failed\n);exit(-1);}int* a5 (int*)malloc(sizeof(int) * N);if (a5 NULL){printf(a5 malloc failed\n);exit(-1);}int* a6 (int*)malloc(sizeof(int) * N);if (a6 NULL){printf(a6 malloc failed\n);exit(-1);}int* a7 (int*)malloc(sizeof(int) * N);if (a7 NULL){printf(a7 malloc failed\n);exit(-1);}int* a8 (int*)malloc(sizeof(int) * N);if (a8 NULL){printf(a8 malloc failed\n);exit(-1);}for (int i 0; i N; i){a1[i] rand() % N;a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];a8[i] a1[i];}int begin1 clock();BubbleSort(a1, N);int end1 clock();int begin2 clock();SelectSort(a2, N);int end2 clock();int begin3 clock();InsertSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4,N);int end4 clock();int begin5 clock();QuickSort1(a5,0,N-1);//三路划分版本int end5 clock();int begin6 clock();ShellSort(a6, N);int end6 clock();int begin7 clock();MergeSort(a7, N);int end7 clock();int begin8 clock();CountSort(a8, N);int end8 clock();printf(BubbleSort%dms\n, end1 - begin1);printf(SelectSort%dms\n, end2 - begin2);printf(InsertSort%dms\n, end3 - begin3);printf(HeapSort%dms\n, end4 - begin4);printf(QuickSort1%dms\n, end5 - begin5);printf(ShellSort%dms\n, end6 - begin6);printf(MergeSort%dms\n, end7 - begin7);printf(CountSort%dms\n, end8 - begin8);
}
int main()
{srand(time(NULL));TestOP();return 0;
}
函数clock()是返回程序运行到当前指令的时间 这是1w整形数据的运行结果 这是10w整形数据的运行结果 可以看到10W个O(N^2)的排序就有点hold不住了,特别是我们的冒泡排序居然跑了14秒
这是100w整形数据的运行结果
O(N^2)的算法跑太慢了我们就不让它们上场了。 这是1000w整形数据的运行结果 这是1亿整形数据的运行结果 可以看到1亿整型数据除了我们的快速排序和计数排序稳在10秒内其它N*logN级别的排序算法都超过了10秒HeapSort更是达到了惊人的41秒多其它O(N^2)的算法都上不了桌这里可能出现内存不够用的情况把编译器调到64位就行。
