有关快速排序-java实现

发布时间 2023-03-29 17:40:07作者: Mexcellent
对于快排,思想是很简单的,易于理解的,关键在于代码的实现中,出现的一些问题,包括遇到的,相同大小的数的位置处理,如果使用递归防止出现无限递归地情况,想清楚其中左所引与又索引的变化:
    /**
     * 快速排序的简介写法(完美)
     * @param num 目标排序数组
     * @param leftIndex 每次处理的左端索引
     * @param rightIndex 每次处理的右端索引
     */
    public static void quickSort2(int[] num,int leftIndex,int rightIndex){
        int leftI=leftIndex;
        int rightI=rightIndex;
        //基准数,依次将数组中的数分为两部分
        int midNum=num[leftIndex];
        int temp=0;
        //递归出口
        if (leftIndex>=rightIndex)
            return;
        while (leftI<rightI){
            //寻找右端第一个大于基准数的索引,注意最后的两索引只会相等
            while (num[rightI]>=midNum&&leftI<rightI){
                rightI--;
            }
            //寻找左端第一个大于基准数的索引
            while (num[leftI]<=midNum&&leftI<rightI){
                leftI++;
            }
            //交换左右端数
            if (leftI<rightI){
                temp=num[leftI];
                num[leftI]=num[rightI];
                num[rightI]=temp;
            }
        }
        //基准数交换。应当与左端最大的数交换
        num[leftIndex]=num[leftI];
        num[leftI]=midNum;
        //递归处理左右的数组
        quickSort2(num,leftIndex,rightI-1);
        quickSort2(num,leftI+1,rightIndex);
    }