Day13-【软考】长文！什么是散列表查找？以及所有的排序算法是怎样的？如何进行堆排序（重点！）？

文章目录

• 什么是散列表查找？
• • 计算出空间相同怎么办？
  • 排序有哪些概念？
• 排序方法有哪些分类？
• • 什么是直接插入排序？（稳定）
  • 什么是希尔排序？
  • 什么是冒泡排序？（稳定）
  • 什么是快速排序？O（nlog2为底 n为真数）
  • 什么是简单选择/直接选择排序？
  • 什么是堆排序（重点！）？O（nlog2为底 n为真数）
  • • 比简单的选择排序，有什么优势？
    • 如何建堆？
    • 取走堆顶元素后，如何重新调整堆（关键！）？
    • 堆排序最适合什么场景？
  • 什么是归并排序？（稳定）（n个辅助空间）O（nlog2为底 n为真数）
  • 什么是基数排序？（稳定）
• 排序算法的时间复杂度/空间复杂度/稳定性是怎样的（重点！）？

什么是散列表查找？

是一个全新的查找方式，

• 和按内容存储类似，具体在哪里，后面再找找…

就是在存储的时候，就想好一定的规则，存到一定的空间中去

那么制定什么样的规则就很重要，不同的规则不同的计算

查找数据时，无需查表，根据规则进行计算即可

key，就是关键码是多少

h就是最终存储的空间

计算出空间相同怎么办？

比如3，和8，和5模运算，值都是3

两种方式处理

线性探测法

就是3号被占，就顺次往下存即可

伪随机数法

暂未介绍

总之，散列表设计的关键，是减少这种冲突，这样效率才会更高

整体空间大一些，冲突的概率也会低一些

排序有哪些概念？

排序是必考的，有时下午也会考

稳定排序和不稳定排序

• 稳定排序，就是经过排序算法处理之后，黑色21仍然在红色21之前

比如总分一样的场景，遇到的这种情况相当之多，但是也会有个先来后到，它背后的含义不太一样，顺序就不能随意变化

• 不稳定排序，则是反之

内排序和外排序

内排序，是内存中的排序

外排序，会涉及外部存储空间

排序方法有哪些分类？

• 直接插入排序，操作简单容易
• 效率不如希尔排序高
• 冒泡排序，是基础算法
• 快速排序，效率会更高，过程复杂些
• 简单选择排序，考程序算法没什么好考的，太简单了
• 堆排序的效率是非常高的，建堆过程的有些操作，和之前操作排序二叉树有点类似；删除节点时，要确保仍然是一个堆的形态
• 归并和基数排序，考察相对少一些

什么是直接插入排序？（稳定）

插入元素时，从高到低依次找，找到了就插入

排序过程：

1. 比较前面两个元素，前面的小，就无变化，得到一个有序序列；如果前面的大，就交换即可
2. 第三个元素，插入这个序列，从高到低依次找，找到了第三个元素刚好大于这个关键字的，就插入这个关键字前面
3. 第四个元素同理

什么是希尔排序？

属于直接插入排序的一种，但是操作复杂一些

1、首先d1是5，就是各5个数，形成一个组，每个组只有两个元素，组内进行直接插入排序，因为只有两个元素，所以特别简单，要么不动，要么交换

• 这第1个5是怎么来的？

  就是总元素个数/2，这里n=10

2、d2，变成3了，也就是间隔变小了，每个组有四个元素了，28,24,96,72，进行直接插入排序，这时候也不太简单吧，24交换，72交换，先这样走

3、d3，变成1了，都是同一个组了，再直接插入排序，要交换几次，19,28,交换，后面的52交换还不行，最后还有个57，这样也很复杂呀

说好处是元素的挪动次数大大减少了，也就是一次次地接近更有序

虽然说19，确实到最后，只需要交换一次了，但是这个57就比较可惜，从最开头，挪到了倒数第二个，交换次数也差不了太多

什么是冒泡排序？（稳定）

相邻元素比较，较小元素组件从底部移动到顶部

1. 先把数组的最后两个元素对比，后一个小，交换
2. 继续把52和前一个对比，52小，继续交换
3. 继续和前一个比，小，交换，到这里52定位完成
4. 再从最后一个树开始，循环几轮，逐一定位

什么是快速排序？O（nlog2为底 n为真数）

采用分治法，就是把大问题分解为若干小问题，小问题运用递归的方式来进行

1. 假设，先定第一个元素为基准，基准在头部，尾部还有一个指针，指向最末端的元素，最末端元素和基准对比，末端元素小，交换；

2. 指针指向第二个元素，就当成是第二位的元素，还是和基准比较，基准比它小，交换；

3. 指针又到了倒数第二位，跳来跳去的好复杂…，倒数第二位小，交换；

4. 总之，大于基准的，都往后交换，小于基准的，都往前交换

5. 若干轮之后，前面的都小于基准，后面的都大于基准

6. 前后两个小序列还要再分别进行排序，这也太复杂了…这分治法不太行，一点也不高效

什么是简单选择/直接选择排序？

1. 先选出最小的52，和第一个57交换
2. 剩下的选最小，再交换
3. 剩下的再选，无需交换了，排序完成

• 那为啥要一遍遍交换呢，意思就把大的数往后丢呗，每次选最小的往前一个个排不是更明了

什么是堆排序（重点！）？O（nlog2为底 n为真数）

堆的结构，和完全二叉树结构相同，见，Day12-【软考】广义表如何取出表元素？二叉树如何遍历（重点！）？，中：完全二叉树，除了最后一层，上面的都是满的，并且最后一层的左边，都是满的，按照顺序排满了的

k2i，实际上就是ki的左子树节点

k2i+1，就是右子树节点

所有的孩子节点，都小于根结点，就是大顶堆；注意，并且每一个局部的小树，都是这样，都遵循这样的规律！

反之，是小顶堆，根节点比任何其他节点都要小

比简单的选择排序，有什么优势？

就是这种结构选择最小元素会更高效

如何建堆？

按照完全二叉树的方式来建

1. 将数组顺次，从第上到下，每一层从左到右，填入元素，形成完全二叉树结构
2. 从最后一个非非非叶子节点开始（重要的字说三遍），1,3,4,5是非叶子结点，最后一个就是5
3. 如果建设大顶堆，看5是否大于两个孩子，大则不变，但是目前小，把最大的孩子和根结点交换
4. 倒数第二个非叶子节点4，开始调，同样最大孩子交换
5. 倒数第三个非叶子节点3，调整，最大孩子交换，变成8,3，但是此时3的小堆，又不符合了，得变成5，3，这就是倒数第三幅图
6. 倒数第四个非叶子节点1，调整，最大孩子交换，变成8，1，同样小堆要调，变成7,1，到这里调整完毕，也有点复杂，特别是涉及小堆的调整

取走堆顶元素后，如何重新调整堆（关键！）？

1. 顶取走之后，完全二叉树的最后一个节点，放到根的位置

2. 把目前的根，和两个孩子对比，交换成60,20

3. 再比较，交换成50,20

4. 再比较，交换成40,20，完成重建，感觉也很复杂呀…

   这是从本身稀烂的无序中，硬制定规则，编造规律，而规则本身就很复杂

5. 以上是第一个数取走了，那么新的堆，继续取走，此时又是20变成根，循环一轮，最终所有的数按照顺序取走了…

堆排序最适合什么场景？

就是N多元素中，无需对所有元素进行排序，只要排出前10，就只求一部分极值，这样用这个结构就最合适

因为它每一轮选出一个，并且是所谓很高效地选出一个

什么是归并排序？（稳定）（n个辅助空间）O（nlog2为底 n为真数）

为了操作简单，通常都是两两归并，也叫做二路合并

1. 8个元素排序，相邻的两两分组，前两组归并，后两组归并；
2. 比较57,52，小的52复制到一个小组R中，放在第一个位置k上，k+1，就是下一个位置，i+1，就是指向下一个元素，比较57和59
3. 再把57复制到k+1中，指标说又指向68，遇到题目再说好了…

• 第2步，为何是比较57和59了，不是i加了1，j又没动

  不过从道理来说，也确实是应该从57接着开始比

说对有序表进行合并，要比对无序表合并，比较的次数少很多

当问题扩大时，所消耗的时间，不是线性增长，而是几何级数去增长！所以一定要把问题分解得更小！

什么是基数排序？（稳定）

考得很少

先排个位，再排十位，再排百位

1. 135，个位是5，放到第5位
2. 242,192，都是2,192链接在242下面
3. 把个位排序的结果，进行十位排序，11，排第1位
4. 242，排第4位
5. 把十位排序结果，进行百位排序，11，排第0位，剩下的该链接起来的，都链接起来
6. 最终得到从小到大的结果，就是通过挂链接，来进行排序的！

排序算法的时间复杂度/空间复杂度/稳定性是怎样的（重点！）？

同样的关键字，会不会改变顺序， 这就是稳定性

红21和黑21，排序之后，颠倒了位置，就是破坏了稳定性，这就不就是稳定排序的概念

除了选择的之外，越简单的就越稳定呗

辅助空间，绝大部分，都只需要1个，或者说自然个数，只需要1个；注意归并排序，需要n个空间，不合算

时间复杂度，以O（n的2次方）为主，

其次就是O（nlog2为底 n为真数）的情况，基本都是涉及二分，涉及树的，就会出现这种

这归并排序，三个都沾…