-
算法思想：
根据序列中两个相邻数据的比较结果来对换这两个记录在序列中的位置，
交换排序的特点：将键值较大的记录向序列的尾部移动，键值较小的记录项序列的前部移动
-
时间复杂度 O(
$n^2$ ) -
空间复杂度O(1)
-
稳定性：稳定（因为是连续比较，相同键值的元素并不会交换位置，所以是稳定的）
-
时间复杂度是否与初始序列有关
完全正序：只需要遍历一遍，发现没有交换，就直接返回，所以时间复杂度为O(n)
完全逆序：每次都需要交换，所以时间复杂度为O(
$n^ 2$ )
-
算法思想：每次从待排序的数据中选出最小（最大）的一个数据，存放在序列的起始（末尾）位置，直到整个序列有序
优化，可以在一次查找中，同时找最大和最小两个元素，然后把它们放到合适的位置。
-
时间复杂度O(
$n^ 2$ ) -
空间复杂度O(1)
-
稳定性:不稳定
-
时间复杂度是否与初始序列有关：无关
（因为前面数据已经有序，优化为折半插入排序）
-
算法思想：
当插入第i（i>=1）个位置元素的时候，前面的array[0],...array[i-1]已经排好序，对i位置元素，寻找合适插入位置（可以考虑折半查找），找到合适位置之后，将元素后移，然后，插入array[i]
-
时间复杂度O(
$n^ 2$ ) ，如果是折半查找的话，查找合适位置的时间为O($lg i$ ),但是需要搬移元素，总体时间复杂度也是O($n^ 2$ ) -
空间复杂度O(1)
-
稳定性：是一种稳定的排序算法
-
时间复杂度是否与初始化序列有关
完全逆序的情况：O(
$n^ 2$ )完全正序的情况：O(n)
-
算法思想：
是对直接插入排序的优化，先选定一个整数gap，将待排序数据分成若干个组，所有距离为gap的数分在同一个组中，并对每一组的数据进行排序，然后取gap = gap/3 + 1，重复分组排序的过程，直到gap为1，所有数据有序。
-
时间复杂度O(
$n^ 2$ ) -
空间复杂度O(1)
-
稳定性: 不稳定
-
时间复杂度是否与初始序列有关
完全正序的情况：时间复杂度为O(n)
完全逆序的情况：时间复杂度为O(
$n^ 2$ )
-
算法思想：
取待排序元素中的某一元素作为基准值，将序列划分为两个子序列，左子序列中的所有元素都小于基准值，右子序列中的所有元素都大于基准值
然后对左右子序列重复该过程，直到所有元素都排列在相应位置上
-
时间复杂度：O(
$n lg n $ ) -
空间复杂度： O(
$lg n$ ) -
稳定性：不稳定
-
时间复杂度是否与初始化序列有关
如果完全逆序，而对快速排序没有什么优化，获取的基准值可能为极值，这样的话时间复杂度就变为O(
$n^ 2$ )如果完全正序，与完全逆序情况一样，时间复杂度也变为O(
$n^ 2$ )对快速排序，数据越不规则，效率越高
-
参考代码
-
算法思想：
是建立在归并操作上的一种有效的排序算法，将已经有序的子序列合并，得到完全有序的序列
先使每个子序列有序，在使子序列的段间有序，若将两个有序表合成一个有序表，称为二路归并，
核心步骤：先分解，再合并
-
时间复杂度：O(
$n lg n $ ) -
空间复杂度： O(n)(这样是归并排序的缺点)
-
稳定性：稳定
-
时间复杂度是否与初始化序列有关
无关
-
算法思想：
利用堆这种数据结构所设计的一种排序算法，是选择排序的一种，它是通过堆来进行选择数据
升序建大堆，降序建小堆
具体排序过程：建堆（将所有元素插入堆里）->将堆顶元素与最后一个元素交换，并让堆的大小减一 -> 然后调整堆-> 继续
-
时间复杂度O（$n lg n$）
-
空间复杂度O（1），因为堆是自己写的，堆只是一个算法，其实堆还是这个数组，并没有开辟额外空间，所以空间复杂度为O(1)
-
稳定性：不稳定
-
时间复杂度是否与初始化序列有关
无关，因为是把所有元素插入堆里，每次插入都会进行堆调整
-
算法思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。
-
具体做法：以LSD（Least Significant Digit first，最低位优先）为例，基数为10
a. 先统计这组序列中最大的数的位数（决定多少次循环）
b. 先根据个位的数值，在走访数值时将他们划分到0到9号桶中
c. 将桶中的数据回收，并再次按照十位进行划分
d. 直到处理完最高位，回收数据之后，这个序列就有序了
-
实现方法：
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
-
时间复杂度：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集
-
空间复杂度：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针
-
时间复杂度是否与初始化序列有关
无关
-
算法思想：鸽巢原理，是对哈希表直接定址法的变形运用
a. 统计相同元素的出现次数
b. 根据统计结果将序列回收到原来的序列中
在数据范围比较集中时，效率很高，但是使用范围及场景有限
-
时间复杂度O(max(n, 数据范围))
-
空间复杂度O(数据范围)
-
稳定性： 稳定
-
时间复杂度是否与初始化序列有关 无关
-
总结
如果数据量过大，超过最大的内存容量，那么一次性将所有数据读入内存，进行排序是不可行的。
例如，一个文件每一行存储一个整数，该文件大小为10GB，而内存大小只有512M，如何对这10GB的数据进行排序呢？
-
思路：
将超大文件分成若干部分，每一部分是可以读入内存的，例如，将10GB的文件分为40份，则每一份只有256M，将每一份读入内存，用快排，堆排等方式进行排序，在写到一个文件中。这样，我们得到了40个已经有序的小文件。
再采用归并的方式，将40个文件合并为一个大文件，则这个大文件就是我们要的结果
-
难点
-
归并的方式可以考虑二路或者四路归并
-
失败树
-
失败树的性质
失败树里的每个节点中所存的值是失败者的下标
-
-