数据结构经典算法六：快速排序与三种分段方法

阅读量：

快速排序

基本理念：运用分治策略进行处理。首先确定一个基准数值pivot，将所有待处理元素划分为三个区域，其中小于或等于该基准值的元素排列于其左侧，基准值本身处于中间位置，而大于基准值的元素则置于右侧。随后，对左右两侧形成的两个子区间继续执行相同的划分操作。

快速排序主要分三部分：

1. 选择一个基准值(可选择区间最右边的元素作为基准值)

确定基准值的三种途径：

随机选取法
采用边界数值（即最左侧或最右侧的数值）
选取中间值的方法

复制代码

    //实现基准值的三数取中法
    int medianOfThree(int[] array, int left, int right) {
    int mid = left + (left + right) / 2;
    if(array[left] > array[right]){
        if(array[left] < array[mid]){
            return left;
        } else if(array[mid] > array[right]){
            return mid;
        } else {
            return right;

全部评论 (0)

还没有任何评论哟~