微网站建设及微信推广方案ppt模板,成都市建筑设计研究院,大型门户网站建设流程,北京网站开发服务文章目录一、排序的概念及其运用1.排序的概念2.常见排序的分类3.排序的运用二、常见排序算法的实现1.直接插入排序1.1排序思想1.2代码实现1.3复杂度及稳定性1.4特性总结2.希尔排序2.1排序思想2.3复杂度及稳定性2.4特性总结3.直接选择排序3.1排序思想3.2代码实现3.3复杂度及稳定…
文章目录一、排序的概念及其运用1.排序的概念2.常见排序的分类3.排序的运用二、常见排序算法的实现1.直接插入排序1.1排序思想1.2代码实现1.3复杂度及稳定性1.4特性总结2.希尔排序2.1排序思想2.3复杂度及稳定性2.4特性总结3.直接选择排序3.1排序思想3.2代码实现3.3复杂度及稳定性3.4特性总结4.堆排序4.1排序思想4.2代码实现4.3复杂度及稳定性4.4特性总结5.冒泡排序5.1排序思想5.2代码实现5.3复杂度及稳定性5.4特性总结6.快速排序(重要)6.1排序思想6.2快速排序递归实现6.2.1 hoare法6.2.2 挖坑法6.2.3 前后指针法6.3快速排序递归实现的完整代码6.4快速排序非递归实现6.5复杂度及稳定性6.6特性总结7.归并排序7.1排序思想7.2归并排序递归实现7.3归并排序非递归实现7.4复杂度及稳定性7.5特性总结8.计数排序8.1排序思想8.2代码实现8.3计数排序的缺陷8.4特性总结三、排序总结一、排序的概念及其运用
1.排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
为什么要关注排序的稳定性 排序算法如果是稳定的那么从一个键上排序然后再从另一个键上排序第一个键排序的结果可以为第二个键排序所用。基数排序就是这样先按低位排序逐次按高位排序低位相同的元素其顺序再高位也相同时是不会改变的。 比如一个班的学生已经按照学号大小排好序了我现在要求按照年龄从小到大再排个序如果年龄相同的必须按照学号从小到大的顺序排列那么问题来了你选择的年龄排序方法如果是不稳定的是不是排序完了后年龄相同的一组学生学号就乱了你就得把这组年龄相同的学生再按照学号排一遍。如果是稳定的排序算法我就只需要按照年龄排一遍就好了这样看来稳定的排序算法是不是节省了时间 所以在特殊场景下对排序的稳定性是有要求的另外排序的稳定性在校招中也经常被考察 内部排序数据元素全部放在内存中的排序比如插入排序选择排序和交换排序
外部排序数据元素太多不能同时放在内存中不能同时放入内存中而是需要将待排序的数据存储在外存中待排序时再把数据一部分一部分地调入内存进行排序在排序的过程中需要多次进行内存和外存之间进行交换这种排序就称为外部排序我们的归并排序既可以是内部排序也可以是外部排序。
**比较排序**通过比较两个元素的大小来确定元素在内存中的次序我们常见的选择排序插入排序比较排序和归并排序都属于比较排序
**非比较排序**通过确定每个元素之前统计相同元素出现次数根据统计的结果将序列回收到原来的序列中常见的非比较排序有基数排序计数排序和桶排序
2.常见排序的分类 3.排序的运用
排序在我们的日常生活中的应用十分广泛比如我们在网上购物时会对商品的价格购买数量评分等等一系列进行排序又比如我们的成绩也会进行排序我们的大学也会进行排序等等。 二、常见排序算法的实现
【注意】本篇文章所有的排序都是以升序实现。
1.直接插入排序
1.1排序思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
实际中我们玩扑克牌时就用了插入排序的思想 动图演示
当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与
array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 1.2代码实现
// 直接插入排序
// 最坏时间复杂度O(N^2) -- 逆序
// 最好时间复杂度O(N) -- 顺序有序
void InsertSort(int* a, int n)
{//[0,end]插入end1 [0,end1]有序for (int i 0; i n - 1; i){int end i;int tmp a[end 1];//记录最后一个元素//当目标元素为最小元素end为-1时退出循环while (end 0){//如果大于tmp中的数据就往后挪并--endif (tmp a[end]){a[end 1] a[end];end--;}//如果小于tmp中的数据就跳出循环准备插入else{break;}}//将数据插入到end的后一个位置a[end 1] tmp;}
}【注意】 1.对于单趟排序来说假设该数组[0,end]有序我们需要插入end1位置的数据。使得[0,end1]有序。 2.我们end的位置一次从0,1,2,3…n-2开始即end1从1,2,3…n-1(下标为n-1为数组的最后一个元素)使得[0,1],[0,2]…[0,n-1]有序我们用变量tmp保存end1位置的数据使得在挪动的过程中不会因为覆盖而丢失数据。 3.当tmp保存的元素大小小于数组中任意一个元素的时候为了避免数组越界while循环的条件应该是end0;d当tmp比第一个元素还小时end此时为-1此时tmp里的数据会被放入a[0]位置逻辑是正确的。 1.3复杂度及稳定性
时间复杂度
最坏情况当数组的元素为逆序时第一次插入移动0第二次插入移动1次…第n次插入移动n-1次,由等差数列求和公式可知此时的时间复杂度为O(N^2);
最好情况当数组的元素为顺序时每次插入都不需要移动数据遍历一遍数组即可此时的时间复杂度为O(N);
所以直接插入排序的时间复杂度为O(N^2)
空间复杂度
直接插入排序是在原数组上进行的没有开辟额外的空间所以直接插入排序的空间复杂度为O(1)
稳定性
在数组内部前半部为排好序的记录后半部是未排好序的。 比较时从前半部的后向前比较所以不会改变相等记录的相对位置。所以直接插入排序是稳定的。
1.4特性总结 1.元素集合越接近有序直接插入排序算法的时间效率越高 2.时间复杂度O(N^2) 3.空间复杂度O(1)它是一种稳定的排序算法 4.稳定性稳定 2.希尔排序
2.1排序思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。
画图演示 1.一组一组的进行直接插入排序
//希尔排序
// gap 1 预排序
// gap 1 直接插入排序//一组一组的进行直接插入排序
void ShellSort1(int* a, int n)
{int gap n;while (gap 1){//gap gap / 2;gap gap / 3 1;for (int i 0; i gap; i){// [0,end] 插入 endgap [0, endgap]有序 -- 间隔为gap的数据for (int j i; j n - gap; j gap){int end j;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}
}2.gap组数据多组依次并排
//gap组数据多组依次并排
void ShellSort2(int* a, int n)
{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 (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}【注意】 1.关于gap的取值我们知道gap越大大的数据就能越快跳到后面小的数据就能越快跳到前面但不是很接近有序gap越小大的数据到后面和小的数据到前面的速度就越慢但更接近有序所以综合这两种情况为了提高效率最初Shell提出取gapn/2,直到gap1;后来大佬Knuth提出gapn/31;还有人提出都取奇数好也有人提出各gap互质为好我们这里取的是每次缩小3倍 2.对于一组一组的进行直接插入排序我们每次只排一组数据当这组数据排完之后再排下一组时候所以我们需要用两层循环嵌套来保证没每一组数据都被排序对于gap组数据多组依次并排我们每次让i加1即让所有组数据同时进行排序(第一组插入一个元素后让第二组插入第一个元素然后第三组插入第一个元素…直到所有组都插入第一个元素之后再插入每一组的第二个元素,…如此循环往复)就像流水线一个每一个都先做一点下一组继续做所以我们只需要使用一个for循环便可以使得所有组数据都可以进行排序。 3.当gap1时相当于对数组进行直接插入排序 4.无论gapn为奇数还是偶数gap经过不断的除3加1或者不断除2进行最后一趟排序时gap一定等于1我们可以带数字进行验证。 2.3复杂度及稳定性
时间复杂度
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在一些优秀的数据结构书籍中给出的希尔排序的时间复杂度也都不固定:
《数据结构(C语言版–严蔚敏 《数据结构-用面相对象方法与C描述》–殷人昆 因为我们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(N1.25)到O(1.6*N1.25)来算大概为O(N^1.3)
空间复杂度
希尔排序没有额外的内存消耗空间复杂度为O(1)
稳定性
和插入排序不同希尔排序是不稳定的因为在预排序过程中数值大小的数据可能会被分配到不同的组中不同的组进行插入排序之后数值大小相同的数据的相对位置就可能会发生改变所以希尔排序是不稳定的。
2.4特性总结 希尔排序是对直接插入排序的优化 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会使得最后一次排序很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比 时间复杂度O(N^1.3)(不确定) 空间复杂度O(1) 稳定性不稳定 3.直接选择排序
3.1排序思想
直接选择排序的基本思想是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。这里我们对其进行一些优化我们每次从数组中选择最大的和最小的把最小的放在最前面最大的放在最后面。
动图演示(优化之前)
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素。 3.2代码实现
// 最坏时间复杂度O(N^2)
// 最好时间复杂度O(N^2)//选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){// 选出最小的放begin位置// 选出最大的放end位置int maxi begin, mini begin;for (int i begin 1; i n; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);//修正一下maxiif (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}【注意】 我们优化之后程序会出现一个bug当我们数组的最大元素在数组的最前面(beginmaxi)的时候我们交换a[begin]和a[mini]之后会使得最大数a[begin]被交换到下标为mini的位置此时我们需要修正最大数的下标。 3.3复杂度及稳定性
时间复杂度
无论我们的数组是顺序逆序还是无序都不会改变排序的效率因为我们始终是通过遍历数组来找最大和最小值即使最小值在第一个位置最大值在最后一个位置都需要遍历一遍。所以直接选择排序的时间复杂度为O(N^2);
空间复杂度
直接选择排序没有开辟额外的数组所以空间复杂度为O(1);
稳定性
直接选择排序给我们的直观感受是稳定的因为他每次选择元素的时候只有当遇到比自己小的元素时才更新mini与自己相等的元素并不会更新mini所以相等元素间的相对位置不会发生改变但其实它是不稳定的
我们以 8 9 8 5 5 为例我们第一次排序发现5为最小元素所以mini3然后交换a[0]和a[mini]第一次排序之后的数组为 5 9 8 8 5 我们仔细对比第一次排序前和排序后的数组我们发现8和8之间的相对位置发生了改变所以说直接选择排序其实是不稳定的我们这里为了方便好理解我们以未优化的直接选择排序为例。
3.4特性总结 1.直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2.时间复杂度O(N^2) 3.空间复杂度O(1) 4.稳定性不稳定 4.堆排序
4.1排序思想
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
4.2代码实现
#include stdio.h
#include assert.h//空间复杂度O(1)
//时间复杂度O(N*logN)typedef int HPDataType;
//交换两个节点
void Swap(HPDataType* p1, HPDataType* p2)
{assert(p1 p2);HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//堆的向上调整 --小根堆
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2; //找到父节点//while (parent 0) 当父亲为0时(0 - 1) / 2 0;又会进入循环while (child 0) //当调整到跟节点的时候不再继续调整{//当子节点小于父节点的时候交换//if (a[child] a[parent]) 大根堆if (a[child] a[parent]){Swap(a[child], a[parent]);//迭代child parent;parent (child - 1) / 2;}//否则跳出循环else{break;}}
}//堆的向下调整 --小根堆
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int minchild parent * 2 1;while (minchild n){//找出那个较小的孩子if (a[minchild] a[minchild 1] minchild 1 n){minchild;}//if (a[minchild] a[parent]) 大根堆//当子节点小于父节点的时候交换if (a[minchild] a[parent]){Swap(a[minchild], a[parent]);//迭代parent minchild;minchild parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{/* 建堆 -- 向上调整建堆 - O(N*logN)for (int i 1; i n; i){AdjustUp(a, i);}*/// 大思路选择排序依次选数从后往前排// 升序 -- 大堆// 降序 -- 小堆//建堆 -- 向下调整建堆 - O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int i 1;while (i n){Swap(a[0], a[n - i]); // 交换堆尾和堆顶的数据AdjustDown(a, n - i, 0); //向下调整i;}
}int main()
{int a[] { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}printf(\n);return 0;
}4.3复杂度及稳定性
时间复杂度
堆排序的建堆的时间复杂度为O(N),选数的时间复杂度为O(N*logN),所以堆排序的时间复杂度为O(N*logN)
空间复杂度
堆排序直接在原数组进行建堆和选数操作没有额外的内存消耗所以空间复杂度为O(1)
稳定性
由于堆排序中相同的数据父节点还是孩子节点做左孩子还是右孩子这些都没有规定所以堆排序吧不稳定的
4.4特性总结 1.堆排序使用堆来选数效率就高了很多。 2.时间复杂度O(N*logN) 3.空间复杂度O(1) 4.稳定性不稳定 5.冒泡排序
5.1排序思想
交换的基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
冒泡排序的基本思想冒泡排序的思想就是利用的比较交换利用循环将第 i 小或者大的元素归位归位操作利用的是对 n 个元素中相邻的两个进行比较如果顺序正确就不交换如果顺序错误就进行位置的交换。 通过重复的循环访问数组直到没有可以交换的元素那么整个排序就已经完成了。
由于冒泡排序本身并不知道排序的数据是否有序了所以即便目标数据已经有序它还是会继续比较直到循环结束所以为了提高效率我们可以对冒泡排序进行简单的优化即增加一个有序的判断标志使得我们知道排序的数据已经有序的时候能够提前跳出循环结束排序。
动图演示
5.2代码实现
// 最坏情况O(N^2)
// 最好情况O(N)
// 冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int exchange 0;for (int j 1; j n - i; j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);exchange 1;}}// 如果没有进行交换则说明已经有序则直接跳出循环if (exchange 0){break;}}
}【注意】
由于冒泡排序本身不知道待排序的数据是否是有序的所以即便是在后面排序的过程中数组中的元素都是有序的它依然会进行进行所以我们可以进行一个优化定义一个标志的变量exchange如果一趟排序完成之后标志仍然没有改变则说明数组已经有序则可以直接退出循环停止后面不必要的排序。
5.3复杂度及稳定性
时间复杂度
最坏的情况数组如果是逆序的则第一趟排序需要交换n-1次第二趟排序需要交换n-2次…第n-1趟排序需要交换一次根据等差数列求和可知此时的时间复杂度为O(N^2)
最好的情况数组如果是有序或者接近有序在没有优化之前数组元素的数据不会影响排序的时间效率但是在我们进行优化了之后此时我们遍历很少的次数便会跳出循环停止排序时间复杂度最好的情况达到O(N)
所以冒泡排序的时间复杂度为O(N^2)
空间复杂度
冒泡排序没有开辟额外的数组所以空间复杂度为O(1);
稳定性
冒泡排序每一趟排序时只有当前一个元素大于后一个元素的时候才会发生交换我们是可以控制的在元素相等时不发生交换所以冒泡排序是稳定的。
5.4特性总结 1.冒泡排序是一种非常容易理解的排序 2.时间复杂度O(N^2) 3.空间复杂度O(1) 4.稳定性稳定 6.快速排序(重要)
6.1排序思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
6.2快速排序递归实现
快速排序的过程是这样的每次单趟排序先选出一个数作为一个基准值把比这个小的数放在这个基准值的左边比这个大的数放在这个基准数的右边这样经过一次单趟排序之后这个基准值到了它最终的位置并且以这个基准数为界分为了两个左右区间左边的比它小右边的比它大这样我们就可以对左右区间进行同样的操作每一次单趟排序都会使得一个数到达它最终的位置当它的左右区间只有一个元素(一个元素本身就可以看做有序)或者是一个不存在的区间时说明排序已经完成。
我们发现快速排序的过程和二叉树的前序(先序)遍历十分相似我们每一趟排序确定一个元素的最终位置我们只需要按照同样的方式排它的左右区间即可这个就是不断的把问题分为它的子问题去解决这便是递归的思想。所以说快速排序是一种二叉树结构的交换排序方法。
//快速排序递归实现
void QuickSort(int* a, int left, int right)
{//如果区间只有一个元素或者区间不存在则返回if (right left){return;}//单趟排序确定基准值的位置int keyi PartSort(a, left, right);//递归左区间QuickSort(a, left, keyi - 1);//递归右区间QuickSort(a, keyi 1, right);
}关于快速排序的单趟排序现在主流的有三种方法hoare法挖坑法已经前后指针法
【注】快速排序所有代码中的keyi代表的是数组的下标key则是代表数组中的元素
6.2.1 hoare法
hoare法的算法思想我们取最左边的元素做key然后定义两个指针L和RL指向区间的第一个元素R指向区间的最后一个元素然后让R先走当R遇到小于或等于key的元素时就停下来然后让L走L遇到大于或等于key的数据时停下来然后交换L和R所对应的值进行交换然后重复上面的步骤直到L和R相遇二者相遇位置所对应的值一定是小于key的这时候交换key和L/R即可 代码实现
【注意】 1.我们需要保存的是数组元素的下标keyi,而不是数组中元素的大小key,因为在partsort中key只是一个局部变量局部变量的改变不会影响数组中的元素 2.在写循环条件的时候我们需要假上left right这是为了避免keyi右边的元素全部大于a[keyi]的时候R不会停止而造成数组的越界访问同时也避免L在往右走的过程中不会越过R和不会在相遇点停下来 3.我们判断L和R移动的条件的时候a[left]或者a[right]等于a[keyi]的时候我们也让L和R移动避免出现a[keyi]a[left]a[right]这种情况而造成死循环的情况 为什么L和R相遇位置对应的元素一定小于key 这里的关键在于我们让R先走 我们知道L和R相遇只有两种情况L撞R或者是R撞L 当L撞R的时候由于R是先走的所以R停下来的位置下标对应的元素一定是小于key的所以相遇位置对于的元素是小于key的 当R撞L的时候这里分为两种情况1是L一直没有动此时LR可以交换后不变2是L动过此时L处对于的下标值一定是小于keyi位置的值的因为在此之前两者一定发生过交换否则R不会动所以相遇时对于的下标的值是小于keyi对于的值的 排序优化
我们已经实现了快速排序我们是选择最左边或者最右边的值做key但是如果在某些特殊的情况下比如数组是顺序或者逆序的情况下快速排序的时间复杂度此时为O(N^2),且有可能会出现栈溢出的情况这里我们可以对其中的两个逻辑进行优化一是选key逻辑二是小区间优化
优化选key逻辑
我们知道我们当前的算法是选择区间第一个位置的元素作为key然后通过单趟排序确定该元素的最终最值那么最好的情况就是我们每次取出的keyi对于的值都为该区间的中位数这个我们就能不断进行二分效率就很高 那么最坏的情况是数组有序或者接近有序的时候在这种情况下我们可以认为keyi处于最左边这样每次递归左区间的长度为0右区间的长度为n-1那么递归的深度为n,即一个会建立n层栈帧但是我们知道栈区的空间是非常小的在Linux下只有8M那么当我们需要排序的数量达到一定的程度之后就可能发生栈溢出导致程序崩溃 针对数组有序或者接近有序造成程序栈溢出的情况有人对选key的逻辑提出了一下三种优化方法 1.随机选数这样使得每次key都为最小或最大的概率变得很小因为排序的数本来就是随机的再随机选数就使得选得最小或最大的可能变得更小 2.选中间数做key这个是专门对有序数组进行的一个优化 3.三数取中-取区间里left,mid,right三个下标对应值的中间值 这里我们选择采用第三种优化方法
//三数取中
int GetMidIndex(int* a, int left, int right)
{int mid left (right - left) / 2;//int mid (left right) / 2;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;}}
}优化后的单趟排序代码
// hoare
int PartSort1(int* a, int left, int right)
{//三数取中int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int keyi left;while (left right){// 6 6 6 6 6// R找小// left right,避免left和right错过或者越界// 避免死循环while (left right a[right] a[keyi]){right--;}//L找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}// 记录二者相遇的位置使其与key交换int meeti left;Swap(a[meeti], a[keyi]);return meeti;
}递归小区间优化
我们知道在完全二叉树中最后一层的节点数占总节点数的1/2倒数第二层的节点数占总节点数的1/4倒数第三场占1/8也就是说完全二叉树最后三层的节点数占了总节点数的87.5%
对于快速排序来说虽然我们递归下来的树并不是一个完全二叉树因为我们每一层取的key不一定都是中位数但是总整体上来看递归下来的二叉树可以认为是一棵完全二叉树而且对于快速排序来说最后几层的元素很少(倒数第三层的元素大概为8个倒数第二层为4个倒数第一层为2个左右)并且他们都是较为有序的所以当区间长度小于等于8的时候我们可以使用直接插入排序为什么不选择其他的排序方式呢对个冒泡排序来说循环结束的条件太苛刻了对于希尔排序对于大量数据来说效率高对于数量少的数据在预排阶段就会有很大的消耗而直接插入排序对于接近有序的数据那么数据移动的次数就会很少非常适合这种接近有序的数组的排序这样我们就不再继续递归分割子区间从而达到提高效率的目的我们也可以在长度小于15的时候就使用直接插入排序这个可以自己选择 优化后的递归函数
//快速排序递归实现-递归优化
// [begin, end]
void QuickSort(int* a, int begin, int end)
{// 如果左右区间相等或者右区间的值小于左区间的值时返回if (begin end){return;}// 当递归到元素个数小于8的时候为了提高效率直接使用直接插入排序if (end - begin 8){InsertSort(a begin, end - begin 1);}else{int keyi PartSort3(a, begin, end);//[begin, keyi-1] keyi [keyi1, end]// 递归左区间QuickSort(a, begin, keyi - 1);// 递归右区间QuickSort(a, keyi1, end);}
}6.2.2 挖坑法
挖坑法的算法思想如下
首先我们利用三数取中筛选出合适的数值然后让其与最左边的数据进行交换再让keya[left]其次定义两个变量L和R分别指向区间的开始和末尾与hoare法不同的是挖坑法会增加一个变量hole,用来记录坑的位置同时hoare中使用的是keyi(数组下标)而挖坑法中使用的是key(下标对应的元素)
如下图坑最开始的位置在最左边我们让R先走当R找到比key小的值之后与a[hole]进行交换并让R的位置作为新的坑然后让L走找到比key大的位置找到后也与坑所在位置的元素进行交换并更新坑最后重复上述过程直到L和R相遇此时直接用key覆盖掉L/R/hole(代表同一个位置)对于的元素即可
动图演示 代码实现
// 挖坑法
int PartSort2(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int key a[left];int hole left;while (left right){// 右边找小填到左边坑while (a[right] key left right){--right;}a[hole] a[right];hole right;// 左边找大填到右边坑while (a[left] key left right){left;}a[hole] a[left];hole left;}a[left] key;return hole;
}6.2.3 前后指针法
前后指针的算法思想如下
首先最开始的还是和前面两种方法一样利用三叔取中函数来优化选key逻辑三种方法不同之处在于一次快速排序的逻辑对于前后指针法的单趟排序我们定义第三个变量keyileft,prevleft,curleft1;其中keyi代表key值所在的下标而prev和cur就是我们的前后指针我们让cur先走当找到小于a[keyi]的时候停下来然后prev再判断cur和prev是否相等不相等就交换对于的值重复以上步骤直到curright,最后交换a[keyi]和a[prev]即可 代码实现
//前后指针法
int PartSort3(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int keyi left;int prev left;int cur left 1;while (cur right){// 找小if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}/*while (cur right){while (a[cur] a[keyi] cur right){prev;Swap(a[prev], a[cur]);cur;}while (a[cur] a[keyi] cur right){cur;}}*/Swap(a[keyi], a[prev]);return prev;
}【注意】 1.因为prev是从keyi的位置开始的而keyi在循环结束时才进行交换所以我们先让prev再观察prev是否等于cur,如果相等就没有必要交换了 2.如果不相等由于cur比prev先走并且cur只有遇到小于a[keyi]的值才停下来prev,交换prev和cur的值所以a[prev]一定大于a[cur]二者进行交换 3.当curright跳出循环之后prev并没有进行自增那么a[prev]一定是小于a[keyi]的所以直接交换二者即可 6.3快速排序递归实现的完整代码
//交换两个数据
void Swap(int* left, int* right)
{int tmp *left;*left *right;*right tmp;
}
//三数取中
int GetMidIndex(int* a, int left, int right)
{int mid left (right - left) / 2;//int mid (left right) / 2;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;}}
}// [left, right] -- O(N)
// hoare
int PartSort1(int* a, int left, int right)
{//三数取中int mid GetMidIndex(a, left, right);//printf([%d,%d]-%d\n, left, right, mid);Swap(a[mid], a[left]);int keyi left;while (left right){// 6 6 6 6 6// R找小while (left right a[right] a[keyi]){right--;}//L找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}int meeti left;Swap(a[meeti], a[keyi]);return meeti;
}// 挖坑法
int PartSort2(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int key a[left];int hole left;while (left right){// 右边找小填到左边坑while (a[right] key left right){--right;}a[hole] a[right];hole right;// 左边找大填到右边坑while (a[left] key left right){left;}a[hole] a[left];hole left;}a[left] key;return hole;
}//前后指针法
int PartSort3(int* a, int left, int right)
{// 三数取中int mid GetMidIndex(a, left, right);Swap(a[mid], a[left]);int keyi left;int prev left;int cur left 1;while (cur right){// 找小if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}/*while (cur right){while (a[cur] a[keyi] cur right){prev;Swap(a[prev], a[cur]);cur;}while (a[cur] a[keyi] cur right){cur;}}*/Swap(a[keyi], a[prev]);return prev;
}//快速排序
// [begin, end]
void QuickSort(int* a, int begin, int end)
{if (begin end){return;}if (end - begin 8){InsertSort(a begin, end - begin 1);}else{int keyi PartSort3(a, begin, end);//[begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);}
}6.4快速排序非递归实现
经过上面的学习我们已经知道如何使用递归的方式来实现快速排序但是有时候递归的深度太深就会出现栈溢出的问题对于上面的递归过程来说其实是一个数组区间变化的过程先的整个数组然后被分为左右区间左右区间又被分为左右区间…而数组的区间我们用left和right边界表示根据这个思路我们利用这个就可以得到非递归的思路
快速排序的非递归我们需要借助一个数据结构–栈首先我们将数组的左右边界(左闭右闭)入栈然后取出栈顶的right和left作为左右区间取出元素的同时我们需要把这两个元素出栈此时我们就有了左右区间之后我们调用单趟排序对此区间进行排序排序完成之后再将此区间的左右进行入栈操作重复上述操作直到栈为空为止
我们会写快速排序的递归方式为什么还要了解快排的非递归呢首先对于未优化的快速排序当数组中的元素有序或者接近有序的时候我们使用递归的方式的话此时递归的深度为N而递归调用函数的栈帧是在栈上开辟的而栈很小在Linux下只有8M左右所以当我们排序的数据的数量比较大的时候就可能会出现栈溢出对于优化后的快速排序来说三数取中只能保证我们每次取出的key值不是最小或者最次小的数如果我们每次取出的key都是第三第四小的数的时候我们依然可能出栈栈溢出的情况所以对于一些极端的场景我们使用递归的方式进行排序就可能出现栈溢出的情况此时非递归就可以避免这种情况
代码实现
//快速排序非递归
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(st);StackPush(st, begin);StackPush(st, end);while (!StackEmpty(st)){int right StackTop(st);StackPop(st);int left StackTop(st);StackPop(st);int keyi PartSort3(a, left, right);// [left, keyi-1] keyi [keyi1,right]if (keyi 1 right){StackPush(st, keyi 1);StackPush(st, right);}if (left keyi - 1){StackPush(st, left);StackPush(st, keyi - 1);}}StackDestroy(st);
}【注意】 1.我们这里没有提供栈的实现的代码我们自己写的时候需要加上栈实现的代码如果我们已经实现过我们就只需要在当前项目中加上之前我们实现的Stack.h和Stack.c即可 2.由于栈是先进后出的如果我们的入栈顺序为begin,end那么我们的出栈顺序就应该为end,begin 3.对于把递归改成非递归我们通常才用循环利用数据结构的栈和队列来实现我们利用栈和队列的时候通常是模拟递归的过程我们这里就是模拟递归调用的过程所以我们在单趟排序之后选择先入右区间再入左区间这样就使得左区间就会先出栈先进行单趟排序和我们递归方式的顺序一样当然我们也可以先入左区间再入右区间不会影响最终的结果。 6.5复杂度及稳定性
时间复杂度
递归实现
快速排序递归的深度大约是logN(假设为此都是二分)每一层的元素个数大约是N尽管每一层少了之前层数keyi位置的值但是这个数量对于N来说相差很大可以忽略所以数据复杂度为O(N*logN) 非递归实现
入栈和出栈的时间复杂度为O(logN),然后每次单趟排序的时间复杂度为O(N),所以时间复杂度为O(N*logN)
空间复杂度
递归实现函数栈帧的创建消耗空间此时的空间复杂度为O(logN),非递归实现栈的实现有空间的消耗也为O(logN)
稳定性
由于快速排序选出的key值是不确定的在交换的过程中可能顺序会发生改变所以是不稳定的
6.6特性总结 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定 7.归并排序
7.1排序思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并
动图演示 7.2归并排序递归实现
如上图所示如果说快速排序递归实现是相当于二叉树的前序遍历的话那么归并排序的递归实现就相当于二叉树的后续遍历因为归并排序思想本质就是将两个有序数组排成一个有序的数组。
归并排序的基本思想对于两个有序的数组不断的取小的元素尾插对于我们真正困难的是如何达到归并排序的条件–被归并的两个区间的元素必须是有序的这时候我们就需要用到递归的思想了我们需要不断的将待排序的区间分为左右两个子区间进行递归直到左右区间元素的个数为1我们就认为是有序了然后再进行归并返回上一层待上一层的右区间变成有序后进行归并归并之后就把有序的拷贝到原数组然后重复上述的步骤直到原数组的所有元素都有序为止就中思想就和二叉树的后续遍历很相似先访问左子树再访问右子树最后再访问根节点。
我们以10 6 7 1 3 9 4 2 为例先进行不断的缩小子区间直到左右区间元素的个数为1然后10 6 7 13 9,4 2 进行两两归并返回上一层为6 10 1 7 3 9 2 4 再进行两两归并成1 6 7 10 2 3 4 9最后一次归并为1 2 3 4 6 7 9 10此时就完成了排序 代码实现
_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, mid 1, 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, (end - begin 1) * sizeof(int));
}//归并排序
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);tmp NULL;
}【注意】 我们这里开辟了一个和待排序一样大小的tmp数组在每一次归并完成之后需要将tmp数组中归并的结果拷贝到原数组中这里需要注意的是我们进行拷贝的区间(数组下标对应)因为tmp中保存的是整个数组区间中一小部分归并的结果所以我们拷贝的时候也应该拷贝到原数组的对于区间中否则可能会拷贝一些随机值。 7.3归并排序非递归实现
归并排序递归 和快速排序不同的是归并排序的左右区间是严格进行二分的即归并排序递归下来是一棵完全二叉树那么此时的递归深度为logN所以归并排序不用担心栈溢出的问题比如我们需要排序的数据的数量为10亿此时的递归深度为30空间是可以重复利用的左区间递归回来之后函数栈帧销毁继续分配给右区间继续使用所以我们只需要看深度即可看次看来归并排序的非递归的价值不是很大但是呢由于归并排序非递归版本会涉及到区间的边界问题为什么递归不会有这问题呢这是因为我们子函数里面进行也判断只有一个元素或者是不存在的区间就直接递归返回上一层而对于非递归来说就要考虑区间的边界问题这个问题又比较的复杂有的公司可能会拿它来考察我们的编程能力和逻辑思维能力所以我们还是有必要去学习一下
归并排序的非递归不能使用栈来实现因为归并排序的非递归类似于二叉树的后续遍历而同一个区间的left和right可能会被使用多次而栈出栈之后就找不到原来区间的边界了所以非常麻烦我们选择采用循环的方式就行斐波那契数列一样通过前面的区间来得到后面的区间 如上图我们顶一个gap变量用于指定每次进行排序的一组数据元素的个数然后不断二倍增长直到所有的数据都进行归并排序但是这个对于排序的数组元素的个数有严格的限制那就是必须的2^N个否则就可能会发生越界访问 我们仔细分析之后发现越界的情况一共有三种 1.第一组越界第一组越界只可能是right越界因为如果是第一组的left越界那么就不会进入循环就不会进行归并排序此时第二组全部越界那么第一组的数据是有序的右区间么没有需要排序的数据那么就不需要进行归并直接break; 2.第二组全部越界此情况也只有左区间一组数据也不需要进行归并直接break; 3.第二组部分越界即第二组的right越界此时存在左右两组数据需要进行归并那么只能将第二组的right修正为n-1然后再进行归并 代码实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){// gap个数据 gap个数据归并for (int i 0; i n; i 2 * gap){// 归并 取小的尾插int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// 第一组越界if (end1 n){break;}// 第二组全部越界if (begin2 n){break;}// 第二组部分越界if (end2 n){// 修正一下end2继续归并end2 n - 1;}int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}// 拷贝回原数组 -- 归并哪部分就拷贝哪部分回去memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}
7.4复杂度及稳定性
时间复杂度
对于递归实现的归并排序来说递归的深度为logN,每层排序的元素个数为N,所以归并排序的时间复杂度为O(N*logN);对于非递归实现来说gap每次增加2倍每次gap中待排序的数据等于或小于N,所以非递归实现的归并排序的时间复杂度也为O(N*logN)
空间复杂度
归并排序需要额外的和原数组一样大小的第三方数组所以空间复杂度为O(N)
稳定性
归并排序的稳定性取决于我们在单次归并过程中取较小的元素尾插还是取较小或等于的元素尾插但是排序算法的稳定性只要我们能控制成稳定的那么该算法就是稳定的因为任何一个排序算法我们都可以写成不稳定的所以归并排序是稳定的算法
不稳定写法
while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}稳定写法
while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}7.5特性总结 1.归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2.时间复杂度O(N*logN) 3.空间复杂度O(N) 4.稳定性稳定 8.计数排序
8.1排序思想
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
1.统计相同元素出现次数
2.根据统计的结果将序列回收到原来的序列中
计数排序就是将数组中对应的数据出现的次数映射到一个新的初始化为0的新数组的对应的下标中每出现一次下标对应的值就1其中映射分为绝对映射和相对映射
绝对映射
绝对映射就是Count数组中下标为i的位置记录的是待排序数组中值为i的元素出现的次数我们先遍历一遍原数组找出原数组中的最大元素(数组中的元素都大于0)然后我们开辟一个比原数组大于1的空间然后我们将原数组中的数据映射到新的数组中最后我们遍历新数组根据新数组中对应下标的值输出即可该下标的数组就是下标的出现次数。 相对映射
我们了解绝对映射的原理之后就会发现绝对映射有以下的缺陷 1.绝对映射排序的数组中的元素不能的负数因为数组的下标从0开始不能为负数 2.当待排序的数组元素值比较大的时候我们就需要开辟一个很大的空间此时就会有很大的空间浪费 基于绝对映射的缺陷我们又设计出了相对映射来对其进行一定程度上的优化其基本思路为
我们不再根据数组的最大元素来开辟空间而是根据数组中的最大元素和最小元素的差值来开辟空间开辟空间的大小为最大元素-最小元素1映射的规则为元素值的大小减去最小元素的大小映射到开辟数组的下标这样我们数组中的负数也可以进行映射我们取出元素时覆盖到原数组的值为下标加上最小值 8.2代码实现
// 时间复杂度O(Nrange)
// 空间复杂度O(range)
// 适合数据范围集中也就是range小
// 只适合整数不适合浮点数、字符串等
//计数排序
void CountSort(int* a, int n)
{int max a[0], min a[0];for (int i 1; i n; i){if (a[i] max){max a[i];}if (a[i] min){min a[i];}}int range max - min 1;// 统计次数int* Count (int*)malloc(sizeof(int) * range);if (Count NULL){perror(malloc fail);return;}memset(Count, 0, sizeof(int) * range);for (int i 0; i n; i){Count[a[i] - min];}// 排序int j 0;for (int i 0; i range; i){while (Count[i]--){a[j] i min;j;}}
}8.3计数排序的缺陷
计数排序看起来效率很高但是它有如下两个缺陷 1.计数排序只能对整型数据进行排序对于浮点型字符型类型等其他类型的数据则不能使用计数排序 2.计数排序适用于数据分布较为集中的情况当我们分布较分散的时候空间复杂度就会很大 8.4特性总结 1.计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2.时间复杂度O(MAX(Nrange)) 3.空间复杂度O(range) 4.稳定性稳定 三、排序总结 排序方法平均情况最好情况最坏情况辅助空间稳定性直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(n*logN)~O(N^2)O(N^1.3)O(N^2)O(1)不稳定直接选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定堆排序O(n*logN)O(n*logN)O(n*logN)O(1)不稳定冒泡排序O(N^2)O(N)O(N^2)O(1)稳定快速排序O(n*logN)O(n*logN)O(N^2)O(logN)~O(N)不稳定归并排序O(n*logN)O(n*logN)O(n^2)O(N)稳定计数排序O(MAX(Nrange))O(MAX(Nrange))O(MAX(Nrange))O(range)稳定
