快速排序算法实现（随机生成pivot）

public class QuickSort {

    public static void main(String[] args) throws Exception {
        QuickSort quickSort = new QuickSort();
        int[] data = new int[]{4, 1, 2, 3, 5, 0, 1, 9};
        quickSort.QuickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    public void QuickSort(int[] data, int start, int end) throws Exception {
        if (start == end) {
            return;
        }
        int index = Partition(data, start, end);
        if (index > start) {
            QuickSort(data, start, index - 1);
        }
        if (index < end) {
            QuickSort(data, index + 1, end);
        }
    }


    private int Partition(int[] data, int start, int end) throws Exception {
        if (data == null || start < 0 || end >= data.length) {
            throw new Exception("输入参数错误");
        }
        int partitionIndex = RandomInRange(start, end);
        int pivot = data[partitionIndex];
        // 将pivot和最后的元素交换，这样比较的时候不会和pivot相比较，同时也让最后一个元素参与了比较
        Swap(data, partitionIndex, end);
        int small = start - 1;
        for (int index = start; index < end; index++) {
            if (data[index] < pivot) {
                small++;
                if (small != index) {
                    Swap(data, small, index);
                }
            }
        }
        small++;
        // 将pivot移动到合适的位置
        Swap(data, small, end);
        return small; // 返回当前的划分点的位置
    }


    private void Swap(int[] data, int index1, int index2) {
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /*随机生成划分的中心点*/
    private int RandomInRange(int start, int end) {
        Random random = new Random();
        // nextInt(n)生成的随机数的范围不包括n，所以我们下面加1。
        return random.nextInt(end - start + 1) + start;
    }
}

快速排序的时间复杂度：
最好：O(nlogn）
最坏：O(n^2)
平均：O(nlong)
空间复杂度：
最优O(logn)
最差O(n)

最后

以上就是背后咖啡为你收集整理的快速排序算法实现（随机生成pivot）的全部内容，希望文章能够帮你解决快速排序算法实现（随机生成pivot）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。