1. 整体介绍
分类
排序大的分类可以分为两种，内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。主要需要理解的都是内排序算法：
内排序可以分为以下几类：
(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
(2)、选择排序：简单选择排序、堆排序。
(3)、交换排序：冒泡排序、快速排序。
(4)、归并排序
(5)、基数排序
性能对比
稳定性：就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即如果A i == A j，A i 原来在 A j 位置前，排序后 A i 仍然是在 A j 位置前。
不稳定：简单选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法
稳定：冒泡排序、直接插入排序、二分法插入排序，归并排序和基数排序都是稳定的排序算法。
时间复杂度：一个算法执行所耗费的时间。
O(nlogn):快速排序，归并排序，希尔排序，堆排序。
O(n^2):直接插入排序，简单选择排序，冒泡排序。
O(n): 桶、箱、基数排序
快速排序是目前基于比较的内部排序中最好的方法， 其次是归并和希尔，堆排序在数据量很大时效果明显。当数据是随机分布时快速排序的平均时间最短。
空间复杂度：运行完一个程序所需内存的大小。
解释：n: 数据规模；k:“桶”的个数；In-place: 占用常数内存，不占用额外内存；Out-place: 占用额外内存。
排序方法的选择
1.数据规模很小（插入、简单选择、冒泡）
（1）数据基本有序的情况下，可选直接插入排序；
（2）数据无序时，对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
2.数据规模一般（快速排序、归并排序）
（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
3.数据规模很大（归并、桶）
（1）对稳定性有求，则可考虑归并排序。
（2）对稳定性没要求，宜用堆排序
4.待排序列初始基本有序（正序），宜用直接插入，冒泡
2. 插入排序（Insertion Sort）
基本思想：依次遍历元素，在已排序的序列中找到合适的位置将当前遍历的元素插入，直到所有元素都已排序。
方法：直接插入排序、二分插入排序、希尔排序2.1 直接插入排序
算法思想：
- <1>.从第一个元素开始，该元素可以认为已经被排序；
- <2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；
- <3>.如果该元素（已排序）大于新元素，将该已排序元素移到下一位置；
- <4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- <5>.将新元素插入到该位置后；
- <6>.重复步骤2~5。
时间复杂度：平均情况下：O(n2)
最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)
最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n2)
稳定性：稳定。由算法思想易知，反向遍历已排序元素，若已排序元素小于等于当前元素，则将当前元素插入该已排序元素后的位置，因此相对顺序不变，插入排序是稳定的。
Java实现：
public int[] insertSort(int[] arr){
//从前向后遍历待排序列
for (int i = 1; i < arr.length; i++) {
//当前正在遍历的元素值
int key = arr[i];
//从后向前扫描已排序序列，依次与当前元素对比
int j = i - 1;
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
return arr;
}
2.2 二分排序（折半插入排序）
二分法查找基本思想：对于一个有序的待查序列，定义三个指针low、high、mid，分别指向待查序列所在范围的下界、上界及区间中间位置，即mid=（low+high）/2。对比待查数据与mid所指的值，若相等则查找成功并返回mid，若待查数小于mid值，则令high=mid-1，否则令low=mid+1，得到新的需要查找的区间，如此循环直到找出或找不到。如下示例：
二分排序：从第二个数开始往后遍历，用二分法查找合适的插入位置。当low<high条件不成立时说明找到合适位置，将low及之后元素后移
时间复杂度：二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)。
稳定性：稳定。
Java实现：
public int[] binaryInsertSort(int[] arr) {
int low, high, mid;
int key;
for (int i = 1; i < arr.length; i++) {
key = arr[i];
low = 0;
high = i - 1;
//执行二分查找，注意符号（<、<=...）
while(low <= high){
mid = (low + high)/2;
if (key < arr[mid]){
high = mid -1;
}else {
low = mid + 1;
}
}
//二分查找终止，说明找到合适的位置low
//将low位置及之后的所有元素右移一位，再将当前遍历元素插入到low处
for (int j = i - 1; j >= low; j--) {
arr[j+1] = arr[j];
}
arr[low] = key;
}
return arr;
}
2.3 希尔排序（Shell Sort）
基本思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,这样可以把表的全部记录分成d1个组：所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。
时间复杂度： 平均情况下：O(N*logN)
最好情况：由于希尔排序的好坏和步长d的选择（di到di+1的选择策略）有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。
最坏情况：O(N*logN)，最坏的情况下和平均情况下差不多。
稳定性：由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同趟的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(有个猜测，方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。)
Java实现：
public int[] shellSort(int[] arr) {
//分组
int d = arr.length/2; //初始增量
while(d > 0){
for (int i = d; i < arr.length; i++) { //i是当前等待插入的元素的本来位置
int key = arr[i];
int j = i - d; //j用来循环，i位置之前待比较的元素序列
while(j >= 0 && arr[j] > arr[i]){ //待插入元素小了
arr[j+d] = arr[j]; //比待插入元素大的都往后移，类似于直接插入排序，但是增量由1改为d
j = j - d; //比较已排序序列的前一位置元素
}
arr[j+d] = key; //跳出循环说明找到当前a[j]<待排元素，将待排元素插入到j后的一个位置
}
d = d / 2; //步长算法，可以优化
}
return arr;
}
解释：就是将增量（d）为1的直接插入排序，增量改为从d到1的递减。不再是相邻元素间的对比，而是以d为间隔的对比插入。
3. 交换排序
3.1 冒泡排序（Bubble Sort）
基本思想：通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。
时间复杂度：平均O(n2)
最好情况：正序有序，则只需要比较n次。故，为O(n)
最坏情况: 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N2)
稳定性:稳定。排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以相对位置并没有改变，冒泡排序算法是稳定的！
算法描述：
- <1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- <2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- <3>.针对所有的元素重复以上的步骤，除了最后一个；
- <4>.重复步骤1~3，直到排序完成。
Java实现：
public int[] bubbleSort(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j]>arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}
return arr;
}
/**
* 交换两个数
*/
public void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
冒泡排序改进1：设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。因为上一轮冒泡的最后一次交换说明该交换的元素是其位置以前的所有元素中最大的(毕竟是自己冒上来的)。下一趟找最大元素的冒泡从该位置开始即可，不必从头开始两两交换
Java实现：
public int[] bubbleSort2(int[] arr){
for (int i = arr.length - 1; i >= 0; i--) {
int pos = 0; //每趟开始，无交换记录
for (int j = 0; j < i; j++) {
if (arr[j]>arr[j+1]) {
swap(arr[j], arr[j+1]);
pos = j; //记录交换位置
}
i = pos; //从上轮交换最后一次交换的位置开始两两对比
}
}
return arr;
}
3.2 快速排序（Quick Sort）
基本思想：由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位)。
核心思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
时间复杂度：O(N*logN)
最好的情况：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)
最坏的情况：基本有序时，退化为冒泡排序，几乎要比较N*N次，故为O(N*N)
稳定性：不稳定。由于每次都需要和中轴元素（不一定相邻）交换，因此原来的顺序就可能被打乱。快速排序是不稳定的。
算法描述：
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- <1>.从数列中挑出一个元素，称为 "基准"（pivot）；
- <2>.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- <3>.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
Java实现：
public int[] quickSort(int[] arr,int low,int high){
int i = low;
int j = high;
// if ((arr == null) || (arr.length == 0)){
// return null;
// }
while (i < j) { //查找基准点下标
while (i < j && arr[i] <= arr[j]) // 以数组start下标的数据为key，右侧扫描
j--;
swap(arr[i], arr[j]); // 从右往左扫描，找出第一个比key小的，交换位置
while (i < j && arr[i] < arr[j]) // 从左往右扫描（此时a[j]中存储着key值）
i++;
swap(arr[i], arr[j]); // 找出第一个比key大的，交换位置
}
if (i - low > 1) { // 递归调用，把key前面的完成排序
quickSort(arr, 0, i - 1);
}
if (high - j > 1) {
quickSort(arr, j + 1, high); // 递归调用，把key后面的完成排序
}
return arr;
}
4. 选择排序
4.1 简单选择排序（Selection Sort）
基本思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。
时间复杂度：平均情况下：O(N2)
最好情况：交换0次，但是每次都要找到最小的元素，因此大约必须遍历N*N次，因此为O(N*N)。减少了交换次数！
最坏情况：平均情况下：O(N*N)
稳定性：不稳定。 由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！
算法描述：n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。
- <1>.初始状态：无序区为R[1..n]，有序区为空；
- <2>.第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- <3>.n-1趟结束，数组有序化了。
Java实现：
public int[] selectionSort(int[] arr) {
int minIndex;
int temp;
//一趟找出一个最小值
for (int i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < arr.length ; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//将找到的最小值放到已排序序列的末尾
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
4.2 堆排序（Heap Sort）
基本思想：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。
时间复杂度：O(nlogn)。最坏情况下，接近于最差情况下：O(N*logN)，因此它是一种效果不错的排序算法。
稳定性：不稳定。需要不断地调整堆。
算法描述：
- <1>.将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
- <2>.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]；
- <3>.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
Java实现:
5. 归并排序
基本思想：多次将两个或两个以上的有序表合并成一个新的有序表。
时间复杂度：O(nlogn)
最好情况：一趟归并需要n次，总共需要logN次，因此为O(N*logN)
最坏情况：接近于平均情况下，为O(N*logN)
稳定性：归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。
缺点：它需要O(n)的额外空间。但是很适合于多链表排序。
6. 基数排序
基本思想：它是一种非比较排序。它是根据位的高低进行排序的，也就是先按个位排序，然后依据十位排序……以此类推。示例如下：
时间复杂度：分配需要O(n),收集为O(r),其中r为分配后链表的个数，以r=10为例，则有0～9这样10个链表来将原来的序列分类。而d，也就是位数(如最大的数是1234，位数是4，则d=4)，即"分配-收集"的趟数。因此时间复杂度为O(d*(n+r))
稳定性：稳定。
适用情况：如果有一个序列，知道数的范围(比如1～1000)，用快速排序或者堆排序，需要O(N*logN)，但是如果采用基数排序，则可以达到O(4*(n+10))=O(n)的时间复杂度。算是这种情况下排序最快的！！
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
参考链接：
http://www.cnblogs.com/jztan/p/5878630.html
http://blog.chinaunix.net/uid-25906157-id-3318529.html
http://www.cnblogs.com/leeplogs/p/5863846.html