稳定性：任意两个相等的数据，排序前后的相对位置不会发生改变。满足这一条的排序称他为稳定的。
没有一种排序是任何情况下都表现最好的。也就是说一种算法能被写进教科书一定有他的理由。
选择排序
public void run(int[] args){ int length = args.length; //每次检索最小的放到最左边，放好后再检索剩下没排好的 for (int i = 0 , k = 0 ; i < length ; i ++ , k = i){ for (int j = k +1 ; j < length ; j++){ if ( args[j] < args[k]) k = j; //k用来指向当此循环中最小那个 } if ( k != i) Utils.swap(args, i, k); } }
冒泡排序
public void run(int[] args){ boolean finishSort = false; int len = args.length; for (int i = len ; i > 0 ; i--){ //用i指示内循环中的上限，因为每一次内循环都能将一个最大的数放好位置 finishSort = true; //所以每次可以少遍历一个数 i-- for (int j = 0 ; j < i-1 ; j ++){ //一轮冒泡把最大的放到最右边，然后对剩下没排好的继续冒泡 if ( args[j] > args[j+1]){ Utils.swap(args, j+1, j); finishSort = false; } } if (finishSort) break; //避免中途已经排序完成还继续做无畏循环 } }
最好情况：一开始就是有序的，那么内循环循环一次即可，时间复杂度T=O(N)，最坏情况是逆序，那么就要将两个循环全部走完，T=O(N2)
好处是相当简单，两个for循环就搞定了，但是一个O(N2)的算法是不可接受的。但是他有一个好处，如果数据是按链表来存的，那么冒泡依然可行，因为他只是交换相邻的元素，不管是数组还是链表都没有问题，但是其他算法就不是这样了。还有一个好处，那就是这里是判断>就交换，那么=的话是不会交换的，也就是说这个算法是稳定的！
插入排序
public class InsertSort implements Sort{ public void run(int[] args){ int len = args.length; for (int i = 1 ; i < len ; i++){ //从下标1开始 for (int j = i ; j > 0 && args[j] < args[j-1] ; j--) //保证循环后i前面的数都是有序的 Utils.swap(args, j, j-1); //交换相邻 } } }
还有一种写法，不是用交换相邻元素，感觉这个更像插入排序一点！这个应该算正宗的插入排序:)
package sort; public class InsertSort implements Sort{ public void run(int[] args){ int len = args.length; int j ; for (int i = 1 ; i < len ; i++){ int tmp = args[i]; for ( j = i ; j > 0 && args[j-1] > tmp ; j-- ) args[j] = args[j-1]; //腾出空位，找到新元素要插入的位置 args[j] = tmp; } } }
最好情况：跟冒泡一样，也是一开始就是顺序的，遍历一遍元素就可以完成。T=O(N)
最坏情况：逆序，T=O(N2)
有点：非常简单，还有就是比起冒泡，可以省掉交换函数的那三条语句，算起来还是可以省很多步骤的
插入排序也是在前面的元素比新元素大的时候才移位的，如果相等则不会移动，所以插入排序也是稳定的
考虑一个问题
34，8，64，51，32，21 这几个数字分别进行插入和冒泡的元素交换次数是多少？
答案是都是9次…………那这是个巧合麽？
对于下标i < j ，如果 A[i] > A[j] ，那么称（i ， j）是一对逆序对(INVERSION)
再数数上面的数列有多少个逆序对？会发现有9个，这两个9是一个巧合麽？不是！因为交换一次相邻元素刚好消去一个逆序对！
因为无论如何，都要从头到尾扫描一遍，所以至少是一个O(N)复杂度，另外，他操作的次数是跟他逆序对的个数成正比的，所以可以说T(N,I) = O(N+I) 由此可见，如果这个I非常小，跟N是一个数量级的，甚至比N还要小，换言之，这个序列是基本有序的！则插入排序简单且高效
定理：任意N个不同元素组成的逆序对平均具有N(N-1)/4个逆序对
也就是说不管是插入排序还是冒泡排序，他们的平均时间复杂度都是跟逆序对的个数有关的，由此可以推出下面的定理
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度是Ω(N2)。Ω代表的是时间复杂度的下界，也就是说，你最好也就是N2时间复杂度了，那换句话说，如果想要提高算法的效率，我们必须做到：
- 每次消去不止一个逆序对。（如果至少交换相邻两元素是做不到这一点的，所以还必须……）
- 每次交换相隔较远的两个元素。（期望在一次排序中同时消去多个逆序对）
希尔排序
Donald Shell提出来的。利用了插入排序的简单，同时呢要克服每次只能交换相邻两个元素的缺点。基本步骤如下
- 定义增量序列DM>DM-1>...>D1=1
这个增量序列是随你怎么定的，比如5，3，1，但是最后一个一定要是1
- 对每一个增量Dk进行Dk间隔的排序
注意：Dk间隔有序的序列，在执行Dk-1间隔排序后，仍然是Dk间隔有序的。也就是说，每一次排序都没有把上一次的排序结果弄坏……
最重要的一点是，希尔排序的增量序列的选取很关键，如果选的不好，可能比前面的几趟排序都不能产生效果，最后还是得靠增量1来排序。这里选取序列1/2（3k-1)
package sort; public class ShellSort implements Sort { @Override public void run(int[] args) { int len = args.length; int h = 1; while ( h < len) h = 3*h + 1; int j; while ( h >= 1){ //将数组变成h有序，增量为h的插入排序 for ( int i = h ; i < len ; i++){ int tmp = args[i]; for ( j = i ; j-h >= 0 && args[j-h] > tmp ; j-=h) args[j] = args[j-h]; args[j] = tmp; } h /= 3; } } }
注意：虽然插入排序是稳定的，但是希尔排序不是稳定的，这个还是容易理解的
归并排序
自顶向下的归并
public class MergeSort implements Sort { //递归实现 int[] tmp; public void run(int[] a){ tmp = new int[a.length]; //一次性分配数组 sort( a , 0 , a.length -1 ); } void sort(int[] a , int lo , int hi){ if (hi <= lo) return; int mid = lo + (hi - lo)/2; sort(a , lo , mid); //将左半边排序 sort(a , mid+1 , hi); //将右半边排序 merge(a , lo , mid , hi); //归并结果 } void merge(int[] a , int lo , int mid , int hi){ for ( int k = 0 ; k <= hi ; k++) tmp[k] = a[k]; //复制数组 int i = lo , j = mid+1; // i扫描左半边的元素 j扫描右半边的元素 for ( int k = lo ; k <= hi ; k++){ if ( i > mid ) a[k] = tmp[j++]; else if ( j > hi ) a[k] = tmp[i++]; else if ( tmp[i] < tmp[j] ) a[k] = tmp[i++]; else a[k] = tmp[j++]; } } }
递归便于了解，但是实际上操作得时候递归并不是那么美妙的，下面提供一种非递归的方法实现，也叫自底向上的归并排序
void sortBU( int[] a){ //非递归 int length = a.length; for ( int size = 1 ; size < length ; size = 2*size) //size为每次要归并的子数组的大小，2个、4个、8个…… for ( int lo = 0 ; lo < length-size ; lo = lo + 2*size) //lo为子数组的索引 merge(a , lo , lo+size-1 , Math.min(lo+2*size-1, length-1)); }
归并排序有一个好处是它是稳定的，平均时间复杂度是nlogn，最坏时间复杂度也是nlogn，千好万好有一点不好的是，它需要一个额外的空间，它需要在数组和数组之间来回的捣腾复制元素，所以实际应用中基本不用归并排序做内排序，就是说如果我们所有的元素都可以在内存里面完成，没用会用归并排序做这件事，但是它在外排序的时候是非常有用的
非递归实现比较适合用链表组织数据，想象一下将链表先按大小为1的子链表进行排序，然后是2，然后是4，这种方法只需要重新组织链表链接就能将链表原地排序，不需要创建任何新的链表结点。
快速排序
传说中现实应用中最快的一种排序算法，但是它也不是在任何情况下都是最好的，我们总能构造出一种它的最坏情况，但是对于大规模的随机数据，快速排序的表现还是相当出色的。跟归并排序有相似之处，都是属于分治思想
有两个关键的地方：1.选主元。2.根据主元分成两个独立的子集
快速排序的最好情况：每次选的主元都恰好在数组的中间 T(N) = O(NlogN)
- 选主元
1.令pivot = a[0]?
有一种情况，如果一开始就是有序的，根据这种选法的话，子集划分的时候就会发现左边的是空集，然后要遍历右边所有的元素，然后开始递归
T(N) = O(N) + T(N-1)=O(N) + O(N-1) + T(N-2)=...=O(N2)
2.随机选主元？随机函数不便宜啊
3.取头中尾的中位数
例如8 ， 12 ， 3 的中位数就是8
当然还有很多选主元的方法
public class QuickSort implements Sort{ public void run(int[] a){ sort(a , 0 , a.length-1); } public void sort(int[] a , int lo , int hi ){ if ( hi <= lo) return; int j = partition(lo , hi , a); sort(a , lo , j-1); sort(a , j+1 , hi); } public int partition(int lo , int hi , int[] a){ int v = a[lo]; //选第一个数作为主元 int i = lo , j = hi+1; while (true){ while (a[++i] < v) if ( i == hi) break; //遇到一个大于v的数就停下来 while (a[--j] > v ) if ( j == lo) break; //遇到一个小于v的数就停下来 if ( i >= j) break; Utils.swap(a , i , j); //交换这两个数 } Utils.swap(a, lo, j); return j; } }
快速排序的问题？
1.用递归，会占用大量的堆栈空间，要push很多次，然后还要pop很多次。对于小规模数据，比如N<100可能还不如插入排序来的快，所以大规模数据我们才采用递归，小规模的就不用这个了
由此可以对快速排序做一个优化，在递归的时候判断一下数组的大小，当比较小的时候就停止递归，直接用简单排序，比如插入排序，要修改也很简单，比如这样
// if ( hi <= lo) return; if ( hi <= lo +5) { new InsertSort().run(a); return; }