思想

快速排序也属于交换排序，不同于冒泡排序的是，快速排序在每一轮挑选出一个基准元素，然后比较其它元素，比基准元素小的移到左边，比基准元素大的移到右边，从而拆解成两个部分，也就是分治法。每一轮的交换需要把元素全部对比一遍，时间复杂度是O(n)，需要进行logn轮，所以时间复杂度是O(nlogn)

双边循环法

对于一个数组[2,5,1,4,8,6,9,7]，选定一个基准元素pivot，并且设置两个指针left和right，指向数组的最左和最右的两个元素，分三步走：1、right指针向左移动一直到元素小于基准元素为止，2、left指针向右移动一直到元素大于基准元素为止，3、交换此时left和right指向的元素。然后继续一直到left=right，交换基准元素与left=right时指向的元素；这样一来，比基准元素小的都在左边，比基准元素大的都在右边了；然后对于左边右边新拆开的数组继续以上步骤执行。

public static void quickSort(int arr[], startIndex, endIndex) {
    // 当startIndex 大于或等于 endIndex时，递归结束
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr[], startIndex, endIndex);
    quickSort(arr[], startIndex,pivotIndex - 1);
    quickSort(arr[], pivotIndex + 1, endIndex);
}
public static int partition(arr[], startIndex, endIndex) {
    int left = startIndex;
    int right = endIndex;
    int pivot = arr[startIndex];
    while (left != right) {
        // 1、right指针向左移动一直到元素小于基准元素为止
        while (right > left && arr[right] > pivot) {
            right--;
        }
        // 2、left指针向右移动一直到元素大于基准元素为止
        while (left < right && arr[left] < pivot) {
            left++;
        }
        // 3、交换此时left和right指向的元素
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    // 交换基准元素与left=right时指向的元素
    arr[startIndex] = arr[left];
    arr[left] = pivot;
    return left;
}

单边循环法

对于一个数组[2,5,1,4,8,6,9,7]，选定一个基准元素pivot，然后设定一个标志位mark，mark的作用是用来作分界点，左边的元素都大于基准元素，右边的元素都小于基准元素。具体表现为，取第一个元素的位置为mark，然后从第二个元素开始遍历，如果遍历到的元素大于基准元素，则不做改变，如果遍历的元素小于基准元素，那么此时mark位置的元素与遍历到的元素交换位置，且mark向右移动一位，知道遍历完。

public static void quickSort(int arr[], startIndex, endIndex) {
    // 递归结束的条件
    if (startIndex >= endIndex) {
        return;
    }
    int pivotIndex = partition(arr[], startIndex, endIndex);
    quickSort(arr[], startIndex,pivotIndex - 1);
    quickSort(arr[], pivotIndex + 1, endIndex);
} 
public static int partition(arr[], startIndex, endIndex) {
    int pivot = arr[startIndex];
    int mark = satrtIndex;
    for (int i = startIndex + 1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            mark ++;
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}