网站html动态效果,微信小程序开发难吗,建立与建设的区别,自媒体135客户端下载文章目录 一、常见的排序算法二、插入排序2.1、直接插入排序2.2、希尔排序( 缩小增量排序 ) 三、选择排序3.1、直接选择排序3.2、堆排序3.2.1、堆排序的代码实现 一、常见的排序算法 常见排序算法中有四大排序算法#xff0c;第一是插入排序#xff0c;二是选择排序#xff… 文章目录 一、常见的排序算法二、插入排序2.1、直接插入排序2.2、希尔排序( 缩小增量排序 ) 三、选择排序3.1、直接选择排序3.2、堆排序3.2.1、堆排序的代码实现 一、常见的排序算法 常见排序算法中有四大排序算法第一是插入排序二是选择排序三是交换排序四是归并排序。本站文章针对前两个排序这其中不才将拿出每个排序中所具有代表性的排序算法进行深入解读。 二、插入排序
基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想
2.1、直接插入排序 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 代码实现
void InsertSort(int* arr, int n) {// 外层循环从第二个元素开始逐步处理每个元素for (int i 0; i n - 1; i) {// tmp 是当前元素的索引初始值是 i1表示从第二个元素开始int tmp i 1;// end 是已排序部分的最后一个索引初始值是 iint end i;// 把当前比较的数据保护起来int num arr[tmp];// 内层循环寻找当前元素插入的位置while (end 0) {// 如果已排序部分的元素大于当前元素if (arr[end] num) {// 已经把当前元素比较保护好可以将已排序部分的元素向右移动arr[tmp] arr[end];// tmp 和 end 都向左移一位tmp--;end--;}else {// 找到合适的位置不需要继续向左移动了break;}}// 将当前元素插入到合适的位置arr[tmp] num;}
}
时间复杂度
最好的情况是如果数组已经是有序的或者几乎有序只需要进行一轮比较时间复杂度是O(n)。最坏的情况是数组是逆序的每次都要比较所有已排序的元素时间复杂度是O(n²)。
直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)稳定性稳定 2.2、希尔排序( 缩小增量排序 )
希尔排序法又称缩小增量法。希尔排序法的基本思想是 先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时即为直接插入排序所有记录在统一组内排好序。 希尔排序的工作原理 初始间隔gap希尔排序的关键点在于选择一个合适的“间隔”序列也叫做增量序列。初始时希尔排序会使用一个较大的间隔比如n/2然后通过逐渐缩小间隔来进行多次排序。 分组插入排序每次排序时希尔排序将待排序的序列按间隔分成多个子序列。然后对每个子序列分别进行插入排序。例如间隔为2时序列的第一个元素、第三个元素、第五个元素、第七个元素、第九个元素形成一个子序列(如下图gap2时)。然后对这个子序列进行插入排序。接着处理间隔更小的子序列直到间隔为1时整个序列就是有序的。 逐渐减小间隔随着间隔的逐步减小元素变得越来越接近排序完成最后当间隔为1时希尔排序就变成了直接插入排序。 总的来说希尔排序就是直接排序PRO MAX版本。使用希尔排序它可以快速地把大数放在右边小数放在左边。在快速区分大小数位置之后就比原先的混乱顺序变得更有序在直接插入排序中我们知道元素集合越接近有序直接插入排序算法的时间效率越高我们就不断的往有序的方向靠近最后再直接在使用直接排序就可以缩短大部分时间。如下图我们使用gap来表示每一次比较的跨越元素个数。
代码的实现两种循环的实现
void shellSort(int* arr, int n) {int gap n / 3 1;while (gap 1) {// 判断收缩gap的值直到gap值为1时完成插入排序//int gap 3;//for (int j 0; j gap; j) {//end要分别对gap分出的gap个数组进行排序这样便可完成数组中每个位置的比较//for (int i 0; i n - 1 - gap; i gap) { // 把间距把分开的每个tmp位置都进行插入排序for (int end 0; end n - gap; end) { //这样设置循环可以把end在数组中的每个位置都走一边 与上面两层循环相比只是逻辑不同效率上没有变化//int end i j;int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;}//}//}gap gap / 3 1;}
}排序代码的实现得有里到外的编写这样容易把控首先编写一个正常的直接插入排序并且把gap加上。
for (int i 0; i n - 1; i) {int gap 1;int tmp i gap;int end i;int num arr[i gap];while (end 0){if (arr[end] num) {arr[tmp] arr[end];tmp--;end--;}else {break;}}arr[tmp] num;
}这样我们就改好了直接插入排序有gap时的写法了我们开始修改gap每次跳转的范围首先以gap2为例首先我们把i每次增加的个数都增加gap个。我们也优化变量
int gap 2;
for (int i 0; i n - 1 - gap; i gap) {int end i;int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;
}这个时候我们就完成了一个子序列第一个元素、第三个元素、第五个元素、第七个元素、第九个元素的元素排序。但是我们gap 2时我们是把原数组分为两个子序列。所以要对两个子序列都进行排序。这样我们就必须在外面再套一层循环来把gap分开的子序列都进行排序。(如下图中被分开为红蓝两个子序列)
int gap 2;
for (int j 0; j gap; j) {for (int i 0; i n - 1 - gap; i gap) {int end i j;int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;}
}子序列的第一个节点起始点永远不会再第一个子序列的第二个节点的后面所以我们可以通过套用外层循环j遍历的控制end的起始地址则这样就可以完成多个子序列的访问。 这时候我们就可以完成所有子序列的第一次排序。但是为了完成原数组的整体排序我们必须要让gap每完成一个排序就减少直到gap 1时变为直接插入排序完成数组的排序。
int gap 2;
while (gap 0) {for (int j 0; j gap; j) {for (int i 0; i n - 1 - gap; i gap) {int end i j;int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;}}gap--;
}这样我们就完成了一个低效版本的希尔排序
为何说是低效版本呢因为gap的值是固定的。当数据量达到数十亿的级别之后。我们一个区区的常量2的效率与直接插入排序的效率几户一样。
这时候就有大佬研究出目前位置希尔排序gap的最好取值之二(n是数组的元素个数)gap n/2或gap n/3 1(最快)。我们再自己手搓希尔排序时使用gap选择哪个都可以。不才选择gap n/3 1作为示范。
int gap n;
while (gap 1) {gap (gap / 3) 1;for (int j 0; j gap; j) {for (int i 0; i n - 1 - gap; i gap) {int end i j;int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];end - gap;}else {break;}}arr[end gap] tmp;}}
}在使用gap n/3 1之后每次gap缩小值都是gap/3 1。无论是什么数循环到一定次数后最后除三的都会变为零。当除3等于0时再加一gap就等于1这时候就是直接插入排序。当gap 1时就不会再进入循环。
但此时上面循环中i、j就只是为了控制end变量起始位置可以遍历一遍数组end每次都是与gap位后的数值进行比较。那么我们就可以把两层循环变为一层循环
void shellSort(int* arr, int n) {int gap n;while (gap 1) {// 再收缩gap的值直到gap值为1时完成插入排序gap gap / 3 1;for (int end 0; end n - gap; end) { //这样设置循环可以把end在数组中的每个位置都走一边但效率上没有变化int tmp arr[end gap];while (end 0) { //把当前tmp插入到合适的位置if (arr[end] tmp) {arr[end gap] arr[end];//每次都与前gap值为比较end - gap;}else {break;}}arr[end gap] tmp;}}
}希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书籍中给出的希尔排序的时间复杂度都不固定
《数据结构-用面相对象方法与C描述》— 殷人昆 不才上面使用的是Knuth提出的方式取值的而且Knuth进行了大量的试验统计暂时就按照O(n1.25)到O(1.6*n1.25)来算按照我们也可以粗略的归类与O(n * logn)的量级但是真实的时间复杂度是比O (n * logn)大。 三、选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 3.1、直接选择排序
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素
直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 3.2、堆排序 在堆的的逻辑结构中是严格遵循有序但这并不意味着整个堆的物理存储结构是有序的。堆排序的目的是对堆中的元素进行排序通过堆这种数据结构的特性来实现元素的排序。 排序中分为升序和降序堆排序即利用堆的思想来进行排序
排升序对应着建大堆排降序对应着建小堆
堆排序的方法
因为堆排序的逻辑与堆的删除逻辑是完全一致的都是先把堆顶元素与最后一个元素进行交换之后向下调整。与删除不同的是删除需要把数组中最后一个元素完全删除排序只需要不再理会数组最后一个元素不用真正删除元素。
排升序建大堆的原因在把堆顶元素与最后一个元素进行交换之后堆中的中最大的值被放置在物理结构的最右边如此循环即可完成结构的升序。降序同理 把堆中元素进行升序排序 我们使用上述大堆的例子创建有序的物理结构物理结构[9570821534691] 首先交换堆顶与最后一个元素(如下图) 在交换完成后逻辑结构上不再把95结点当作堆的结点之后进行向下调整(如下图) 此时物理结构为[7021895346195]。这样就把最大值放置在物理结构最右边并且忽略最后一个结点后其他结点依旧保持着大堆结构。(与删除堆顶逻辑完全相同)
循环上述操作可得下图 一定次数的循环后会得到下图 观察上图可以看到此时物理结构:[8631549217095]只要循环次数足够就可以把物理结构排为升序
最终可得下图 此时我们就完成了堆中元素的升序排序。物理结构为[1345689217095]。
3.2.1、堆排序的代码实现
void HeapSort(HPDataType* arr, int capacity, int farent) {assert(arr); // 确保传入的数组指针不为空int cp capacity; // 存储堆的初始容量// 当堆中还有元素时进行排序while (cp ! 0) {// 将堆顶元素最大或最小元素与当前堆的最后一个元素交换HeapSwap(arr, 0, cp - 1); // 减少堆的有效大小去除已排序的最大元素--cp;// 调整堆结构确保堆的性质依然保持AdjustDown(arr, cp, farent);}
}
首先把堆顶元素与最后一个叶子节点的元素进行交换。之后--元素个数把已经交换完成的最大值(最小值)忽略。完成后再向下调整。把交换完成后的顺序表重新调整为大堆(小堆)。
堆排序的特性总结
堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 ps剩下的两大排序真正紧张制作中欲知后事如何请听下回分解~~
以上就是本章所有内容。若有勘误请私信不才。万分感激 如果对大家有帮助的话就请多多为我点赞收藏吧~~~
ps:表情包来自网络侵删
