【学习总结】《大话数据结构》- 总

第9章排序-代码链接

启示：

• 排序

• 9.1 开场白
• 9.2 排序的基本概念与分类
• 9.3 冒泡排序
• 9.4 简单选择排序
• 9.5 直接插入排序
• 9.6 希尔排序
• 9.7 堆排序
• 9.8 归并排序
• 9.9 快速排序
• 9.10 总结回顾
• 9.11 结尾语

========================================

9.1 开场白

• 一些可以略过的场面话...

========================================

9.2 排序的基本概念与分类

• 排序的定义：

• 关键字：可以是主关键字、次关键字，甚至是若干数据项的组合

• 多个关键字的排序最终都可转化为单个关键字的排序

• 排序的稳定性

  • 定义

• 内排序和外排序

  • 定义

• 内排序的排序算法的性能的影响因素

  • 时间性能：排序核心操作--比较和移动。高效率的内排序算法--尽可能少的比较和移动。
  • 辅助空间：除了存放待排序所占用的存储空间外，执行算法所需的其他存储空间。
  • 算法的复杂性：不是时间复杂度，是算法本身的复杂性。算法过于复杂也会影响排序性能。

========================================

9.3 冒泡排序

• 思想：

  • 两两比较，逆序则交换，一轮比较过后把最大的值冒泡到最后一个。（正序时）

• 优化：

  • 避免在后面已经排好序的情况下仍然进行无意义的遍历，设置一个flag，可以提升一些性能。

• 复杂度：

  • 最好：O(n)
  • 最坏：O(n^2)
  • 平均：O(n^2)

========================================

9.4 简单选择排序

• 选择排序的基本思想：

  • 每一趟在n-i+1(i=1,..,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录

• 简单选择排序：

  • 通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。

• 步骤：

  • 外循环每次将当前外循环i定义为最小值下标min
  • 内循环遍历比较，如有小于当前arr[min]的，将其下标赋值给变量min
  • 内循环完成一轮遍历后进行判断，若min不等于i，说明找到不是i对应元素的最小值，进行交换即可

• 代码实现

• 复杂度

  • 特点：比较移动数据次数相当少，性能略优于冒泡
  • 时间复杂度：O(n^2)，比较多，最好最坏都是这样

========================================

9.5 直接插入排序

• 基本操作：

  • 将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表。
  • 思路1：记录待插入元素，然后角标遍历找到合适的空位，同时后移已排序序列中的元素使空出位置，最后确定角标变化时，将元素插入到空位
  • 思路2：先确定确实需要插入，即已排序序列的最大值大于待插入元素，然后进行比较，当大时，后移一位，最后把待插入元素插入到空位

• 代码实现

• 复杂度

  • 时间复杂度：O(n^2)
  • 最好：O(n)
  • 最坏：O(n^2)
  • 直接插入比冒泡和简单选择排序的性能要好一些

========================================

9.6 希尔排序

• 思想

  • 对直接插入排序改进后可以增加效率
  • 将原本有大量记录数的记录进行分组，分割成若干个子序列，然后在这些子序列内分别进行直接插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序
  • 基本有序：小的关键字基本在前，大的基本在后，不大不小基本在中间。
  • 采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

• 代码实现

• 复杂度

  • O(nlogn)
  • 不稳定

========================================

9.7 堆排序

========================================

9.8 归并排序

========================================

9.9 快速排序

========================================

9.10 总结回顾

========================================

9.11 结尾语

END