总结了几个跟Partition相关的题目，发现对Partition的结果要求有着小小的不同，就导致Partition过程中细节略有不同。
譬如:

  1. Quick Sort
    要求:
    • a[low..i-1] <= pivot <= a[i..high]
  2. Partition Array
    要求:
    • a[low..i-1] < pivot <= a[i..high]
    • pivot可以不存在于a数组中
  3. Kth Largest Element in an Array
    要求:
    • a[low..i-1] < pivot == a[i] <= a[i+1..high]
    • pivot一定存在
    • 且至少有一个跟pivot相同的值在a[i]

综合以上，想找到一个满足所有要求的Partition函数

  1. a[low..i-1 ] < pivot <= a[i..high]
  2. 如果pivot存在，且a[i]为pivot

所以总结成以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int partition(int[] a, int lo, int hi, int pivot) {
    int i = lo, j = hi + 1;
    int idx = -1;
    while (i < j) {
        if (a[i++] >= pivot) {
            swap(a, --i, --j);
            if (j + 1 <= hi && a[j + 1] == pivot) {
                idx = j + 1;
            }
        }
    }
    if(idx != -1 && j <= hi)
        swap(a, i, idx);
    // with a[lo..i-1] < pivot <= a[i..hi].
    // if there is a[x] == pivot,
    // at least one of the value is in a[i]
    return i;
}
void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

附提到的程序

Quick Sort Partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private void quickSort(int[] A, int start, int end) {
    if (start >= end) {
        return;
    }
    int left = start, right = end;
    // key point 1: pivot is the value, not the index
    int pivot = A[(start + end) / 2];
    // key point 2: every time you compare left & right, it should be
    // left <= right not left < right
    while (left <= right) {
        // key point 3: A[left] < pivot not A[left] <= pivot
        while (left <= right && A[left] < pivot) {
            left++;
        }
        // key point 3: A[right] > pivot not A[right] >= pivot
        while (left <= right && A[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }
    }
    quickSort(A, start, right);
    quickSort(A, left, end);
}

Partition Array

http://www.lintcode.com/en/problem/partition-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int partitionArray(int[] nums, int k) {
  if(nums == null || nums.length == 0)
      return 0;
  int i = 0, j = nums.length - 1;
  while(i <= j) {
      while(i <= j && nums[i] < k) {
          i++;
      }
      while(i <= j && nums[j] >= k) {
          j--;
      }
      if(i <= j) {
          int tmp = nums[i];
          nums[i] = nums[j];
          nums[j] = tmp;
          i++;
          j--;
      }
  }
  return i;
}

Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0)
        return 0;
    if (k <= 0)
        return 0;
    k = nums.length - k;
    return helper(nums, 0, nums.length - 1, k);
}
public int helper(int[] nums, int left, int right, int k) {
    if (left == right)
        return nums[left];
    int position = partition(nums, left, right);
    if (position == k) {
        return nums[position];
    } else if (position < k) {
        return helper(nums, position + 1, right, k);
    } else {
        return helper(nums, left, position - 1, k);
    }
}
private int partition(int[] a, int lo, int hi) {
    int i = lo, j = hi, pivot = a[hi];
    while (i < j) {
        if (a[i++] >= pivot)
            swap(a, --i, --j);
    }
    swap(a, i, hi);
    return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}
void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}