Hoare划分的正确性
题目：本章中给出的PARTITION算法并不是其最初的版本。下面给出的是最初由C.A.R.Hoare设计的划分算法。
HOARE-PARTITION(A,p,r):
1 x <- A[p] 2 i <- p-1 3 j <- r+1 4 while TRUE 5 do repeat j <- j-1 6 until A[j] <= x 7 repeat i <- i+1 8 until A[i] >= x 9 if i<j 10 then exchange A[i] <-> A[j] 11 else return j
问题：
a)说明HOARE-PARTITION在数组A={13,19,9,5,12,8,7,4,11,2,6,21}上的运行过程，并说明4~11行中while循环的每一轮迭代后，数组中各个元素的值和辅助值的情况。
下面3个问题要求读者具体地证明过程HOARE-PARTITION是正确地。假设子数组至少A[p,r]包括两个元素，证明以下几点都是正确的。
b)下标i和j满足这样的特点：即我们从不会访问数组A的，在子数组A[p,r]之外的元素。
c)当HOARE-PARTITION结束时，它返回的j值满足p<=j<r
d)当过程HOARE-PARTITION结束时，A[p..r]中的每个元素都小于或等于A[j+1,r]中的每一个元素。
在7.1节给出PARTITION过程中，将主元值（原来位于A[r]中）与围绕它划分形成的两个部分分割了开来。与此相反，HOARE-PARTITION过程则总是将主元值（原先是A[p]中的）放入两个划分A[p..j]和A[j+1...r]的某一个之中。因为p<=j<r，故这种划分总是非平凡的。
e)利用HOARE-PARTITION，重写QUICKSORT过程。
答案
a)
b)
A[p....r] ,x=A[p], j=r+1 , i=p-1；
在第一轮循环中：
由于 repeat j <- j-1 until A[j]<=x，所以j的最小值是p。
由于 repeat i<i+1 until A[i]>=x ，所以第一轮循环中，i==p
假设第一轮循环中，i跟j的repeat都走完，j==p,i==p，就满足 return j；
假设在第一轮循环中， p<j<r，那么交换i，j，进入第二轮循环。假设这时j=j1，这时A[j1]<=x ；
交换i,j后，A[p] =A[j1] <= x，同样 j永远不会超过p
同理，A[j1] = A[p] == x，i永远不会超过j1
c)
由于 repeat j <- j-1 until A[j]<=x，而且 A[p] = x，所以j的最小值是p。 p<=j
d)
e)
1 public class HoareQuickSort {
2
3 public static void quickSort(int[] arr) {
4 quickSort(arr, 0, arr.length - 1);
5 }
6
7 private static void quickSort(int[] arr, int l, int r) {
8 if (l < r) {
9 int mid = hoarePartition2(arr, l, r);
10 quickSort(arr, l, mid );
11 quickSort(arr, mid + 1, r);
12 }
13 }
14
15 private static int hoarePartition2(int[] arr, int l, int r) {
16 int e = arr[l];
17 int i = l - 1, j = r + 1;
18 while (true) {
19 do {
20 j--;
21 } while (arr[j] > e);
22
23 do {
24 i++;
25 } while (arr[i] < e);
26
27 if (i < j) {
28 swap(arr, i, j);
29 } else {
30 return j;
31 }
32 }
33 }
34
35 private static void swap(int[] arr, int i, int j) {
36 int e = arr[i];
37 arr[i] = arr[j];
38 arr[j] = e;
39 }
40
41 public static void main(String[] args) {
42 int arr[] = {13,19,9,5,12,8,7,4,11,2,6,21};
43 HoareQuickSort.quickSort(arr);
44 System.out.println(Arrays.toString(arr));
45 }