标签：排序 记录 复杂度 元素 关键字 序列 数据结构 408

数据结构 排序

分冶
稳定性 时间复杂度 空间复杂度

1.插入类排序

• 直接插入排序
• 折半插入排序
• 希尔排序 分组(间距d--)，直接插入排序

2.交换类排序

• 起泡排序
• 快速排序 每次选一个基准元素，将待排序的元素分成两个部分 （可以选第一个元素作为基准元素） 以每次的基准元素为根构建二叉树

3.选择类排序

• 简单选择排序 无序序列的最小值和无序序列的首元素交换
• 堆排序 采用顺序存储结构的完全二叉树进行层次遍历 小根堆、大根堆

4.归并排序
归并：将两个或两个以上的有序序列合并成一个有序序列，若才采用线性表易于实现，时间复杂度O(m+n)

• 二路归并排序
• 多路归并排序

性能分析：时间复杂度O(nlog2(n)) 空间复杂度O(n)

5.基数排序
桶排序或数字排序：按待排序记录的关键字的组成成分(或"位")进行排序。不需要进行关键字的比较和记录的移动。

• 多关键字排序 分配、收集
  • 最高位优先 Most Significant Digit first，MSD
  • 最低位优先 Least Significant Digit first，LSD
• 链式基数排序

基本策略

1. 插入类排序
   依次将无序序列中的一个记录按照关键字值的大小插入到已排好序的一个子序列的适当位置，直到所有的记录都插入为止。

2. 交换类排序
   对于待排序记录序列中的记录，两两比较记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。

3. 选择类排序
   不断第从待排序记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。

4. 归并排序
   利用"归并"技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。

5. 基数排序
   按待排序记录的关键字的组成成分("位")从低到高(或从高到低)进行排序。每次是按记录关键字某一"位"的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。

---

直接插入排序

元素越有序，直接插入排序的速度越快

空间复杂度 O(1)
平均时间复杂度 O(n^2)

折半插入排序

平均时间复杂度 O(n^2) 仅减少了关键字的比较次数

希尔排序

缩小增量法，一种分组插入排序方法

起泡排序 冒泡排序

算法思想：依次比较相邻两个记录的关键字，若两个记录是反序的(前一个记录的关键字大于后一个记录的关键字)，则进行交换，直到没有反序的记录为止。

空间复杂度 O(1)
平均时间复杂度 O(n^2)

快速排序

基本思想：通过一趟排序，将待排序记录分割成独立的两部分。其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，从而达到整个序列有序。
即，每次都选一个基准元素，通过对这个基准元素将待排序的元素分成两个部分。 一般选择每段的第一个元素作为基准元素。

如果以每次的基准元素为根，可以构建一棵二叉树。
快排的"趟"：根据二叉树的树形结构，每层元素均调整完毕
快排排序的趟数 等于 所构建的二叉树的高度

元素越无序，快排的性能越好；T(n)= O(nlog2(n)) S(n)= O(log2(n))
元素越有序，快排的性能越差。T(n)= O(n^2) S(n)= O(n)

简单选择排序

直接选择排序，每次都从无序序列中选择最小的元素和无序序列的首元素交换

空间复杂度 O(1)
时间复杂度 O(n^2)

堆排序

采用完全二叉树结构进行排序的方法

• 小根堆
  根结点的值小于左子树的值，并且根结点的值小于右子树的值
• 大根堆
  根结点的值大于左子树的值，并且根结点的值大于右子树的值

堆的序列就是完全二叉树的层次遍历

堆的性质（完全二叉树的性质均具有）

• 堆是一棵采用顺序存储结构的完全二叉树，k1是根结点。
• 堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆。
• 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)排列的。

堆排序思想：
利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序。

排序过程中，若采用小根堆，排序后为非递减序列；
排序过程中，若采用大根堆，排序后为非递增序列；

1.创建完全二叉树，调整顺序：从最后一个元素开始。 "从下到上，从右往左"
2.排序：将堆顶元素和最后一个记录交换位置，堆顶元素输入
3.输出堆顶元素后，用堆中最后一个额元素替代，按照1中调整方法调整

T(n)= O(nlogn)
S(n)= O(1)

堆排序特别适用于从n个元素中获取前k个。

根据给定的关键字序列的顺序输入步骤：
1.构造一棵完全二叉树
2.画出整理好的一棵堆树
3.画出一棵输出一个排序记录后的二叉树
4.画出重新调整好的堆树

归并排序

排序思想：
1.初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列。
2.对所有有序子序列进行两两归并，得到[n/2, 向上取整]个长度为2或1的有序子序列， 即一趟归并。
3.重复2，直到得到长度为n的有序序列为止。
二路归并排序：子序列总是两两归并

最坏情况下比较的总次数达到最小：
例子6个有序表，需要5次两两归并，故可设总比较次数为X-5,X就是以n个叶子结点表示升序表，以升序表的表长表示结点权重，构造的二叉树的带权路径长度。 求X最小，利用哈夫曼树思想。

基数排序

桶排序或数字排序：按待排序记录的关键字的组成成分(或"位")进行排序。不需要进行关键字的比较和记录的移动。

• 多关键字排序 分配、收集
  • 最高位优先 Most Significant Digit first，MSD
  • 最低位优先 Least Significant Digit first，LSD
• 链式基数排序

算法分析:
设有n个待排序的记录，关键字位数为d，每位有r种取值，则排序的趟数是d。
在每趟中：
1.链表初始化的时间复杂度为O(r)
2.分配的时间复杂度为O(n)
3.分配后收集的时间复杂度为O(r)，则链式基数排序的时间复杂度为O（d*(n+r)）
在排序过程中使用的辅助空间是2r个链表指针，n个指针域空间，则空间复杂度为O(n+r).

排序比较

1. 不稳定的：快希选堆（快些选队）
2. 时间复杂度O(nlogn):快归堆（快归队）
3. 空间复杂度：归并是O(n); 快排是O(logn)
4. 基数排序单独记忆：时间是O(d*(n+rd)) 空间是O(rd).

特殊情形总结：

1. 每趟排序无法确定元素最终位置的是 插入类排序、归并类排序、基数类排序。 每趟排序均确定一个元素位置的是交换类、选择类。
2. 一般需要采用顺序结构存储的算法是归并排序、堆排序、快速排序，其他算法可以采用顺序结构和链式结构。
3. 算法的时间复杂度和元素的初始状态无关的是基数排序和简单选择排序。
4. 算法的比较次数和元素的初始状态无关的是基数排序和简单选择排序。
5. 排序趟数和元素的初始状态 有关的是快速排序； 无关的是直接插入排序(n-1)、折半插入排序(n-1)、希尔排序、简单选择排序(n-1)、堆排序(n-1)、归并排序（log2(n)）。

标签：排序,记录,复杂度,元素,关键字,序列,数据结构,408
From： https://www.cnblogs.com/yongchao/p/17156814.html