Java基础：排序算法总结
By arthur503 -- 13 Oct 2013
笔试被笔了好多次，所以总结一下。包括：
* 哪些排序算法与初始顺序无关； * 排序算法的时间复杂度和空间复杂度，包括最优、最差、平均； * 排序算法的原理； * 稳定性； * 代码实现；
归并排序效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
快速排序平均效率O（nlogn），适用于排序大列表。 此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。
基数排序又被称为桶排序。基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
百度百科上排序算法的介绍中，有对排序算法的一个总结：
在计算机科学所使用的排序算法通常被分类为： (a)计算的复杂度（最差、平均、和最好性能），依据列表(list)的大小(n)。 一般而言，好的性能是O\left(n\log_2n\right)，且坏的性能是O\left(n^2\right)。对于一个排序理想的性能是O\left(n\right)。 而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O\left(n\log_2n\right)。 (b)存储器使用量（空间复杂度）（以及其他电脑资源的使用） (c)稳定度：稳定的排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。 (d)一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序和快速排序。插入排序包含希尔排序，选择排序包括堆排序等。
还有一个算法列表：【最后总结完了删掉！】
简介
在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。 稳定的
冒泡排序（bubble sort） — O(n^2） 鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2） 插入排序（insertion sort）— O(n^2) 桶排序（bucket sort）— O(n); 需要 O(k) 额外空间 计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间 合并排序（merge sort）— O(nlog n); 需要 O(n) 额外空间 原地合并排序— O(n^2) 二叉排序树排序 （Binary tree sort） — O(nlog n)期望时间； O(n^2)最坏时间； 需要 O(n) 额外空间 鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间 基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间 Gnome 排序— O(n^2) 图书馆排序— O(nlog n) with high probability，需要 （1+ε)n额外空间 不稳定的
选择排序（selection sort）— O(n^2) 希尔排序（shell sort）— O(nlog n) 如果使用最佳的现在版本 组合排序— O(nlog n) 堆排序（heapsort）— O(nlog n) 平滑排序— O(nlog n) 快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况； 对于大的、乱数列表一般相信是最快的已知排序 Introsort— O(nlog n)
Patience sorting— O(nlog n+ k) 最坏情况时间，需要 额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing > subsequence）
不实用的排序算法
Bogo排序— O(n× n!) 期望时间，无穷的最坏情况。 Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器 珠排序（Bead sort） — O(n) or O（√n)，但需要特别的硬件 Pancake sorting— O(n)，但需要特别的硬件 stooge sort——O（n^2.7）很漂亮但是很耗时
先介绍一下“稳定性”的概念：
一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
下面逐一对排序算法进行分析。每个算法包括：原理、稳定性、复杂度分析（包括时间复杂度和空间复杂度）。还有与初始顺序是否相关。
注：所有的排序算法都是以进行升序排序为例。
一、插入排序（insertion sort）
1. 原理
插入排序的原理是先建立一个空列表，用来保存排序后的有序数列。每次从原数列取一个数，将其“插入”到新的“有序列表”中，使新列表保持有序状态。重复，直至原数列为空。
插入排序的思想很直观、简单，容易实现。它占用了额外的空间来保存有序数列，对每个数字都进行插入判断，时间复杂度是平方级的，效率不高。
2. 稳定性
插入排序是稳定的。排序后的数列中，数值相同的关键字排序后顺序保持不变。
3. 复杂度分析
插入排序与初始顺序有关。若要建立升序排列，则初始顺序为降序排列时速度最快（每次都在第一次比较后插入），为O(n)；初始顺序也为升序排列时速度最慢（每次均要比较到队列末尾），为O(n^2)。因此，插入排序的时间复杂度最优为O(n)，最差为O(n^2)，平均为O(n^2)。【平均的对吗？】
插入排序需要建立一个新的数列，大小与原数列相同，因此，空间复杂度是O(n)。
* 实现难度
容易。
二、冒泡排序
原理
冒泡排序是对相邻元素的比较。每一次比较，若后者较大则不变，否则二者交换。这样，经过n-1轮的比较，每一轮都将数列中最大的值放到最后（每一轮的比较次数也逐次递减），最终完成升序排列。
稳定性
冒泡排序是稳定的，排序结果与初始顺序有关。
冒泡排序的排序时间与初始顺序无关，由于每一轮的比较次数是固定的，因此，最终的排序时间复杂度是固定的O(n^2)。
冒泡排序只有进行数据交换位置时需要额外空间（如果对空间要求严格，数据交换也可以不需要额外空间，进行两次异或比较即可实现交换），空间复杂度是O(1)。
三、选择排序
原理
选择排序也是对数组进行遍历，对每一次遍历（如第i次），都寻找当前所有元素中最小的元素，与第i位元素进行交换；再进行下一次遍历，直至所有元素排序完成。
稳定性
选择排序是稳定的，排序结果与初始顺序有关。
选择排序的排序时间和初始顺序是无关的，每一次遍历都需要和所有的元素进行对比，因此，时间复杂度是固定的O(n^2)。
选择排序不需要额外空间存放数列，因此空间复杂度是O(1)。
难度
容易。
四、快速排序
现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而”保证列表的前半部分都小于后半部分”就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
【百度百科上有快排的动态图，下载下来】
快排采用了分治的思想（可以利用递归的方法实现）：首先保证列表的前半部分都小于后半部分，然后对前半部分和后半部分均进行排序（同样采用快排）。
快排是所有排序算法中最高效的一种，它的高效原因是：“保证列表的前半部分都小于后半部分”后，前半部分的任何一个数都不必要再跟后半部分的数进行比较了，可以大大减少数字之间的不必要的比较次数。
那么，快排的思路这么简单，在具体实现上，就要考虑如何保证列表的前半部分都小于后半部分？