归并排序

归并排序 Merge Sorted Array 左边排序，右边排序，左右两边合并 === 归并排序需要额外的空间用于合并(要倒腾出来，再倒腾回去)。
归并排序其本质是二叉树的后序遍历！即分治。

  1. // 思想：左边排序、右边排序，然后再合并
  2. public class 归并排序
  3. {
  4.     public static void mergeSort(int[] nums) {
  5.         if (nums == null) {
  6.             throw new RuntimeException("array is null");
  7.         }
  8.         mergeSortHelper(nums, 0, nums.length - 1);
  9.     }
  11.     // 思想：左边排序、右边排序，然后再合并
  12.     static void mergeSortHelper(int[] nums, int start, int end) {
  13.         if (start == end) {
  14.             return;
  15.         }
  16.         // Divide
  17.         int mid = start + (end - start) / 2;
  18.         mergeSortHelper(nums, start, mid);
  19.         mergeSortHelper(nums, mid + 1, end);
  21.         // Conquer
  22.         merge(nums, start, end, mid);
  23.     }
  25.     private static void merge(int[] nums, int start, int end, int mid)
  26.     {
  27.         int[] helper = new int[end - start + 1];
  28.         int p1 = start, p2 = mid + 1;
  29.         int index = 0;
  30.         while (p1 <= mid && p2 <= end) {
  31.             if (nums[p1] < nums[p2]) {
  32.                 helper[index++] = nums[p1++];
  33.             } else {
  34.                 helper[index++] = nums[p2++];
  35.             }
  36.         }
  37.         if (p1 <= mid) {
  38.             while (p1 <= mid) {
  39.                 helper[index++] = nums[p1++];
  40.             }
  41.         }
  42.         if (p2 <= end) {
  43.             while (p2 <= end) {
  44.                 helper[index++] = nums[p2++];
  45.             }
  46.         }
  47.         for (int i = end; i >= start; i--) {
  48.             nums[i] = helper[--index];
  49.         }
  50.     }
  52.     public static void main(String[] args)
  53.     {
  54.         int[] array = {1,5,7,2};
  55.         mergeSort(array);
  56.         for (int i : array)
  57.         {
  58.             System.out.println(i);
  59.         }
  60.     }
  61. }

快速排序

快速排序 ==任取一个数target，将数组分成两部分，左边的<= target, 右边的 > target。然后左右两边再quick sort.复杂的在最坏的情况下是o(n2) 平均复杂度O(nlgn).
快速排序的本质是前序遍历。

// 思想：一个数组，随机找一个数字target，并将其放到正确的位置上(左边的数<=target，右边的数>target)；然后左右两侧亦如此
public class 快速排序
{
    public static void quickSort(int[] nums) {
        if (nums == null) {
            throw new RuntimeException("array is null");
        }
        quickSortHelper(nums, 0, nums.length - 1);
    }
    // position是寻找到的随机数字
    static void quickSortHelper(int[] nums, int start, int end) {
        // 第一步：将index = position的值归还到正确位置
        Random random = new Random(end - start);
        int position = random.nextInt() + start;
        int target = nums[position];
        int p1 = start, p2 = end;
        while (p1 < p2) {
            while (nums[p1] <= target && p1 < p2) {
                p1++;
            }
            while (nums[p2] > target && p1 < p2) {
                p2--;
            }
            if (p1 < p2) {
                swap(nums, p1, p2);
            }
        }
        quickSortHelper(nums, start, p1 - 1);
        quickSortHelper(nums, p1 - 1, end);

    }

    private static void swap(int[] nums, int p1, int p2)
    {
        int temp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = temp;
    }
}

整体来说快拍优于归并排序，因为归并排序，需要额外的空间，然后将两个排序数组倒腾进去，然后再倒腾回去。。工程上常用快排
但是归并排序有个很好的地方，就是，其是稳定排序，而快拍不稳定。

LeetCode 915 分割数组(未完成)