内部排序要求数据元素全部在内存完成排序,且顺序存储。
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
有一个n位数的数据。
1.比较相邻的两个元素，若选取的两个相邻元素中，原来靠左侧的元素>原来靠右侧的元素，则交换两数位置。
2.需要进行n-1轮交换，每轮交换进行n-1次比较（换or不换位置）
※解释：eg.原始数据： 6 2 8 5 1第一轮： 2 6 5 1 |8第二轮： 2 5 1 |6 8第三轮： 2 1 |5 6 8第四轮： 1 |2 5 6 8
第一轮：6 2 8 5 1（原始）2 6 8 5 1（第1-2位：6 2交换）2 6 8 5 1（第2-3位：6 8不交换）2 6 5 8 1（第3-4位：8 5交换）2 6 5 1 8（第4-5位：8 1交换）
第二轮：2 6 5 1 8（第一轮原始）2 6 5 1 8（第1-2位：2 6不交换）2 5 6 1 8（第2-3位：6 5交换）2 5 1 6 8（第3-4位：6 1交换）
2 5 1 6 8（第4-5位：6 8不交换）*
第三轮：2 5 1 6 8（第二轮原始）2 5 1 6 8（第1-2位：2 5不交换）2 1 5 6 8（第2-3位：1 5交换）
2 1 5 6 8（第3-4位：5 6不交换）*
2 1 5 6 8（第4-5位：6 8不交换）*
第四轮：2 1 5 6 8（第三轮原始）1 2 5 6 8（第1-2位：2 1交换）
1 2 5 6 8（第2-3位：2 5不交换）*
1 2 5 6 8（第3-4位：5 6不交换）*
1 2 5 6 8（第4-5位：6 8不交换）*
比较了5-1=4轮，排序结束。
特别适用于：小规模数据 / 基本有序
有一个n位数的数据。从左边第2位开始，将该选取出的数字与左边每一位进行比较（习惯是从近往远比，比如我选的是第3位，我先用第3位与第2位比，再用这个*原来选取的第3位与第1位比），如果选取的数比左侧的比较数要小，则交换两个数字。
*：特别注意是原来选取的第3位，因为比较后数据可能发生交换。选了哪个数字，就用这个数字比较，直到比完该数原来左侧的所有位数。
※解释：eg.原始数据： 6| 2 8 5 1第一轮： 2 6| 8 5 1第二轮： 2 6 8| 5 1第三轮： 2 5 6 8| 1第四轮： 1 2 5 6 8|
*习惯是选一个数，然后与左边的每一位比较。（所以一开始选的是第2位，因为第1位左边没有数字了）
第一轮：6 2 8 5 1（原始，选第2位的2）←不管选出来的这个2移动到哪一位，都要用其与它左边的数对比，直到比较结束。（下面几轮同理，固定的是一开始选出来的数，而不是选出来的位）2 6 8 5 1（2 6交换）
第二轮：2 6 8 5 1（第一轮原始，选第3位的8）2 6 8 5 1（8 6不交换）2 6 8 5 1（8 2不交换）
第三轮：2 6 8 5 1（第二轮原始，选第4位的5）2 6 5 8 1（5 8交换）2 5 6 8 1（5 6交换）2 5 6 8 1（5 2不交换）
第四轮：2 5 6 8 1（第三轮原始，选第5位的1）2 5 6 1 8（1 8交换）2 5 1 6 8（1 6交换）2 1 5 6 8（1 5交换）1 2 5 6 8（1 2交换）
实质：对插入排序的改进，对大规模 / 无序的数据也非常有效率
（原因：相比冒泡排序和插入排序这样的简单排序，希尔排序一次交换可以消去的逆序对不止一对）
eg1.
首先以5为间隔，对数字进行排序：
（蓝色框）81 35 41→35 41 81
（……其余同理），数字的交换只是交换在这三个位置中的数字，位置本身是不变的
同理，再依次以3为间隔、以1为间隔进行交换（要注意的是：间隔数是要依次减小的，增大间隔数起不到排序的效果）
eg2.最坏的情况：
在上图这种情况下，以8/4/2为间隔都起不到交换的效果（因为在这些间隔上的数已经有序了），只有以1位间隔时才能真正地交换、排序（此时效率低下，还不如直接使用插入排序）
原因：间隔数不互质（8/4/2都有公因子）
改进：采用互质的增量序列
简述步骤：
一开始，在所有数字中取出一个最小元（因为一开始整个序列都是未排序的），然后将这个最小元放到最左边，作为已排序部分
之后，重复以下步骤：
在剩余的未排序序列中找出最小元，
然后将这个最小元放到左边有序部分的最后位置（“放到最后位置”这个动作实质上是：将有序部分的后一个位置上的数字 与 这个最小元 进行交换）
优点：简单直观的排序算法、不占用额外的内存空间
特点：
排序时，将数字分为两组：已经排好序的和未排序的
已经排好序的数不动，每次都用未排序组的第一个数字a与后面的数字对比，如果找到一个比数字a更小的数b，则与a与b在一轮对比结束后交换位置
实质：对选择排序的改进（因为利用最小堆，可以快速找出最小元）
堆的存储实现：一维数组
堆是基于完全二叉树的
堆的概念：
可以用完全二叉树简化对堆的判断。
建堆过程：（筛选法）
1、将待排序的数组随意地组成一个堆形（例如：一开始有一个一维数组，就可以直接依次按数组下标递增的顺序，构建一个完全二叉树）
2、排序（筛选）
沿堆形自下向上，自右向左依次进行筛选（对堆中的各个元素位置进行调整）
调整原则（以大顶堆为例）：
（注意：在调整堆中元素位置时，要注意一定是 根节点 与 子节点中最大结点 进行交换！
并不是依照“自右向左”的原则——将靠右的子节点与需要调整的根节点进行交换！）
eg.
上图是堆排序的构造初始序列的过程。
当构造出初始序列后，要将这个大根堆的根节点取出来，放在所有数字的序列最后不动，然后这个根节点将不再加入到后续的堆中，参与排序。（假设一共有10个数需要排序，则一共需要建10次堆，每次堆的结点个数递减：10,9,8...）
然后，再将这个初始序列的二叉树的最后一个叶子结点，作为新的堆的根节点
接着，重复上述操作，直到这个堆只剩下唯一一个元素，就排好序了。
对堆排序的讲解：（讲得不错）
参考：
eg.
第一次：
选关键字第一个数34作为r[0]
第二次：初始序列见图中第一行
此时34排到了中间，需要将34两侧的数分别再进行快速排序（25,23,20,32 / 58,89,45,56,50 ）
此时两组的r[0]分别为25和58
第三次：初始序列键图中第二行
此时除了25,34，58，其他的数字都还未排序
则逐个分组进行快排，得到最后的结果
（分组为：20,23 / 32 / 50,56,45 / 89）
其中，分组中只有一个数字的相当于不需要排序
有n位数，就要进行n次分组收集
（1）基数排序的过程
eg1：
eg2：
解题思路：
进行首趟排序时，先按个位数由小到大，分组收集
每个组内的数字顺序按上一轮的序列顺序进行排列（如果是第一趟则按开始的序列，之后第n趟则按n-1趟得到的序列进行排序）
（2）效率分析
（一种基于分治、合并的排序；相比倾向于基于分治的快速排序，归并排序更倾向于简单地进行“分”，重在“合”的过程）
（以二路归并为例：）
步骤：
1、两两分组，进行排序（若总元素个数为奇数时，在两两分组后，会出现一个元素落单的情况，这种情况是允许的，但是它只能放在所有分组的尾部，单独成组）
2、将排好序的各组中，依次两两组合，再排序，形成一个新的更长的有序组
3、重复以上过程，直到所有元素排序完成
性能分析：
优点：归并排序的最大好处是在数据呈现最坏情况时，是所有排序算法中表现最好的。（？）
缺点：需要外部辅助空间
因此，归并排序常用于外部排序。（当所要排序的的数据量太多或者文件太大，无法直接在内存里排序，而需要依赖外部设备时，就会使用到外部排序。）