一种快速排序的算法 - 黑马程序员技术交流社区

public class SortTest {
public static void main(String[] args) {
int[] arr = {52,18,94,36,72,48,88,65,20};
printArray(arr);
Sort.quickSort(arr);
printArray(arr);
}
public static void printArray(int[] arr) {
System.out.print("[");
for(int x = 0; x < arr.length-1; x++) {
System.out.print(arr[x] + ",");
}
System.out.println(arr[arr.length-1] + "]");
}
}
class Sort {
//对整个数组进行快速排序
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length-1);
}
//对数组[left...right]进行快速排序
public static void quickSort(int[] arr, int left, int right) {
int pivot;
if(left < right) { //若调用者传入的参数左指针比右指针大则不进行排序
pivot = getPivot(arr, left, right); //调用getPivot方法获取分割高低两个数组的枢轴
quickSort(arr, left, pivot - 1); //对低子数组进行递归快速排序
quickSort(arr, pivot + 1, right); //对高子数组进行递归快速排序
}
}
private static int getPivot(int[] arr, int left, int right) {
//定义枢轴关键字为left所指的关键字
int pivotkey = arr[left];
//当left和right不重合时执行循环
while(left < right) {
//right向左搜索，然后交换左关键字和右关键字。
while(left < right && arr[right] >= pivotkey)
right --;
swap(arr, left, right);
//right搜索完，left向右搜索，然后交换左右关键字。
while(left < right && arr[left] <= pivotkey)
left ++;
swap(arr, left, right);
}
//left和right重合时，返回一个新的枢轴
return left;
}
private static void swap(int[] arr, int n1, int n2) {
int temp = arr[n1];
arr[n1] = arr[n2];
arr[n2] = temp;
}
}

复制代码