数据结构--快速排序

• 一、快速排序的算法思想？
• 二、代码

算法思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;
    int middle = partition(arr, start, end);
    quickSort(arr, start, middle - 1);
    quickSort(arr, middle + 1, end);
}
public static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int left = start + 1;
    int right = end;
    while (left < right) {
        while (left < right && arr[left] <= pivot) left++;
        while (left < right && arr[right] >= pivot) right--;
        if (left < right) {
            exchange(arr, left, right);
            left++;
            right--;
        }
    }
    if (left == right && arr[right] > pivot) right--;
    exchange(arr, start, right);
    return right;
}
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}