1回答

Star3327752

提问者

2022-08-08

package 归并排序;

public class QuickSort {
    //传入一个数组，自动进行快速排序
    public static void QuickSort(int arr[]){
        QuickSort(arr,0,arr.length);
    }
    //快速排序本体
    private static void QuickSort(int arr[],int l,int r){
        if (l>=r)
            return;
        int mid=Partition(arr,l,r);
        QuickSort(arr,l,mid-1);
        QuickSort(arr,mid+1,r);
    }

    //快速排序的配套partition方法
    //主要作用就是定义第一个元素为中间元素，然后找出所有比它小和比它大的元素
    //那么第一步就是需要遍历一遍所有的元素
    private static int Partition(int arr[],int l,int r){
        int j=l;
        for (int i=l+1;i<arr.length;i++){
            if (arr[i]<=arr[l]){
                j++;
                swap(arr,j,i);
            }
            if (arr[i]>arr[l]){
                //啥也不干
            }
        }
        swap(arr,j,l);
        return j;
    }
    //配套swap方法
    private static void swap(int arr[],int a,int b){
        int t=arr[a];
        arr[a]=arr[b];
        arr[b]=t;
    }

    public static void main(String[] args) {
        //测试swap方法------>验证通过
        int arr[]={8,2,3,4,5,6,7,8};
        swap(arr,0,2);
        for (int n:arr)
            System.out.print(n+" ");
        System.out.println("\n===============");
        //测试partition方法-------->验证通过
        int arr2[]={4,6,5,2,3,8,7,1};
//        Partition(arr2,0,arr.length);
//        for (int n:arr2)
//            System.out.print(n+" ");
        //测试QuickSort方法
        QuickSort(arr2);
        for (int n:arr2)
            System.out.print(n+" ");

        QuickSort(arr);
        for (int n:arr){
            System.out.print(n+" ");
        }
    }
}

经过测试，有一部分数组不会出现溢出的情况，正常进行排序。比如

int arr2[]={4,6,5,2,3,8,7,1};

但是有一部分数组会出现溢出的情况，比如

int arr[]={8,2,3,4,5,6,7,8};

0

hiuyubobobo

hp>第 6 行最后一个参数应该传 arr.length - 1

22 行 for 循环结束条件应该是 i <= r

继续加油！：）

h022-08-09

共1条回复