个人网站的建设目标,网页设计学校网站,人社部门网站建设,旅游电子商务网站目录 #x1f34f;一.排序的概念及应用#x1f34f; 1.排序的概念 2.排序的应用 3.常用的排序算法
#x1f34e;二.排序算法的实现#x1f34e;
1.插入排序
1.1直接插入排序
1.2希尔排序#xff08;缩小增量排序#xff09;
2.选择排序
2.1直接选择排序
2.2堆排序…目录 一.排序的概念及应用 1.排序的概念 2.排序的应用 3.常用的排序算法
二.排序算法的实现
1.插入排序
1.1直接插入排序
1.2希尔排序缩小增量排序
2.选择排序
2.1直接选择排序
2.2堆排序
3.比较排序
3.1冒泡排序
3.2快速排序
递归版本
快速排序递归优化
快速排序递归总过程
4.归并排序
5.计数排序
三.排序总结 一.排序的概念及应用
1.排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 我们可以通过学生的结构体来理解把学生结构体看成记录学生结构体里有姓名、成绩、学号等成员任一成员都可以当成关键字比如我们需要按照成绩对学生进行排名则成绩作为关键字进行排序即使得学生结构体这一记录通过成绩这一关键字进行排序 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 也就是有一个对于数组里面两个相同的数比如说有一个5a和5b排序前5a在5b前面排序后5a依然在5b的前面就说明此排序是稳定的反之排序之后5a跑到5b的后面去了就说明此排序是不稳定的 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 2.排序的应用 在我们日常购物中我们经常会对物品进行排序比如我要在京东买一个书包我会优先选择很多人都买的于是我会点击销量排序选择销量好的书包 我们高考填志愿时如果你考到了650分以上的成绩你肯定会去找中国排名前几的大学去填志愿而大学的排名就是根据综合实力和录取分数线进行排序的 3.常用的排序算法 常用的排序算法有八大排序算法分别是直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序 二.排序算法的实现 1.插入排序 本篇文章所有排序算法只讨论升序
1.1直接插入排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 最经典的例子就是扑克牌当我们玩扑克牌时如果手上有 一对顺子56789 我们已经 找到了5679最后才找到8 然后我们 需要将8插入到扑克牌中 那肯定是插入到7和9中间构成一对顺子 将9在手上挪一个位置然后将8放到7的后面该过程就是一次直接插入排序 当插入第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)
{for (int i 0; i n-1 ; i){//end从第二个元素开始int end i 1;//保存待插入元素int tmp a[end];int j;//j从待插入元素前一个元素开始比较for ( j i; j 0; j--){if (a[j] tmp)//如果元素比待插入元素大则将该元素往后移a[j 1] a[j];else//如果遇到小于等于待插入元素的元素则退出并将待插入元素放到该元素后面{break;}}/*把待插入元素放到该元素后面如果上面循环结束之后依然没有找到比待插入元素小的说明待插入排序是最小的即应该放到第一个位置上面循环结束j为-1j后面的位置即为下标为0的位置符合要求*/a[j 1] tmp;}
}
直接插入排序的特性总结
1.元素集合越接近有序直接插入排序的时间效率越高 由于待插入元素需要和前面已经有序的区间元素进行依次比较假设原集合本身就是有序的那么待插入元素只的前一个元素肯定比它小所以只需比较一次而所插入的位置就是待插入元素本身所在的位置即减少了比较和移动的次数所以当原集合有序或者接近有序时直接插入的时间效率会大大提升
2.时间复杂度O(N^2) 假设原集合是逆序的那么从第二个元素开始插入第二个元素要挪动1次插入第三个元素要挪动2次插入第四个元素要挪动3次插入最后一个元素则要挪动n-1次可以发现挪动的次数加起来是一个等差数列1234..n-1由等差数列求和公式可以算出总移动次数为n*(n-1)/2,即时间复杂度为O(N^2)
3.空间复杂度O(1) 由于直接插入元素是在原数组进行比较和移动的没有开辟额外空间也没有递归过程故直接插入排序空间复杂度为O(1)
4.稳定性稳定 由于直接插入排序在比较的过程中是遇到小于等于待插入元素的元素时就停止即遇到相同的元素是将待插入元素放在该元素的后面而不是前面故相同元素的相对前后位置不变所以直接插入排序是稳定的排序 1.2希尔排序缩小增量排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取新的gap为原来的一半重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 希尔排序是直接插入排序的一种优化它把一组记录分成若干组进行类似于直接插入排序的操作每一组数据中从这组的第二个元素开始一次与前面的元素进行比较然后插入只不过直接插入排序是与从相邻的元素开始比较而组内的元素是从相邻gap的元素进行比较将每组数据都排好后我们会将新的gap变为原来的一半然后继续分成gap组每组元素进行类似直接插入排序直到gap1当gap等于1的时候就相当于就是直接插入排序了由于之前每组元素都经过了排序所以此时这组记录已经接近有序利用直接插入排序就会大大提高效率
gap1的分组排序操作称之为预排
gap1时则为直接插入排序
即希尔排序的两个步骤为
1.预排
2.直接插入排序 代码 void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap / 2;//每次新的gap为原来的一半for (int i 0; i n - gap; i)//从第二个元素开始让此元素在所在的组内进行排序{int end i gap;//待插入元素的位置int tmp a[end];//保存待插入元素int j 0;for (j i; j 0; j - gap)//从待插入元素距离gap的第一个元素开始比较{if (a[j] tmp)//元素大于待插入元素则往后挪动gap步a[j gap] a[j];else//元素小于等于待插入元素则退出break;}/*循环正常退出则说明待插入元素为该组最小的元素即应该要插到该组第一个位置循环break退出则说明中途找到小于等于待插入元素的元素插入到该元素后面距离gap的位置*/a[j gap] tmp;}}
} 希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果 3.希尔排序的时间复杂度不好计算因为在预排过程中gap的值取值很多 《数据结构 (C 语言版 ) 》 --- 严蔚敏 《数据结构-用面向对象方法与C描述》--- 殷人昆 目前比较公认的一个数据为On^1.3 2.选择排序 2.1直接选择排序 每一次从待排序的数据元素中选出最小和最大的一个元素分别存放在数组的左端和右端然后将待排序的范围减少2即减去上次存放到的左端和右端直到全部待排序的数据元素排完 。 下面为只选择最大或最小的元素的情况的动图展示同时选择最大和最小的元素的情况同理 相当于每次排序我们都在待排序的范围内选出最大和最小的元素放在两端然后待排序范围从两边慢慢往中间缩小直到所有元素排序完成
代码
void SelectSort(int* a, int n)
{int begin 0, end n - 1;//定义两个头尾下标while (begin end){int max begin, min begin;//假设最大值和最小值为第一个元素for (int i begin; i end; i)//在排序范围内遍历比较{if (a[i] a[min])//更新最小值min i;if (a[i] a[max])//更新最大值max i;}//循环结束后即选出最大值和最小值//将最小值放到左端Swap(a[begin], a[min]);/*如果最大值的下标在左端那么将最小值左端则会覆盖最大值而原来在左端的最大值交换之后就跑到最小值的下标去了所以需要更新最大值的下标*/if (max begin)max min;//然后将最大值放到右端Swap(a[end], a[max]);//头下标尾下标--即让待排序范围begin;end--;}
} 选择排序的特性总结
1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用
2.时间复杂度O(N^2 由于选择排序无论什么情况下遍历的比较次数都是一样的即一开始遍历n次找出一个最大和最小的元素之后待排序范围减少2即为n-2第二次遍历n-2次相应地第三次遍历n-3可以看到排序过程的总比较次数是一个等差数列由等差数列求和公式可以得知时间复杂度为O(N^2)
3.空间复杂度O(1) 由于选择排序只在原数组遍历和比较交换没有开辟额外空间也没有递归操作故选择排序的的空间复杂度为O(1
4.稳定性不稳定 由于选择排序数据存在较大的跳跃交换故选择排序不稳定 2.2堆排序
堆排序即利用堆的思想进行排序总共分为两个步骤 1.建堆 升序建大堆 降序: 建小堆 2.利用堆删除思想来进行排序 建堆用到了向下调整因此掌握了向下调整就可以完成堆排序 向下调整算法 以某一个父亲节点开始让它与自己的孩子节点比较当父节点小于最大的孩子节点时为什么要与最大的孩子节点交换如果将较小的孩子换上去成为父节点此父节点依然小于最大孩子节点显然这不符合大堆的性质于是需要将两个节点的值交换最大孩子节点变为父节点之前的父节点往下成为孩子节点新的孩子节点作为父节点依然需要与下一个孩子节点比较直到所有节点都符合大堆的性质原来的父亲节点再调整的过程中不断往下走故称为向下调整如图所示 向下调整算法有一个前提左右子树必须是一个堆才能调整 向下调整代码设计和过程 函数的参数为一个数组以及数组的大小和父节点下标首先通过父节点下标算出最大孩子节点的下标接着进行两者的比较如果父节点小于最大孩子节点则两者交换并更新父节点再算出新的最大孩子节点以此循环直到符合大堆的性质或者父节点已经走到最后则调整结束 向下调整算法代码
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child parent * 2 1;//通过父节点算出最大孩子节点假设最大孩子为左节点while (childn){//如果右节点大于左节点则将最大孩子设为右节点if (child1na[child 1] a[child]){child;}if (a[child] a[parent])//父节点小于最大孩子节点则调整{Swap(a[child], a[parent]);//将父节点与最大孩子节点交换parent child;//更新父节点child parent * 2 1;//再算出新的最大孩子节点}else{break;//不需要调整则直接退出}}
} 排序过程建立大堆大堆能够相对较大的元素在堆顶首先让堆顶元素和最后一个元素交换然后数组大小减1再对堆顶元素应用向下调整此时第二大的数就在堆顶了第一轮就可以将最大的树放到数组最后面依次进行第二轮则可以将第二大的数放到数组的倒数第二个位置直到数组的大小变为1即排序完成 代码
void HeapSort(int* a, int n)
{for (int i n/2; i0; i--)//从倒数第一个非叶子结点开始建立大堆{AdjustDwon(a, n, i);}int end n - 1;while (end0){Swap(a[0], a[end]);//将堆顶元素与最后一个元素交换AdjustDwon(a, end, 0);//然后将堆顶元素进行向下调整end--;//数组范围减1}
} 堆排序的特性总结
1.时间复杂度O(N*logN) 建堆的时间复杂度为O(N详见文章【数据结构】树和二叉树——堆有n个元素堆顶元素和最后一个元素交换的次数为n-1每次交换之后需要进行向下调整向下调整算法时间复杂度为O(logN),所以总的时间复杂度为O(N*logN)
2.空间复杂度O(1) 由于堆排序只在原数组上进行建堆和比较交换没有开辟额外空间也没有递归操作故选择排序的的空间复杂度为O(1
3.稳定性不稳定 由于堆排序过程中堆顶与最后一个元素存在较大的数据跳跃交换故堆排序不稳定 3.比较排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 3.1冒泡排序 冒泡排序可以说我们大学生的最爱了因为我们学习编程语言时接触到的第一个排序一般就是冒泡排序因为其简单易理解所以知名度很高 冒泡排序基本思想从一个元素开始进行相邻元素两两比较即一个元素与第二个元素然后第二个元素与第三个元素比较依次类推直到倒数第二个元素与最后一个元素进行比较在两两比较的过程中如果前面的元素大于后面的元素即逆序则将两个元素交换进行一轮之后可以发现将最大的元素换到了最后然后将排序的范围减1再进行一轮则将第二大的元素换到最后即整体的倒数第二个位置因为排序的范围已经减1这样每次都把相对较大的数换到最后面类似与水中的起泡过程所以叫做冒泡排序 n个元素每次将相对较大的数换到后面需要换n-1趟因为只剩一个数的时候已经有序然后每一趟的比较次数是n-1-ii为已经换到最后的数 第一趟的比较有n个元素所以需要两两比较n-1次第一趟后排好一个数排序范围减1 第二趟的比较有n-1个元素所以需要两两比较n--2次第二趟后排好两个数排序范围减1 ... 下面是动图展示 代码 void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i)//n个元素需要进行n-1趟比较{int flag 0;//定义一个变量用来判断是否发生交换for (int j 0; j n - 1 - i; j)//每一趟的比较次数为n-1-i{if (a[j 1] a[j])//如果前面元素大于后面则将两者交换{Swap(a[j 1], a[j]);flag 1;//判断变量置为1}}if (flag 0)//如果一趟比较后flag依然为0说明没有发生交换则证明已经有序退出排序break;}
}
冒泡排序的特性总结
1.时间复杂度O(N^2) 最坏情况下即数组的元素为逆序第一趟交换次数为n-1次第二趟交换次数为n-2以此类推我们可以发现每一趟比较次数构成等差数列由等差数列求和公式可以求得时间复杂度为O(N^2)
2.空间复杂度O(1) 由于冒泡排序只在原数组进行比较和交换没有开辟额外空间也没有递归过程故冒泡排序空间复杂度为O(1)
3.稳定性稳定 冒泡排序每一趟只进行两两比较而且只在前面元素大于后面元素的情况下发生交换没有发生元素跳跃交换故冒泡排序是稳定排序 3.2快速排序 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 快速排序分为递归和非递归两个版本 递归版本 1. hoare 版本 基本思想 定义两个左右指针下标分别指向第一个元素和最后一个元素选取基准值让右指针先走右指针走到比基准值小的元素就停下然后让左指针开始走直到左指针找到比基准值大的元素就停下然后交换两个指针对应的值然后继续让右指针找小停下左指针找大停下然后交换直到两个指针相遇然后将基准值和两个指针指向的值交换这样基准值的左边都是比基准值小的元素基准值的右边都是比基准值大的元素然后再递归分割左区间和右区间 下面是动图展示 分割完区间之后类似于下面的示意图可以发现该过程与二叉树的前序遍历相似所以整体逻辑可以按照前序遍历的思想进行关键在于单趟排序的设计 单趟代码
int PartSort1(int* a, int left, int right)
{int mid GetMidIndex(a, left, right);//三数取中选取基准值Swap(a[left], a[mid]);//将选取的基准值放到最左边int begin left, end right;//定义左右指针int keyi left;//基准值下标while (begin end){while (begin end a[end] a[keyi])//右指针找到小于基准值的元素才停下end--;while (begin end a[begin] a[keyi])//右指针停下后让左指针找大再停下begin;Swap(a[begin], a[end]);//交换两个指针对应的值}Swap(a[keyi], a[begin]);//两个指针相遇则循环结束让基准值和两个指针指向的值交换keyi begin;//基准值的下标变为指针相遇的地方return keyi;//返回基准值的下标
}
每一趟排序都将基准值交换到了它该位于的位置因为排序后左边区间都是小于等于它的值右边区间都是大于等于它的值
下面我们讨论为什么为什么两个指针相遇地方的值一定小于基准值
指针相遇有两种情况
1.右指针停下左指针与它相遇右指针遇到小才停下所以左指针与它相遇对应的值比基准值小
2.左指针停下右指针与它相遇左指针遇到大停下而后与右指针的值交换由于右指针的值是小于基准值的所以交换后左指针指向的值就是小于基准值的值所以右指针与它相遇对应的值比基准值小 2.挖坑法版本 基本思想定义两个左右指针再定义一个坑位下标开始默认坑位是第一个位置选择一开始坑位所在的值为基准值同样也是右指针先走不同的是右指针找到小之后将值放到坑位然后坑位更新为右指针指向的位置然后让左指针找大找到大之后将值放到坑位然后坑位更新为左指针指向的位置直到两个指针相遇然后将基准住放到两个指针相遇的地方继续以指针相遇的地方分割左区间和右区间进行递归
下面是动图展示 单趟排序代码
int PartSort2(int* a, int left, int right)
{int mid GetMidIndex(a, left, right);//三数取中选取基准值Swap(a[left], a[mid]);//将基准值放到第一个元素int begin left, end right;//定义前后指针int key a[begin];//保存基准值int hole begin;//一开始坑位默认为第一个位置while (begin end){while (begin end a[end] key)//右指针找小才停下right--;a[hole] a[right];//把找到的小的值放到坑位hole right;//坑位更新为右指针指向的位置while (begin end a[begin] key)//然后让左指针找大begin;a[hole] a[begin];//将找到的大的值放到坑位hole begin;//坑位更新为左指针指向的位置}a[hole] key;//两个指针相遇后将保存的基准值放到两个指针相遇的地方即最后的坑位return hole;//返回坑位以进行分割区间进行递归
} 下面我们讨论为什么两个指针会相遇在坑位上
指针相遇有两种情况
1.右指针停下左指针与它相遇右指针找到小才停下然后把小的值放到坑位后坑位更新为右指针指向的地方所以右指针停下之后会成为坑位所以左指针与它相遇会相遇在坑位
2.左指针停下右指针与它相遇左指针找到大才停下然后把大的值放到坑位后坑位更新为左指针指向的地方所以左指针停下之后会成为坑位所以右指针与它相遇会相遇在坑位 3.前后指针版本 基本思想定义一个前指针pre指向第二个位置定义一个后指针cur指向第二个位置选取基准值然后让cur指针先走当cur指针找到小之后让pre指针向前一步然后再交换两个指针指向的值以此类推直到cur指针走过最后一个位置最后让基准值与pre指针指向的值进行交换然后将基准值的下标更新为pre的位置以便返回新的基准值的下标进行分割区间递归
下面是动图展示 单趟代码
int PartSort3(int* a, int left, int right)
{int mid GetMidIndex(a, left, right);//三数取中选取基准值Swap(a[left], a[mid]);//将基准值放到第一个位置int keyi left;//由于left下标整个过程不变所以保存基准值的下标int pre left;//定义前指针指向第一个元素int cur left 1;//定义后指针指向第二个元素while (cur right){if (a[cur] a[keyi] pre ! cur)//后指针找到小且pre指针向前一步的值不与后指针的值相等就交换Swap(a[cur], a[pre]);cur;//后指针向后走}Swap(a[keyi], a[pre]);//循环结束后将基准值放到pre的位置keyi pre;//基准值下标更新为pre的位置return keyi;//返回新的基准值以分割区间进行递归
}
上面我们对快速排序递归单趟的三种版本进行了学习下面我们进行一些优化 快速排序递归优化
1.三数取中 当原来的元素已经是有序或者接近时我们每次选取最左边的元素作为基准值则会导致选取的基准值每次都是最大或者最小的一趟排序后就会变成基准值的左边都是小于等于的值而右边没有值基准值为最大的值或者基准值的左边没有值而右边都是大于等于的值基准值为最小的值这样我们进行递归分割区间时每次区间只缩小了1所以第一趟排序遍历比较的次数为n-1第二个排序遍历比较的次数为n-2以此类推可以发现每一趟的比较次数是一个等差数列n-1n-2n-3..321,由等差数列的求和公式可以求得此时的时间复杂度为O(N^2 显然当原来的元素已经有序或者将接近有序时就成为了快速排序的最坏情况再利用原来的每次只选取最左边的元素作为基准值已经行不通于是有人提出了一种优化方法——三数取中法 三数取中 选取三个元素最左边的元素中间位置的元素最右边的元素然后两两进行比较选出中间大小的那个数然后把这个数放到最左边作为基准值
代码
int GetMidIndex(int *a, int begin, int end)
{int mid (begin end) / 2;if (a[begin] a[end]){if (a[end] a[mid])return end;else if (a[begin] a[mid])return mid;elsereturn begin;}else{if (a[begin] a[mid])return end;else if (a[begin] a[mid])return mid;elsereturn begin;}
}
2.小区间优化 我们前面已经介绍过快速排序的递归过程类似于二叉树的前序遍历而我们知道二叉树最后几层的元素个数是占据绝大部分的当递归到区间很小时比如递归区间只有10个数显然递归到只剩10个数时已经递归到最后几层对于10个数排序调用递归而且递归那么多次显然是杀鸡用了牛刀费时费空间而且效率也低于是有人提出了一种优化——小区间优化 小区间优化即当递归区间已经很小的时候可以选用直接插入排序对递归区间进行排序这样就减少了递归过程中绝大数的递归次数提高了快速排序的效率 快速排序递归总过程 先判断区间是否只有一个值或者不存在如果是一个值可以认为其已经有序则直接返回如果不是则执行排序过程先进行小区间优化非小区间则进行三数取中法选取基准值然后进行上面三个版本的任一单趟过程单趟排序后被分割成两个区间然后对这两个区间分别进行递归排序
总代码
void QuickSort(int* a, int left, int right)
{if (left right)//left等于right则说明该区间只有一个值大于则说明区间不存在return;if(left-right 1 10)//小区间优化如果区间范围小于10则进行直接插入排序{InsertSort(a left, right-left1);}else{int keyi PartSort3(a,left,right);//单趟排序后返回更新后的基准值下标//以单趟排序后的更新后基准值下标k为分割分割成[left,keyi-1] keyi [keyi1,right]QuickSort(a, left, keyi - 1);//递归左区间QuickSort(a, keyi1, right);//递归右区间}
}
快速排序非递归 基本思想利用栈模拟递归过程先让整体区间入栈先入栈区间左下标再入栈区间右下标然后再将区间下标出栈调用单趟排序单趟排序后分割成两个区间由于栈是先进后出的区间低估过程是先递归左边所以单趟排序后先入栈右区间再入栈左区间然后接着出栈一个区间进行单趟排序排序后再入栈分割后的右区间和左区间直到栈为空则排序完成 代码
void QuickSortNonR(int* a, int left, int right)
{Stack st;//定义栈StackInit(st);//栈的初始化StackPush(st, left);//入栈区间左下标StackPush(st, right);//再入栈区间右下标while (!StackEmpty(st))//栈为空则结束{//取出一个区间进行单趟排序int right StackTop(st);StackPop(st);int left StackTop(st);StackPop(st);int keyi PartSort3(a, left, 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. 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 2.时间复杂度O(NlogN) 快速排序再进行相应的优化后效率大大提升通过递归展开图可以发现每趟递归只处理一个值有N个值由二叉树的有关知识可以得知总共有logN层第一层遍历的次数诶N第二层遍历的次数为N-1第三层遍历的次数为N-2..每一层的时间复杂度为O(N)有logN层所以时间复杂度为O(N*logN) 3.空间复杂度O(logN) 由于快速排序存在递归过程递归的层数为logN层递归过程需要开辟一定空间的栈帧所以空间复杂度为O(logN) 4.稳定性不稳定 由于快速排序存在较大的跳跃交换过程故快速排序不稳定 4.归并排序 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 可以看出归并排序递归过程可以看成是二叉树的后续遍历即让左右区间先排序等左右区间都有序了再将左右区间合并一起排序。 归并排序是每次将区间二分进行递归直到递归到只有一个元素过着区间不存在只有一个元素可以认为其已经有序所以回溯至上一层然后上一层将左右区间合并排序再回溯至上一层直到回溯到顶层将整体的左右区间进行合并两个区间的合并过程类似于合并两个有序数组的过程详情见代码 实际上是空间换时间的思想归并排序一开始就开辟了待排序元素的等额空间每趟合并在额外空间排序然后将合并后的元素又拷贝至原数组
下面是动图展示 代码
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin end)//只有一个元素或者区间不存在则已经有序直接返回return;int mid (begin end) / 2;//二分区间_MergeSort(a, begin, mid,tmp);//递归左区间_MergeSort(a,mid1, end,tmp);//递归右区间//左右区间有序后进行合并int begin1 begin, end1 mid;//定义左区间指针下标int begin2 mid 1, end2 end;//定义右区间指针下标int j begin;//从区间起始位置开始存元素while (begin1 end1 begin2 end2)//有一个区间元素放完了就结束{if (a[begin1] a[begin2])//如果左区间指针指向的元素比右区间指针指向的元素小则将小的元素放到tmp数组内tmp[j] a[begin1];elsetmp[j] a[begin2];//反之}//有一个区间的元素元素放完了但是不知道具体哪个区间还没有放完所以两个区间都将剩下的元素放进tmp数组while(begin1end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];//单趟合并后将元素拷贝至原数组memcpy(a begin, tmp begin, sizeof(int)*(end2 - begin 1));
}
void MergeSort(int* a, int n)
{int* tmp malloc(sizeof(int) * n);//开辟额外的等额数组空间if (tmp NULL)//检查是否开辟成功{perror(malloc fail);exit(-1);}_MergeSort(a, 0, n - 1, tmp);//调用归并排序free(tmp);//释放额外空间tmp NULL;
}
归并排序非递归版本 基本思想先让每个区间只有一个元素只有一个元素认为有序即每个区间都是有序的则每两个区间两两归并然后让每个区间只有两个元素然后让每两个区间进行两两归并每次让区间的元素个数扩大两倍直到每个区间的元素数设定超过元素总数即结束 非递归过程过程中存在的问题由于区间的元素个数是成倍增长的而待排序元素个数不一定是区间元素个数的倍数这必然会导致在取区间的时候存在越界问题 解决方法
1.end1越界 en1越界则begin2和end2也越界由于只有最区间一部分元素合法右区间都不合法即没有两个可以合并的区间则直接break,跳出此次循环
2.begin2越界 begin2越界则end2必越界也是和第一点一样整个右区间都不合法即没有两个可以合并的区间则直接break,跳出此次循环
3.只有end2越界 只有end2越界说明右区间也是有一部分合法的元素我们只需将end2修正为n-1即可然后将两个区间合并 代码
void MergeSortNonR(int* a, int n)
{int* tmp (int *)malloc(sizeof(int)*n);//开辟额外的等额空间int gap 1;//定义每个区间的元素个数一开始为1while (gap n){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;//划分右区间int j i;//解决区间越界问题if (end1 n)break;else if (begin2 n)break;else if (end2 n){end2 n - 1;}//合并两个区间while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[j] a[begin1];elsetmp[j] a[begin2];}while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];//合并之后将元素拷贝至原数组memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;//让区间的元素个数翻倍}free(tmp);//排序完后释放额外空间tmp NULL;
}
归并排序的特性总结
1.归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题
2.时间复杂度O(NlogN) 由归并排序的递归过程可以发现其类似于二叉树的后序遍历过程总共由logN层每一层都要遍历N个元素所以时间复杂度为O(N*logN)
3.空间复杂度O(N 归并排序主要应用了空间换时间的思想开辟了等额的空间故空间复杂度为O(N)
4.稳定性稳定 由于归并排序是分区间排序然后再合并且在小区间比较过程没有发生大的跳跃交换过程中故归并排序是稳定排序 5.计数排序 基本思想遍历找出待排序元素的最大值和最小值并求出它们的差值然后开辟差值数量大小的空间并全都初始化为0遍历原数组将每一数组元素减去最小值相对映射然后得到一个下标将次下标对应的额外空间的值加1,然后遍历完原数组后再将额外空间的每个下标的值的次数将元素放回原数组 总步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中 代码 void CountSort(int* a, int n)
{int min a[0], max a[0];//假设最小值和最大值for (int i 0; i n; i)//遍历原数组找出最小值和最大值{if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;//求出最大值和最下值的差值int* tmp (int *)calloc(range,sizeof(int));//开辟差值数量大小的空间并都初始化为0if (tmp NULL)//检查是否开辟成功{perror(calloc fail);exit(-1);}for (int i 0; i n; i)//遍历原数组将每个元素减去最小值得到一个下标将额外空间的次下标的值加1{tmp[(a[i] - min)];}int j 0;for ( int i 0; i range; i)//遍历完之后按照额外空间的值的大小将元素放回原数组{while (tmp[i]--){a[j] i min;}}free(tmp);//排序完释放额外空间tmp NULL;
}
计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 如果原数组的最大值与最小值的差值很大而原数组的元素个数又很少则必然会造成空间的严重浪费 2.时间复杂度O(max(N,范围)) 计数排序需要遍历两次原数组此过程的时间复杂度为O(N)然后后面由需要遍历一次额外空间此过程的时间复杂度为O(范围故计数排序的空间复杂度为O(max(N,范围)) 3.空间复杂度O范围 由于计数排序开辟了最大值与最小值的差值数量的额外空间故计数排序的空间复杂度为O(范围 4.稳定性稳定 由于计数排序为非比较排序没有发生比较和交换的过程故计数排序为稳定排序 三.排序总结 好啦关于八大排序的学习我们就先学到这里如果对您有所帮助欢迎一键三连~
