怎么用一个主机做多个网站,创意设计公司经营范围,自建wordpress主题,一键生成logo免费在线网页0.前言 接下来进入排序#xff0c;我们知道在c语言阶段可能就学习过了像冒泡排序#xff0c;选择排序这种比较简单的排序#xff0c;那么接下来我们就会学习到更加高级的排序算法。但高级代表着难度的提升#xff0c;但不用担心#xff0c;博主会细细来谈#xff0c;慢慢…0.前言 接下来进入排序我们知道在c语言阶段可能就学习过了像冒泡排序选择排序这种比较简单的排序那么接下来我们就会学习到更加高级的排序算法。但高级代表着难度的提升但不用担心博主会细细来谈慢慢品尝其中的酸甜苦辣。 1.排序的概念及其运用
1.1 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。内部排序数据元素全部放在内存中的排序。外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 排序的运用
其实在我们生活中处处都需要排序请看下面。 它们都需要排序算法的支持才能呈现出我们想知道的排名情况。
这就可知排序算法的重要性。
1.3 常见的排序算法 1.4 测试排序性能代码
这串代码可以测试我们的各个排序算法的性能大小。
计算结果是每个排序算法的启动到结束之间的毫秒差。
void TestOP()
{srand(time(0));const int N 10000;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);
} 一道oj排序练习测试题下面讲解的排序算法都可在上面训练OJ链接
2.插入排序
2.1 基本思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 实际中我们玩扑克牌时就用了插入排序的思想。
2.2 直接插入排序
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 代码
void InsertSort(int* a, int n)
{//[0, end] end 1for (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;}}
直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2),最好情况下ON--- 即当序列已经有序只需要遍历一遍即可。空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
2.3 希尔排序缩小增量排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是
先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 代码 void ShellSort(int* a, int n)
{//预排序 --- 使序列逐渐接近有序//直接插入排序 --- gap 1时即为直接插入排序int gap n;while (gap 1){//gap gap / 2;gap gap / 3 1;版本二for (int i 0; i n - gap; i){int end i;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;}}版本一/*for (int j 0; j gap; j){for (int i j; i n - gap; igap){int end i;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;}}*/} 希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定我们通常把希尔排序的时间复杂度定为On^1.3。稳定性不稳定。
3.选择排序
3.1 基本思想
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置末尾位置直到全部待排序的数据元素排完 。
3.2 直接选择排序
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]--array[n-2]array[i1]--array[n-1]集合中重复上述步骤直到集合剩余1个元素 代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
} 直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)最好情况也是ON^2空间复杂度O(1)稳定性不稳定
3.3 堆排序
堆排序(HeapSort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){//假设左孩子大如果假设错误更新一下if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建大堆 -- 升序//O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//交换//O(N*logN)int end n - 1;while (end 0){Swap(a[end], a[0]);AdjustDown(a, end, 0);end--;}} 直接选择排序的特性总结
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
4.交换排序
4.1 基本思想
基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
4.2 冒泡排序
两两比较大的冒到后面小的留在前面。 代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//时间复杂度:O(N^2)
//最好情况:O(N^2)
//加个exchange可以使最好情况变为O(N)
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){bool exchange false;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange true;}}if (exchange false){break;}}}
冒泡排序的特性总结
冒泡排序是一种非常容易理解的排序时间复杂度O(N^2) 最好情况下也是O(N^2)空间复杂度O(1)稳定性稳定
4.3 快速排序
4.3.1hoare版本 代码
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;//两两比较if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}
void QuickSort(int* a, int begin, int end)
{if (begin end)return;//三数取中int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){//右边找小while (left right a[right] a[keyi]){right--;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;//[begin, keyi - 1] keyi [keyi 1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 我们讲一下上面的代码当然这已经是优化好了的完全版。
我们知道当left和right相遇时就将key位置与相遇位置互换而key位置在相遇位置的左边呀
我们为什么确定相遇位置的数一定比key位置的小呢?
先宣布一下答案答案是因为右边先走的原因
有两种情况
1.R遇L没有找到比key小的数一直走当与left相遇停止此时是一定比key小的因为左边已经全部遍历没有发现比key小的
2.L遇RR先走找到小的停了下来L找大没有找到遇到R停下那么相遇位置比key小。
综上相遇位置数一定比key位置数小 看来hoare版本的快排坑比较多那么我们后来就对它进行了优化。
这种优化是思想上的优化更易于我们理解。
4.3.2 挖坑法 挖坑的基本思想就是挖出一个坑位右边找小的放到坑位右边就空出空位然后左边找大放到右边的空位左边又空出空位最后相遇时把第一次挖出来的数放到相遇时的空位就结束。
int PartSort(int* a, int begin, int end)
{//三数取中int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int key a[begin];int hole begin;while (begin end){//右边找小while (begin end a[end] key){end--;}a[hole] a[end];hole end;//左边找大while (begin end a[begin] key){begin;}a[hole] a[begin];hole begin;}a[hole] key;return hole;
}
void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort(a, begin, end);//[begin, keyi - 1] keyi [keyi 1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 4.3.3 前后指针版本 前后指针cur往后找小prev紧跟着cur找到小cur和prev都往后走cur找到大cur位置与prev位置交换重复操作往后直到cur越界把key位置与prev位置交换一趟结束。 int PartSort(int* a, int begin, int end)
{//三数取中int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int prev begin;int cur prev 1;while (cur end){if (a[cur] a[prev] prev ! cur){Swap(a[cur], a[prev]);}cur;}Swap(a[prev], a[keyi]);keyi prev;return keyi;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int keyi PartSort(a, begin, end);//[begin, keyi - 1] keyi [keyi 1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 4.3.4 快速排序优化
三数取中
为什么我们要三数取中
这是因为三数取中可以减少大量比较原版的hoare版本如果我们不进行三数取中在序列接近有序或已经是有序时当我们选择key时就会选择一个比较小的数那么每次找数都要将序列遍历一遍因为key是在第一个位置那么right必须要走到key位置才会停下来这样的时间复杂度就是ON^2, 如果我们采取三数取中就会减少接近一半的找数的次数近似二分的思想这样的时间复杂度就是O(N*logN)。 小区间优化
由于在大量数据进行快排时是要进行很深的递归的这就大大增加了消耗我们知道vs2022有Debug版本和Relase版本Relase版本下可能这个优化作用并不是很大但Debug版本下就有一些提升使得递归的深度减少我们前面已经学习了二叉树我们知道快排就是一种二叉树的递归形式那么二叉树的最下层是数据占据总节点数的一半的如果这些数据再全部继续递归得不偿失那我们可以让这些数据不再递归而是进行插入排序即可这就是小区间优化。
代码
void QuickSort1(int* a, int begin, int end)
{if (begin end)return;if (end - begin 1 10){InsertSort(a begin, end - begin 1);}else{//三数取中int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int left begin, right end;int keyi begin;while (left right){//右边找小while (left right a[right] a[keyi]){right--;}//左边找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[left], a[keyi]);keyi left;//[begin, keyi - 1] keyi [keyi 1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}
} 4.3.5 快速排序非递归版本 快排的非递归版本就需要用到我们前面学到的栈了用栈的压栈出栈来代替我们递归时的函数调用我们知道函数调用就是创建栈帧和销毁栈帧的过程而我们造出来的数据结构的栈是在堆区开辟看空间故不会有栈溢出的情况这就是非递归的优势。
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(s);STPush(s, end);STPush(s, begin);while (!STEmpty(s)){int left STTop(s);STPop(s);int right STTop(s);STPop(s);int keyi PartSort(a, left, right);//[left keyi - 1] keyi [keyi 1, right]if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}STDestroy(s);
} 快速排序的特性总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定
5.归并排序 5.1 基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 代码:
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid][mid1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid1, end, tmp);// [begin, mid][mid1, end]归并int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while(begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
} 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
6.排序算法时间复杂度及稳定性分析 7.选择题小练 1. 快速排序算法是基于 的一个排序算法。 A分治法 B贪心法 C递归法 D动态规划法 2.对记录54,38,96,23,15,72,60,45,83进行从小到大的直接插入排序时当把第8个记录45插入到有序表时为找到插入位置需比较 次采用从后往前比较 A 3 B 4 C 5 D 6 3.以下排序方式中占用On辅助存储空间的是 A 简单排序 B 快速排序 C 堆排序 D 归并排序 4.下列排序算法中稳定且时间复杂度为O(n2)的是 A 快速排序 B 冒泡排序 C 直接选择排序 D 归并排序 5.关于排序下面说法不正确的是 A 快排时间复杂度为O(N*logN)空间复杂度为O(logN) B 归并排序是一种稳定的排序,堆排序和快排均不稳定 C 序列基本有序时快排退化成冒泡排序直接插入排序最快 D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN) 6.下列排序法中最坏情况下时间复杂度最小的是 A 堆排序 B 快速排序 C 希尔排序 D 冒泡排序 7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)则以第一个关键字65为基准而得到的一趟快速排序结果是 A 3456256586997266 B 2534566599867266 C 3456256566998672 D 3456256599867266 答案 1.A 2.C 3.D 4.B 5.D 6.A 7.A 8.总结 到这里排序这节就结束了排序算法在我们生活中作用还是很大的但理解它还是有一定难度的但我们只要坚持把每一步了解清楚一步一步攻克难关最后都能很好的理解希望多多支持
