class QuickSort{
// 交换元素位置
public void swap(int array[], int i , int k) {
int temp = array[i];
array[i] = array[k];
array[k] = temp;
}
public int partition(int []array, int left, int right) {
int storeIndex = left;
int pivot = array[right]; // 直接选最右边的元素为基准元素
for (int i = left; i < right; i++) {
if (array[i] < pivot) {
swap(array, storeIndex, i);
storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
}
}
swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
return storeIndex;
}
public void sort(int []array, int left,int right) {
if (left > right) {
return ;
}
int storeIndex = partition(array, left, right);
sort(array, left, storeIndex - 1);
sort(array, storeIndex + 1, right);
}
}