快速排序--取最左和中间

101 阅读 0 评论 67 点赞

我是靠谱客的博主认真小熊猫，最近开发中收集的这篇文章主要介绍快速排序--取最左和中间，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.快速排序–取最左为基准

import java.util.Arrays;

/**
 * 快速排序
 *
 * 1. 算法步骤
 * 从数列中挑出一个元素，称为 "基准"（pivot）;
 *
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 *
 * @author alan
 * @since 2022/2/13
 */
public class QuickSort {

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

    public static int partition(int[] ints,int left,int right){
        int pivot = ints[left];
        while (left<right){
            //如果最右边大于基准值说明不需要换位
            while (left<right&&ints[right]>=pivot){
                right--;
            }
            //执行到这里说明小于基准值，需要换位，同时right空出来了
            ints[left] = ints[right];
            //交替left移动 如果最左边小于基准值说明不需要换位
            while (left<right&&ints[left]<=pivot){
                left++;
            }
            //执行到这里说明大于基准值，需要换位，同时left空出来了
            ints[right] = ints[left];
            //如果相等，说明这一次排序确定基准值的位置
            if (right == left){
                ints[left] = pivot;
            }
        }
        return left;
    }

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

2.快速排序–取最右为基准

//快速排序 取中间为基准
public static void quickSortCenter(int[] ints,int left,int right){
    if (left<right){
        int center = (right+left)/2;
        int pivot = ints[center];
        int i = left-1;
        int j = right+1;
        while (true){
            while (ints[++i]<pivot);
            while (ints[--j]>pivot);
            //这里找到中间基准值的位置
            if (i>=j){
                break;
            }
            swap(ints,i,j);
        }
        quickSortCenter(ints,left,i-1);
        quickSortCenter(ints,j+1,right);
    }
}

public static void swap(int[] ints,int i,int j){
    int temp;
    temp = ints[j];
    ints[j] = ints[i];
    ints[i] = temp;
}

public static void main(String[] args) {
    int[] ints = new int[]{2,3,5,4,1,8,7};
    System.out.println("取中间为基准");
    quickSortCenter(ints,0,ints.length-1);
    System.out.println(Arrays.toString(ints));
}