【★★★★★ 第8章 排序 2022 9.10】

排序

排序的定义：D={D0,D1,D2….Dn-1} 包含n个元素，Ki为关键字，对数据D进行排序。实质是找一个元素下标，排列满足Kp0<=Kp1<=Kp2 递增递减的有序过程。
排序的概念： 给定数据元素根据指定数据项排列成一个有序序列的过程。

一、内排序

比较次数至少为log2(n!)
内排序：一次性读入内存完成排序。

内排序的考察

1. 稳定性：待排序数据中两个排序关键字相同的元素，Di=Dj(ki=kj)，排序前Di在前，排序后Di仍然在Dj前，则称这个排序算法是稳定的，反之，则不稳定。
   判断稳定：不能只从一次排序结果中得出结论，要从具体操作中的出。
   判断不稳定：只需要找到一个不稳定的排序结果即可。
   稳定性是一种特性，不是评价算法好坏的指标。
   要求次序重要：就选择稳定的算法。
   若次序不重要：不用特别考虑其稳定性。

2. 排序算法的趟数
   内排序的核心：循环执行一组运算，无序->部分有序->完全有序。不断重复的操作，称为一趟排序过程。
   算法的趟数不能用于评估算法的好坏，但可以用于算法的时间与空间复杂度分析。

3. 时空复杂度
   对每一趟排序过程中：①关键字比较次数，②数据元素移动次数，③临时存储空间大小，可分析时空！分为最好，最坏，平均。

插入排序：适用于基本有序和数据量不大的

1. 直接插入排序 [稳定] 适用于顺序存储和链式存储

2. 折半插入排序 [稳定] O(n方) 与初始状态无关

3. 希尔排序[不稳定] O(n)

交换排序：排序趟数与初始状态有关的只有交换排序

1. 冒泡排序[稳定] 大的往后

2. 快速排序 [不稳定] 空间平均,最好O(log2n) ,最差O（n）递归形式下

选择排序：

1. 堆排序[不稳定] 空间复杂度为O(1)

核心思想：借助堆数据结构，不断输出当前堆顶元素，每次堆顶离开堆后，将剩余元素调整为新的堆，直到堆剩下一个元素；元素的输出序列可以转化为元素的有序序列。
定义满足：
①L[i]>=L[2i]&& L[i]>=L[2i+1] 为大根堆
②L[i]<=L[2i]&& L[i]<=L[2i+1] 为小根堆
堆排序过程： 对n个元素，最后一个结点一定为n/2的孩子，①对n/2个结点为根的子树筛选，若左右孩子大于根，则交换较大的孩子，一次对n/2-1，n/2-2….做满足大根堆定义，若发现交换完成后发现部分破坏了大根堆的定义，则进行上述方法调整。
存储结构：顺序结构
逻辑结构：完全二叉树

堆排序构造过程：

堆的插入或删除

2. 简单选择排序 [不稳定]

与初始序列无关，总是要找最小元素，本身有序无序交换

其他：

两路合并排序算法[稳定]

基数排序：基数排序不基于比较

不能对double 和float类型的实数排序

二、外排序

外排序：待排数据量大，必须分多次读入内存进行排序。