第八章知识小结【数据结构】

目录

• 前言
• • 1. 直接插入排序
  • 2. 折半插入排序
  • 3. 希尔排序
  • 5、交换排序
  • 6、冒泡排序
  • 8、快速排序
  • 9、选择排序
  • • 简单选择排序
  • 10、归并排序

前言

第八章知识小结

1. 直接插入排序

若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况。

平均情况比较次数和移动次数约为n2/4

时间复杂度为 o(n2)，空间复杂度为 o(1)

是一种稳定的排序方法

适用于：基本有序，元素较少。

2. 折半插入排序

折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。

减少了比较次数，但没有减少移动次数

平均性能优于直接插入排序

时间复杂度为 o(n2)

空间复杂度为 o(1)

是一种稳定的排序方法

3. 希尔排序

基本思路：将整个待排记录序列分割成若干组，分别进行直接插入排序。

分组技巧：分组不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个组。让增量dk逐趟缩短，（例如依次取5,3,1），直到dk＝1为止。

优点：

（1）小元素跳跃式前移

（2）最后一趟增量为1时，序列已基本有序

（3）平均性能优于直接插入排序

时间复杂度是n和d的函数：

O(n1.25）～O（1.6n1.25）—经验公式 空间复杂度为 o(1)

5、交换排序

基本思想：两两比较，如果发生逆序则交换位置，直到所有记录都排好序为止。

6、冒泡排序

冒泡排序：两两比较，若逆序则交换，小数如气泡一样上浮（左移），大数如石块一样下沉（右移）。

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素； 一旦下趟没有交换，还可提前结束排序 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法

8、快速排序

(1)可以证明，最好情况下的时间复杂度为O(nlog2n) ,最坏情况下为O(n)，平均时间复杂度是O(nlog2n)。

(2)实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

(3)快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。

(4)最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n) 。

(5)稳定性： 不稳定—可选任一元素为支点。

9、选择排序

简单选择排序

移动次数：最好情况：0。最坏情况：3(n-1) 时间复杂度：O(n²)；空间复杂度：O(1)

稳定 堆排序 什么是堆？ 如何建立堆？（此处不做总结，看书） 时间效率：O(nlog2n) 空间效率：O（1） 稳 定 性：不稳定 适用于n 较大的情况 基本思想：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已经排好序的记录序列的后面。

10、归并排序

归并：将两个或两个以上的有序表组合成一个新有序表 时间效率：O(nlog2n) 空间效率：O（n) 稳 定 性：稳定

在这里插入图片描述