Quick Sort

用于Java中Arrays.sort(Primitive)

性质：

1. in-place, constant extra place的排序算法  
2. Depth of Recursion: logarithmic extra space with high probability  
3. Quick sort is not stable

优化 ：
size < k值的时候用insertion sort

重点题目：

1. Nuts & Bolts Problem
2. Median of Two Sorted Arrays

3. Decimal dominants

   Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected running time of your algorithm should be linear.

Quick Sort 要点

1. 选 Pivot 的位置：中间还是边上？要随机选取，不然造成O(N^2)的复杂度
2. 出现duplicate 的情况，不同的写法，如果不跳跃重复，会造成O(N^2)的复杂度

Take linear time on average, quadratic in worse case.

public int findKthLargest(int[] nums, int k) {
    return helper(nums, 0, nums.length - 1, k);
}

private int helper(int[] nums, int l, int r, int k) {
     int pos = partition(nums, l, r);        // 调用partition返回pivot的位置
     if (nums.length - pos == k) {           // 满足了Kth Large
         return nums[pos];
     } else if (nums.length - pos < k) {     // 这里不同于二分法，一定要弄清楚是哪边！
         return helper(nums, l, pos - 1, k);
     } else {                                // 画图：1,2,3,4,5 pos = 1 k = 2 (5 - 1 > 2),当前是第4大的，那么需要到右边找
         return helper(nums, pos + 1, r, k);
     }
}
// iterative:
public int findKthLargest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int pos = partition(nums, left, right);
        if (k - 1 == pos) return nums[pos];
        else if (k - 1 < pos) right = pos;
        else left = pos + 1;
    }
    return nums[left];
}

Partition

public int partition (int[] nums, int l, int r) {
  // pick random pivot
  int rand = l + (int)(Math.random() * ((r - l) + 1));
  int pivot = nums[rand];
  nums[rand] = nums[l];
  nums[l] = pivot;

  // 开始partition
  while (l < r) {
      while (l < r && nums[r] >= pivot) {   // 跳跃重复元素跳过，不然每次都挪动元素，造成复杂度上升
          r--;
      }
      nums[l] = nums[r];                    // nums[l] 是pivot, 可以覆盖，所以先找右边，然后覆盖左边的nums[left]
      while (l < r && nums[l] <= pivot) {
          l++;
      }
      nums[r] = nums[l];
  }
                                             // 返还 pivot 点到数组里面
  nums[l] = pivot;
  return l;
}

Hint2: there are two basic approaches.

Approach A: Compute the median in a[] and the median in b[]. Recur in a subproblem of roughly half the size.
Approach B: Design a constant-time algorithm to determine whether a[i] is the kth largest key. Use this subroutine and binary search.
Dealing with corner cases can be tricky._

Hint3: determine the(n/10)thlargest key using quickselect and check if it occurs more than n/10 times.

Alternate solution hint: use 9 counters.