排序算法详解
排序算法是算法理论的基础，可以说只有理解了排序算法，才能更加深入地理解其他更加复杂的算法。简单的排序的算法包括选择排序、插入排序、希尔排序，稍微复杂的排序有归并排序和快速排序、堆排序等。本文以循序渐进的方式讲解各种排序和它们之间的改进关系。主要是为自己的整理一下学习思路，同时也希望对同是算法初学者的读者有帮助。
三种简单排序
这里我把选择排序、插入排序和希尔排序成为简单的排序，它们之间具有循序的效率改进关系。有人可能会认为选择排序和插入排序的时间复杂度是一样的，怎么会是改进呢？实际上，插入排序的效率平均比选择排序快1倍，注意，这里指的是平均而言，并不是所有的情况都适用。而希尔排序的效率远远高于选择排序和插入排序，其复杂度目前仍未确定，可以肯定是其排序效率略低于归并排序、快速排序。
问题模型
为了使排序算法更加通用化，这里采用了范型和Comparable接口。
Comparable[] a是需要排序的一个数组，各元素实现了Comparable接口，可以通过compareTo方法比较大小。
定义比较和交换元素的通用方法如下：
public static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static boolean less(Comparable o1, Comparable o2){
return o1.compareTo(o2) < 0;
}
选择排序
选择排序算法是最简单的排序算法，其过程如下：
- 找到最小的元素，与数组中的第一个元素交换位置。
- 找到第i小的元素，与数组中的第i个元素交换位置。
- 直到全部元素都排序完成。
寻找最小元素并且将最小元素与第i个元素交换的代码：
Comparable min = a[i];
for(int j = i; j < N;j++){
if(less(a[j],a[i])){
exch(a,i,j);
}
}
增加外循环，i从0到N-1，得到整个选择排序算法：
public static void selectionSort(Comparable[] a){
for (int i = 0; i < a.length; i++){
int min = i;
for (int j = i; j < a.length; j++){
if (less(a[j],a[i])){
min = j;
}
}
exch(a,i,min);
}
}
选择排序，每个内层循环都会进行N-i次的元素比较，并且可以假设每次选定最小元素都要与第i个元素进行交换位置。可以得到其元素比较次数为：1+2+3+···+N-1=O(N^2/ 2)交换元素的次数为 N-1次。所以，选择排序的复杂度为 O( N^2 )
结论：选择排序需要交换元素的次数是所有排序算法中最少的。
插入排序
插入排序其实就是平时玩扑克牌时候我们最常用的排序算法。
insertion.png
看到这个扑克牌的大家应该马上就明白插入排序的算法了吧。
插入排序最核心的内容就是如何将一个元素插入到合适的位置中，这里可以采用比较的方法，将元素与左边相邻的元素对比，如果小于左边的元素，则交换位置，直到不小于左边相邻的元素或者最左边的元素为止。
实现代码如下：
for(int j = i; j>0 && less(a[j],a[j-1]);j--){
exch(a,j,j-1)
}
既然实现的对任意i位置的元素插入到合适的位置，接下来当然只要对整个数组中的元素进行遍历，为每个元素都找到合适的位置。
public static void insertionSort(Comparable[] a){
int N = a.length;
for (int i = 0; i < N; i++){
for (int j = i; j > 0 && less(a[j],a[j-1]); j--){
exch(a,j-1,j);
}
}
}
仔细分析以下插入排序，不难发现，对于每次插入排序，最多可能出现i-1次比较，且发生i-1次交换，所以，插入排序的最大比较数为（1+2+···+N-1），与交换元素的次数一样。平均的比较次数和交换次数为(i-1)/2
所以插入排序的时间复杂度为O( N^2 )
选择排序和插入排序的比较
sort.png
这是一个插入排序和选择排序的过程图，对于插入排序和选择排序，数组左边的元素都是已经排序好的，但是插入排序的元素位置并没有最终确认。对于选择排序，需要N-1次的比较，对于插入排序则需要的比较次数更少。如果使用改进的插入排序，则不需要每次都交换元素。目前看来，插入排序的效率大约是选择排序的2倍，效率相对较高。
Note：虽然接下去的其他排序算法的时间复杂度都远远低于插入排序，但是由于插入排序对于元素较少的数组可以实现较高的效率，使用较少的系统资源和递归，所以在元素不多的情况下，可以优先考虑插入排序，这也是接下去的几个排序算法在元素较少的情况下可以采用的一种算法效率优化。
希尔排序
Sorting_shellsort_anim.gif
希尔排序是插入排序的一种优化。插入排序在数组较大的情况下，元素的移动距离很远，需要较多的交换元素的次数。基于这个缺点，希尔排序采用了一种称为g有序的策略，也就是说，每相距g位置的元素是有序的，以此来实现插入排序。
g>h,如果某个数组是g有序的，那么经过h排序后，仍为g有序。
基于这个设想，我们只要每次降低排序的间距，即可实现整个数组的排序。
- 首先确定一个h，为最大的有序间隔
- 对数组进行h插入排序
- 减小h的数值，再次对数组进行h排序，直到h=1为止
这里不妨采用3h+1=N这个公式来做排序。
public static void shellSort(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3){
h = 3 * h + 1;
}
while (h > 1){
for (int i = 0; i < N; i++){
for (int j = i; j > 0 && less(a[j],a[j-h]); j = j -h){
exch(a,j-h,j);
}
}
h = h / 3;
}
}
希尔排序的时间复杂度是个至今没有定论的问题，对于不同的间隔递减策略，有不同的排序效率。我们只需要知道，希尔排序算法相对于归并排序、快速排序、堆排序而言效率稍微低一些，在实际的应用中，大约是归并排序的一半左右。
归并、快排和优先队列
前面讲解的三种排序算法都是比较基础简单的排序算法，特别是插入排序和选择排序，时间复杂度都较高，难以在较大规模的应用中采用。接下来的三种排序算法，都实现了复杂度为O(NlgN),这些排序算法的发明，使得大规模的排序开发成为了可能。
归并排序
归并排序可以说是分治算法的典范了。归并排序的精髓在于归并，如何将两个子数组归并是归并排序算法的核心。
Merge-sort-example-300px.gif
public static Comparable[] aux;
public static void merge(Comparable[] a, int lo, int mid, int hi){
int i = lo;
int j = mid+1;
for (int k = lo; k <= hi; k++){
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++){
if (i > mid){
a[k] = aux[j];
j++;
}else if (j > hi){
a[k] = aux[i];
i++;
} else if (less(aux[i],aux[j])){
a[k] = aux[i];
i++;
}else{
a[k] = aux[j];
j++;
}
}
}
归并排序需要一个额外的数组，这个辅助数组用于保存未归并的原数组，归并后的序列存储在原来的数组中。
对于归并排序，首先只需要将一个大的数组切分成2分，对其中的2个小数组分别进行mergeSort，然后归并mergeSort后的子数组即可。所以归并排序是一种递归的排序方法。
public static Comparable[] aux;
public static void mergeSort(Comparable[] a){
aux = new Comparable[a.length];
mergeSort(a,0,a.length-1);
}
public static void mergeSort(Comparable[] a, int lo, int hi){
if (hi < lo) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a,lo,mid);
mergeSort(a,mid + 1, hi);
merge(a,lo,mid,hi);
}
复杂度分析：每个长度为k的归并，都需要进行k次比较，而长度为N的数组，一共需要进行lgN次的归并操作，容易得到归并排序的时间复杂度为O(NlgN)
快速排序
Sorting_quicksort_anim.gif
快速排序可谓是归并排序的一个典型扩展。归并排序每次都是将较大的数组平均分为2份，而后进行归并操作。有没有一个办法，让两个子数组在排序之后不再需要归并操作？答案是，有。只要排序后的两个子数组中的一个数组中的元素小于另一个数组中的任意一个元素。快速排序的核心思想正是如此。
public void quickSort(Comparable[] a){
StdRandom.shuffle(a);
quickSort(a,0,a.length-1);
}
public void quickSort(Comparable[] a,int lo, int hi){
if (hi <= lo) return;
int j = partition(a,lo,hi);
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}
public int partition(Comparable[] a,int lo, int hi){
Comparable v = a[lo];
int i = lo,j=hi+1;
while (true){
while (less(a[++i],v)){
if (i==hi) break;
}
while (less(v,a[--j])){
if (j==lo) break;
}
if (i >= j) break;
exch(a,i,j);
}
exch(a,lo,j);
return j;
}
快排的时间复杂度为O(NlgN)
快排的应用：选择第k大的元素：
题目：给定一个数组，找出其中第k大的数。
分析一下，第一感是要进行排序，然后直接找到第k大的数即可。排序嘛，可以使用快排、归并排序，时间复杂度较低。但是有没有效率更高的算法呢？额，还真有...
这里给出一种基于快排的切分数组的方式的查找算法，实在是妙不可言！
public static void select(Comparable[] a, int k){
StdRandom.shuffle(a);
int lo = 0;
int hi = a.length-1;
while(lo < hi){
int j = partition(a,lo,hi);
if(j < k){
lo = j + 1;
}else if(j > k){
hi = j - 1;
}return{
a[j];
}
}
return a[k];
}
时间复杂度大致为 O(N)
优先队列
使用堆实现优先队列
堆有序：当一个二叉树的每个结点都大于等于他的两个子节点时，成为堆有序。
package elementalSort;
/**
* Created by hwzheng on 2016/12/15.
*/
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
public MaxPQ(int maxN){
pq = (Key[]) new Comparable[N];
}
public boolean isEmpty(){
return N==0;
}
public int size(){
return N;
}
public void insert(Key v){
pq[++N] = v;
swim(N);
}
public Key delMax(){
Key max = pq[1];
exch(1,N);
N--;
sink(1);
return max;
}
public void swim(int n){
while (less(n/2,n)){
exch(n/2,n);
n = n/2;
}
}
public void sink(int i){
while (2 * i <= N){
int j = 2 * i;
if (j < N && less(j, j+1)){
j++;
}
if (!less(i,j)){
break;
}
exch(i,j);
i = j;
}
}
public boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}
public void exch(int i, int j){
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
}
以上的堆排序算法只能针对固定容量的优先队列，如果需要可变容量的优先队列，可以在数组容量不足时将数组大小倍增，数组中元素为1/4容量时，将数组大小减半。
利用有序堆，可以对数组进行排序。
首先，将数据一个一个输入有序堆中，构建一个优先队列。
然后依次弹出最小元素，即可对数组元素进行排序。这也就是堆排序算法的基本思想。
