[数据结构与算法]快速排序（Java）

快速排序

排序原理：

1. .找一个基准值，用两个指针分别指向数组的头部和尾部；
2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4. 交换当前左边指针位置和右边指针位置的元素；
5. .重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

演示

代码

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {14, 21, 2, 32, 29, 43, 43, 13, 12, 30, 19, 34, 38, 8, 48};
        sort(arr);
        for (int a : arr) {
            System.out.print(a + ", ");
        }
    }

    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int left, int right) {
        if (left < right) {
            int index = partition(arr, left, right);
            sort(arr, left, index - 1);
            sort(arr, index + 1, right);
        }
    }

    public static int partition(int[] a, int lo, int hi) {
        int key = a[lo];//把最左边的元素当做基准值
        int left = lo;//定义一个左侧指针，初始指向最左边的元素
        int right = hi + 1;//定义一个右侧指针，初始指向左右侧的元素下一个位置
        //进行切分
        while (true) {
            //先从右往左扫描，找到一个比基准值小的元素
            while (key < a[--right]) {//循环停止，证明找到了一个比基准值小的元素
                if (right == lo) {
                    break;//已经扫描到最左边了，无需继续扫描
                }
            }
            //再从左往右扫描，找一个比基准值大的元素
            while (a[++left] < key) {//循环停止，证明找到了一个比基准值大的元素
                if (left == hi) {
                    break;//已经扫描到了最右边了，无需继续扫描
                }
            }
            if (left >= right) {
                //扫描完了所有元素，结束循环
                break;
            } else {
                //交换left和right索引处的元素
                int tmp = a[left];
                a[left] = a[right];
                a[right] = tmp;
            }
        }
        //交换最后rigth索引处和基准值所在的索引处的值
        int tmp = a[lo];
        a[lo] = a[right];
        a[right] = tmp;
        return right;//right就是切分的界限
    }

}

时间复杂度：O(nlogn)