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 class QuickSort {
long[] theArray = {};
public void insert(long value) {
//...
}
public void quickSort() {
recQuickSort(0, theArray.length - 1);
}
private void recQuickSort(int left, int right) {
if(left >= right)
return;
int p = partition(left, right);
recQuickSort(left, p - 1);
recQuickSort(p + 1, right);
}
private int partition(int left, int right) {
long pivot = theArray[right];
int leftptr = left, rightptr = right - 1;
while(true) {
while(theArray[++leftptr] < pivot);
while(theArray[--rightptr] > pivot);
if(leftptr >= rightptr)
break;
swap(leftptr, rightptr);
}
swap(leftPtr, right);
return leftptr;
}
private void swap(int left, int right) {
long tmp = theArray[left];
theArray[left] = theArray[right];
theArray[right] = tmp;
}
}