# Java for Quick Sort and Three-way Quick Sort

### Quick Sort Ideas

Select an element in the array (usually the first element of the array) as a reference object, arrange elements in the array smaller than the reference object to the left of the array, and elements larger than the reference object to the right of the array.

### Quick sorting steps

1. With the first element a of the array a[N] as the reference object, two pointers i and j are set to point to the positions of the array subscripts 1 and N-1, respectively.
2. Move pointer I until a[i] > a is satisfied
3. Move pointer J until a[j] < a is satisfied
4. Exchange a[i] and a[j]
5. Continue to find and exchange the next a[i] and a[j] that meet the criteria until I >= J
6. Swap a with a[j]
7. Recursively invoke the above steps on two subarrays, using a[j] (a, before swapping) as the delimitation point

### code implementation

```public void quickSort(int[] array, int low, int high) {
if (low >= high) {
return;
}
int mid = divide(array, low, high);//Find the correct position of the first element of the array in the array
quickSort(array, low, mid-1);//Recursively invoke the sort method on two subarrays
quickSort(array, mid+1, high);
}
public int divide(int[] array, int low, int high) {
int a = array[low];//Select first element as reference
int i = low + 1;//Left Pointer
int j = high;//Right Pointer
while(i <= j) {
while(array[i] <= a) {//Find the element position on the left side of the array larger than the reference
if (i >= j) {return;}//Prevent pointer movement from crossing bounds
i++;
}
while(array[j] > a) {//Find an element position smaller than the reference to the right of the array
if (j <= i) {return;}
j--
};
swap(array, i++, j--);//Swap large elements on the left with small elements on the right
}
swap(array, low, j);
return j;//The position where the pointer stops is the correct position of the first element in the array
}```

### 3-way Quick Sort

#### background

If there are a large number of duplicate elements in the array, the normal quick sort will re-slice all the duplicate elements and sort them recursively.In fact, once the position of one element is determined, the position of the other repeating elements should also be determined (the repeating elements hug together).Quick three-way sorting optimizes this problem.

```public void multiQuickSort(int[] array, int low, int high) {
if(low >= high){
return;
}
int i = array[low];//Point to the reference element, or rather, always to the first of all the repeating reference element
int j = i + 1;//Point to the lower element to be sorted
int k = high;//Point to high-order elements to be sorted
while(j <= k) {
if (a[j] < a[i]) {
swap(array, i, j);//Arrange reference elements to the front, smaller than the back
i++;//Self-increasing is to keep the pointer pointing to the reference element
j++;//Point to the next lower element to be sorted
} else if (a[j] == a[i]) {
j++;//Skip duplicate reference element
} else {
swap(array, j, k);//Swap low and high elements to be sorted
k--;//Decremental, pointing to the next higher element to be sorted
}
}//After jumping out of the loop, elements that are the same as the reference elements gather together
multiQuickSort(array, low, i - 1);//Duplicate elements can be separated from subarrays to be sorted on recursion
multiQuickSort(array, j, high);
}```

Posted on Thu, 14 May 2020 09:31:15 -0700 by advancedfuture