1.归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

java代码：

  1. public class Code01_MergeSort {
  3.     public static void process(int[] arr, int L, int R){
  4.         if (L == R){
  5.             return;
  6.         }
  7.         int mid = L + ((R - L) >> 1);
  8.         process(arr, L, mid);
  9.         process(arr, mid+1, R);
  10.         merge(arr, L, mid, R);
  11.     }
  12.     public static void merge(int[] arr, int L, int M, int R){
  13.         int[] help = new int[R-L+1];
  14.         int i = 0;
  15.         int p1 = L;
  16.         int p2 = M + 1;
  17.         while (p1 <= M && p2 <= R){
  18.             help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
  19.         }
  20.         while (p1 <= M){
  21.             help[i++] = arr[p1++];
  22.         }
  23.         while (p2 <= R){
  24.             help[i++] = arr[p2++];
  25.         }
  26.         for(i = 0; i < help.length; i++){
  27.             arr[L+i] = help[i];
  28.         }
  29.     }
  30. }

JavaScript代码：

  1. function process(arr, L, R){
  2.     if(L == R){
  3.         return;
  4.     }
  5.     var mid = L + Math.floor((R-L)/2);
  6.     process(arr, L, mid);
  7.     process(arr, mid+1, R);
  8.     merge(arr, L, mid, R);
  9. }
  10. function merge(arr, L, M, R){
  11.     let help = [];
  12.     let i = 0;
  13.     let p1 = L;
  14.     let p2 = M+1;
  15.     while(p1 <= M && p2 <= R){
  16.         help[i++] = arr[p1] >= arr[p2] ? arr[p1++] : arr[p2++];
  17.     }
  18.     while(p1 <= M){
  19.         help[i++] = arr[p1++];
  20.     }
  21.     while(p2 <= R){
  22.         help[i++] = arr[p2++];
  23.     }
  24.     for(i = 0; i < help.length; i++){
  25.         arr[L+i] = help[i];
  26.     }
  27. }

1）整体就是一个简单递归，左边排好序、右边排好序、让其整齐有序
2）让其整体有序的过程里用了外排序方法
3）利用master公式来求解时间复杂度
4）归并排序的实质
时间复杂度O(N*logN),额外空间复杂度O(N)

2.快速排序

快排1、2版本时间复杂度都是O(N^2)， 快排3版本是O(N*logN)。

不改进的快速排序：

1） 把数组范围的最后一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：
左侧<划分值、中间==划分值、右侧>划分值
2) 把左侧范围和右侧范围，递归执行
分析：
1）划分值越靠近两侧，复杂度越高，划分值越靠近中间，复杂度越低
2）可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2);

随机快速排序

1）在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分：
左侧<划分值、中间==划分值、右侧>划分值
2) 对左侧范围和右侧范围、递归执行
3）时间复杂度为O(N*logN);

快排3版本代码：

  1. package class02;
  3. public class Code03_QuickSort {
  4.     public static void quickSort(int[] arr){
  5.         if(arr == null || arr.length < 2){
  6.             return;
  7.         }
  8.         quickSort(arr, 0, arr.length-1);
  9.     }
  11. //    arr[l...r]排好序
  12.     public static void quickSort(int[] arr, int L, int R){
  13.         if(L < R) {
  14.             swap(arr, L + (Math.random() * (R-L+1), R);
  15.             int[] p = partition(arr, L, R);
  16.             quickSort(arr, L, p[0]-1);
  17.             quickSort(arr, p[1]+1, R);
  18.         }
  19.     }
  21. //    这是一个处理arr[l...r]的函数
  22. //    默认以arr[r]做划分，arr[r] -> p <p --p >p
  23. //    返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[0]  res[1]
  24.     public static int[] partition(int[] arr, int L, int R){
  25.         int less = L - 1;
  26.         int more = R;
  27.         while(L < more){
  28.             if(arr[L] < arr[R]){
  29.                 swap(arr, ++less, L++);
  30.             } else if(arr[L] > arr[R]){
  31.                 swap(arr, --more, L);
  32.             } else{
  33.                 L++;
  34.             }    
  35.         }
  36.         swap(arr, more, R);
  37.         return new int[] {less+1, more };
  38.     }
  39.     public static void swap(int[] arr, int x, int y) {
  40.         int temp = arr[x];
  41.         arr[x] = arr[y];
  42.         arr[y] = temp;
  43.     }
  44. }

JavaScript代码：

  1. function quickSort(arr) {
  2.     if(arr === null || arr.length < 2){
  3.         return;
  4.     }
  5.     quickSortT(arr, 0, arr.length-1);
  6.     return arr;
  7. }
  8. function quickSortT(arr, L, R) {
  9.     if(L < R) {
  10.         swap(arr, L + Math.floor(Math.random() * (R-L+1)), R);
  11.         let p = partition(arr, L, R);
  12.         quickSortT(arr, L, p[0] -1);  // <区域
  13.         quickSortT(arr, p[1]+1, R);  //  >区域
  14.     }
  15. }
  17. function partition(arr, L, R) {
  18.     let less = L - 1;   // 区左边界
  19.     let more = R;              // 区右边界
  20.     while(L < more){        //表示当前数的位置      arr[R] -> 划分值
  21.       if(arr[L] < arr[R]){  // 当前数 < 划分值
  22.         swap(arr, ++less, L++);
  23.       } else if(arr[L] > arr[R]){  //  当前数   > 划分值
  24.         swap(arr, --more, L);
  25.       } else{
  26.         L++;
  27.       } 
  28.     }
  29.     swap(arr, more, R);
  30.     return [less+1, more];
  32. }
  34. function swap(arr, x, y) {
  35.     let temp = arr[x];
  36.     arr[x] = arr[y];
  37.     arr[y] = temp;
  38. }