王道数据结构课代表

您所在的位置：网站首页 › 快速排序算法代码c语言是什么 › 王道数据结构课代表

王道数据结构课代表

2024-07-07 11:50| 来源: 网络整理| 查看: 265

本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！关于对第八章排序知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研数据结构 “排序” 章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。数据结构与算法笔记导航🚥🚥🚥

🥬 第一章绪论(无)🥕 第二章线性表🥪 第三章栈和队列🍊 第四章串-KMP(看毛片算法)🍒 第五章树和二叉树🍀 第六章图🍚 第七章查找(B树、散列表)🧄 第八章排序 (内部排序：八大排序动图演示与实现 + 外部排序) ⇦当前位置🪂🍔 数据结构与算法复试精简笔记 (未完成)🎨 408 全套初复试笔记汇总传送门 🏃‍🏃‍🏃‍

如果本篇文章对大家起到帮助的话，跪求各位帅哥美女们，求赞👍 、求收藏 👏、求关注！👀 你必考上研究生！我说的，耶稣来了也拦不住！😀😀😀

在这里插入图片描述

精准控时：如果不实际操作代码，只是粗略过一下知识点，需花费 70 分钟左右过一遍这个70分钟是我在后期冲刺复习多次尝试的时间，可以让我很好的在后期时间紧张的阶段下，合理分配复习时间；但是刚开始看这份博客的读者也许会因为知识点陌生、笔记结构不太了解，花费许多时间，这都是正常的。重点！！！学习一定要多总结多复习！重复、重复、再重复！！！

食用说明书：第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。所以再第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片对应的知识点以及自己的思考。最后第三遍，查漏补缺。所以，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

第8章排序

文章目录第8章排序8.1 排序的基本概念8.1.1 排序的定义8.1.1 排序的定义小结 8.2 插入排序8.2.1 直接插入排序1、算法思想2、算法效率分析3、优化 8.2.2 折半插入排序8.2.1 小结8.2.3 希尔排序1、算法思想2、具体实现3、算法性能 - 不适应于链表 8.3 交换排序8.3.1 冒泡排序1、算法思想2、算法实现3、拓展 - 适用链表 8.3.1 冒泡排序小结8.3.2 快速排序1、算法思想2、具体实现3、算法效率分析 8.3.2 快速排序小结 8.4 选择排序8.4.1 简单选择排序1、算法思想2、算法实现3、算法性能分析 - 好坏都O(n^2) 8.4.1 简单选择排序小结8.4.2 堆排序1、算法思想2、建立大根堆3、建立大根堆的具体代码4、基于大根堆的排序过程5、完整的堆排序代码6、算法效率分析 8.4.2 堆排序小结8.4.3 堆的插入与删除1、插入2、删除 8.4.3 堆的插入与删除小结 8.5 归并排序和基数排序8.5.1 归并排序1、算法思想2、代码实现3、算法效率分析 8.5.1 归并排序小结8.5.2 基数排序1、算法思想2、算法效率分析3、基数排序的应用 8.5.2 基数排序小结 8.7 外部排序8.7.1 外部排序的基本概念8.7.2 外部排序的方法8.7.2 外部排序小结8.7.3 败者树1、算法思想2、算法实现 8.7.3 败者树小结8.7.4 置换-选择排序（生成初始归并段）1、外部排序的局限性2、置换-选择排序（选择最小或最大元素置换出去） 8.7.4 置换-选择排序小结8.7.5 最佳归并树

8.1 排序的基本概念 8.1.1 排序的定义

在这里插入图片描述

算法稳定性：关键字相同的元素相对先后顺序

在这里插入图片描述

8.1.1 排序的定义小结在学习下面的各种排序方法之前，我想说的是，在你学习的过程中，你需要养成一种习惯，每学习一种排序方法，你需要注意那些关键指标呢？时间、空间复杂度（最好、最坏情况）稳定性比较次数、交换次数

在这里插入图片描述

8.2 插入排序 8.2.1 直接插入排序 1、算法思想

在这里插入图片描述

2、算法效率分析

在这里插入图片描述

// ! 直接插入排序 void InsertSort(int arrList[], int n) { int temp, i, j; for (i = 1; i < n; i++) // ! 有a[0]，下图代码是从a[1]开始的 { if (arrList[i] < arrList[i - 1]) { temp = arrList[i]; for (j = i - 1; j >= 0 && arrList[j] > temp; --j) { arrList[j + 1] = arrList[j]; } arrList[j + 1] = temp; } } }

在这里插入图片描述

3、优化

在这里插入图片描述

下面当mid60low==high时，为了保证算法的稳定性，折半查找还是要接着运行，下一步之后就会low 左、右为什么是n/2呢？因为大于（n/2）位置的结点，是叶子结点，不用管。只看分支节点

在这里插入图片描述

可能出现 “ 持续下坠 ” 的情况

在这里插入图片描述

3、建立大根堆的具体代码

在这里插入图片描述

4、基于大根堆的排序过程核心思想：每一趟循环都是在待排序元素中选取关键字最大的元素加入有序子序列对于大根堆来说，待排序元素中关键字最大的元素就是堆顶元素

在这里插入图片描述

在我解释下面大根堆的排序过程之前，我要先点名两个点

1、下图的数组表是真实的存储结构2、下图的大根堆是我们自己想的逻辑结构（两者要区分开）3、我们建立大根堆的结果，就是下图中的数组表，那个树形结构的大根堆只是便于我们理解

开始：

① 将堆顶元素和待排序序列中最后一个元素交换，也就是87和09交换。（看👆上面的图，下图👇是调整完毕的大根堆）

在数组表里，就只是arr[1]和arr[8]交换了元素在树形大根堆里，09跑到了树根，87去了09原来的位置。

完成①之后，所达到的效果：1、大根堆失效了，需要调整。2、找了待排序序列中最大的元素，加入了有序序列

② 调整大根堆，09不断下坠，78成为新堆顶。

HeadAdjust(int A[], int k, int len); // 此时len的值取8-1=7

在这里插入图片描述

③ 交换堆顶元素和“待排序序列”中最后一个元素，也就是78和53交换。④ 调整大根堆

在这里插入图片描述

大根堆得到递增序列小根堆得到递减序列

在这里插入图片描述

5、完整的堆排序代码 #include using namespace std; // ? 下面两个函数是用来建立大根堆的 // ! 将以 k 为根的子树调整为大根堆 void HeadAdjust(int arrList[], int k, int len) { arrList[0] = arrList[k]; // ! a[0]暂存子树的根结点 for (int i = 2 * k; i 0; i--) // ! 从后往前去调整所有非终端结点 { HeadAdjust(arrList, i, len); } } // ! 堆排序 void HeapSort(int arrList[], int len) { BuildMaxHeap(arrList, len); // 初始建堆 for (int i = len; i > 1; i--) // n-1趟的交换和建堆过程 { swap(arrList[i], arrList[1]); // 堆顶元素和堆底元素交换 HeadAdjust(arrList, 1, i - 1); // 把剩余的待排序元素整理成堆 } } int main() { int a[] = {0, 38, 49, 65, 97, 76, 13, 27, 49}; HeapSort(a, 8); cout

【本文地址】

公司简介

联系我们