快速排序-Quick Sort

快速排序算法本质是通过多次比较和交换来实现排序。

实现步骤
1,设定分界值，使用分界值和待排序元素比较大小，将所有元素分为左右两部分。
2,进行比较并交换，大于或者等于分界值的元素值集中到分界值的右边，小于分界值的元素集中到分界值的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
3,对左边和右边的元素进行独立排序。对于左侧的元素集，又可以取一个分界值，将该部分元素集分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的元素也使用相同方法进行处理。
4,重复上述过程，通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各元素排序完成后，整个元素集的排序也就完成了。

实现代码：

public void solution() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int length = befArrays.length;

    this.quickSort(befArrays, 0, length-1);

    for (int i=0; i<length; i++) {
        System.out.printf(befArrays[i] + "\t");
    }
}

public void quickSort(int[] befArrays, int left, int right) {
    if (left >= right) {
        return;
    }

    int flag = befArrays[left];
    int index = left;
    int l = left;
    int r = right;
    while (l<r) {
        while (l<r && flag<befArrays[r]) {
            r--;
        }
        if (l<r && flag>=befArrays[r]) {
            befArrays[index] = befArrays[r];
            befArrays[r] = flag;
            l++;
            index = r;
        }

        while (l<r && flag>befArrays[l]) {
            l++;
        }
        if (l<r && flag<befArrays[l]) {
            befArrays[r] = befArrays[l];
            befArrays[l] = flag;
            r--;
            index = l;
        }
    }
    this.quickSort(befArrays, left, index-1);
    this.quickSort(befArrays, index+1, right);
}

算法分析：