内部排序
几个概念
关键字：“被排序对象”或者是“排序的依据”，由于关键字可能存在重复，所以还有“次关键字”
例如：成绩表排序，分数是关键词，当分数相同时，姓名首字母为次关键字
“稳定性”：关键字相同的存在，在排序后，相对位置不变，则称为稳定的排序方法
- 排序的内部与外部概念：
- 若所需排序数据都在内存中，则称之为“内部排序”，内部排序是排序的基础
- 若待排序记录数据量较大，排序时只有部分数据被调入内存，排序过程中存在多次内、外存之间的交换，这样的排序称为外部排序。
- 内部排序的分类
排序的基础——交换
交换排序
冒泡排序
一个被刻进DNA的算法
简单的问几个问题
①怎么确认冒泡排序的方向？
- 指针向哪个方向移动，每一轮就会在那边出现一个最值
- 根据冒泡过程中，每一次交换时，处于指针靠前位置的数据的相对大小，确定出现的是哪个最值
②冒牌排序的优化？
- 冒泡排序为什么要优化？
因为传统的冒泡排序外循环O(n-1),内循环O(n-i-1)不变。
在排序过程中，除非一开始序列是完全反向排序，否则冒泡排序应该会提前完成。
优化是为了去除多余的循环
- 冒泡排序怎么优化？
添加标志位（flag）：
只有同时i
若内循环没有交换任何一组数据，则认为flag=0；如果交换了任何一组数据，则flag变为1。
③冒泡排序的时间复杂度与稳定性
O(n)；稳定
快速排序
基本思想
快速排序的基本思想是:通过一趟排序，将序列中的数据分割为两部分，其中一部分的所有数值都比另一部分的小；然后按照此种方法，对两部分数据分别进行快速排序，直到参与排序的两部分都有序为止。
详细讲解
手搓代码
算法分析
以上的算法实现，其核心是一个 while循环，在该循环中实现下标的移动和数据的对比调整。 while循环完成之后，序列被选定的参考值划分为两个子序列，然后通过递归调用函数自身对子序列进行操作。在理想情况下每一次序列划分都划分出两个等长的序列，那么需要划分log2n次，此时快速排序的时间复杂度为O（nlog2n）；而最坏情况下，原始序列已经基本有序，每次划分只能减少一个元素，此时快速排序退化为冒泡排序，时间复杂度为O（n2）。因此快速排序的平均时间复杂度为O（nlog2n）。
相比于冒泡排序，快速排序的排序效率有了质的飞跃，并且快速排序在排序的过程中只需要常数级的辅助空间，空间复杂度仅为O（1）。当然使用递归算法时，每次递归调用需要开辟一定的空间，这个空间总大小为nog2n，所以快速排序的空间复杂度实际为O（nlog2n）。因为冒泡排序存在跳跃性的位置变换，所以关键字相同的两条记录在排序之后先后次序可能发生改变，这个算法是一个不稳定的排序算法。
分割线
插入排序
通用原理
插入排序（ insertion sort）可以视为两步操作，一步是插入，一步是排序。
插入排序的基本思想就是将一条记录插入到一组已经有序的序列中，继而得到一个有序的、数据个数加1
的新的序列。
直接插入排序（略）
折半插入排序
基本原理
折半插入排序（binary insertion sort）是对直接插入排序的改进。在直接插入排序中，主要的时间消耗在数据的比较和移动上。那么有没有方法降低数据比较的次数呢？由于前半部分的序列已经有序，在为新数据寻找插入点时，可以采用折半查找的方法来提高寻找速度。
手搓代码
算法分析
折半插入排序节省了排序过程中比较的次数但是移动的次数与直接插入排序相同，所以其时间复杂度仍为
O（n2）。分析算法可知，两个数据关键字相同时，不会交换数据顺序，所以该算法是一个稳定的算法。
希尔排序
基本原理
希尔排序（Shell sort）也是插入排序算法的一种，是直接插入排序更加高效的改进版本。
该算法由D.L. Shell于1959年提出。
无论是直接插入排序还是折半插入排序，都是将待排序序列视为一个分组。而希尔排序将原始序列按照下标的一定增量分为多个序列，在每个序列中执行直接插入排序。随着增量的减小，每组包含的数据越来越多，当增量减至1时，所有的分组重新整合为一个序列，此时排序结束。
手搓代码
算法分析
希尔排序的核心算法仍然为直接插入排序但是希尔排序比直接插入排序多设置了一个步长增量，从而有效地减少了每轮排序比较的次数和比较的轮数，明显降低了时间消耗。
希尔排序的性能分析比较复杂，它的时间复杂度与设置的增量有关，然而如何取其增量尚无定论。但是无论如何选择，最后一个增量必须为1.
按照上文中取增量的方法:d＝[d/2]，d＝[d/2]（i≥1），即后一个增量为前一个增量的1/2，经过t＝log2（n-1）次后，d＝1。
希尔排序的时间复杂度难以估算，通常认为是O（n）与前面介绍的插入排序算法相比，其时间性能的提升是可观的，希尔排序是真正在时间复杂度上有数量级缩减的算法。
另外，希尔排序是一个不稳定的算法。如果两个相同元素，被分在不同的组中，则可能出现相对顺序改变。
分割线
选择排序
通用原理
选择排序（selection sort）的基本思想是:从待排序的序列中选出最大值（或最小值），交换该元素与待排序序列头部元素，直到所有待排序的数据元素排序完毕为止。
简单选择排序（略）
基本思想
简单选择排序是最基础的一种选择排序，这种排序方法严格贴合选择排序基本思想。
与直接插入排序类似，简单选择排序也可以将序列视为两部分，只是直接插入排序初始的有序序列有一个元素，简单选择排序初始的整个序列都视为待排序序列，有序序列为空。
直接插入排序依次选择待排序序列中的元素，并将其插入有序序列的合适位置，而简单选择排序是依次为序列中的每个位置选择合适的元素。
算法分析
简单选择排序算法包含一个简单的双层循环，其时间复杂度为O（n）
该算法在进行排序的时候可能会改变两个键值相同的记录的先后次序，比如对于数据｛7，7，2｝，使其成为一个升序序列，第一个7在一轮选择排序之后会被换到第三个位置，两个7的先后次序就发生了变化。所以简单选择排序算法不是一个稳定的算法。
树形选择排序
原理
树形选择排序（tree selection sort）又称锦标赛排序（tournament sort），是一种按照锦标赛思想进行选择排序的方法。
锦标赛的比赛过程很简单:首先所有参加比赛的选手两两分组，每组产生一个胜利者；其次这些胜利者再两两分组进行比赛，每组产生一个胜利者；之后重复执行上一步骤，直到最后只有一个胜者产生为止。
更多细节
由于树形选择排序被后面的堆排序碾压，所以，不做过多细节要求
亚军只能从被冠军击败的人中选出。
堆排序
什么是堆？
实现堆排序的两个关键问题?
手搓代码
算法分析
下图是关于堆初始化的时间复杂度的分析，比较清楚明白
对于堆维护的复杂度，按照极限的思考，选择n次,每次选择都经历层数（log+1）次比较，所以复杂度：
O（nlog）
归并排序
算法思路
手搓代码
算法分析
基数排序
前置知识
从计数排序到桶排序
多关键字排序
第一种方法是首先对最高位关键字K进行排序，将原始序列分成若干个序列，每个序列都有相同的K值；其次对每个序列按照关键字K进行分组，使分出的更小的序列包含相同的关键字K；如此重复，直到对关键字Km-1进行排序之后得到的记录都有相同的关键字（K，K，…，K），然后对子序列K进行排序，最后将所有的子序列依次连接在一起，就得到了一个有序序列。这种方法称为最高位优先（ Most Significant Digit first）法，简称MSD法
第二种方法是首先对最低位关键字K进行排序，其次对次低关键字K进行排序，如此重复，直到对最高位关键字K1进行排序之后，原始序列成为一个有序序列。这种方法称为最低位优先（Least Significant Digit first）法，简称LSD法。
MSD和LSD只规定了按照某个关键字的某个顺序（从高到低或从低到高）来进行排序，而不要求对每个关键字进行排序时所用的方法。
根据以上叙述，使用MSD需要不断将序列逐层划分，然后对子序列进行排序，这个过程类似希尔排序中对序列的分组，所以这种方法是一种不稳定的排序方法；使用LSD法进行排序，不必划分子序列，每一次排序都是对完整的序列进行排序，这种方法要求排序过程中使用的排序算法必须是稳定的，即不能改变已排关键字的相对次序。使用这种算法可以不使用前几节中学习的以比较为基础的排序，而是利用分配式排序中的基本思想，通过多次的“分配”和“收集”来实现排序。
链式基数排序（字符串）
理论讲解
https://www.cnblogs.com/yimeixiaobai1314/p/7932254.html
https://www.cnblogs.com/aimmiao/p/9397464.html
通过上面的前置知识讲解，应该可以明白什么是链式基数排序。
手搓代码
外部排序
待补充
若有收获，就点个赞吧
0 人点赞
