按要求排序(JAVA)顺便复习一下mergesort和quicksort

输入整型数组和排序标识,对其元素按照升序或降序进行排序

http://www.nowcoder.com/questionTerminal/dd0c6b26c9e541f5b935047ff4156309

很奇怪用Arrays.sort(arr, Collections.reverseOrder()) 会报错。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++){
                arr[i] = in.nextInt();
            }
            int flag = in.nextInt();
            helper(flag, arr);
        }
    }
    private static void helper(int flag, int[] arr){
        StringBuilder sb = new StringBuilder();
        //Arrays.sort(arr);
        //mergeSort(arr);
        quickSort(arr);
        if (flag == 0){
            for (int i = 0; i < arr.length; i++){
                sb.append(arr[i]);
                sb.append(' ');
            }
        }else{
            for (int i = arr.length - 1; i >= 0; i--){
                sb.append(arr[i]);
                sb.append(' ');
            }
        } 
        System.out.println(sb.toString());
    }

    //mergesort
    private static void mergeSort(int[] arr){
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }
    private static void mergeSort(int[] arr, int[] temp, int l, int r){
        if (l == r) return;
        int mid = l + (r-l)/2;
        mergeSort(arr, temp, l, mid);
        mergeSort(arr, temp, mid + 1, r);
        merge(arr, temp, l ,mid, r);
    }
    private static void merge(int[] arr, int[] temp, int l, int mid, int r){
        for (int i = 0 ; i < arr.length; i ++){
            temp[i] = arr[i];
        }
        int p1 = l;
        int p2 = mid + 1;
        int k = l;
        while(p1 <= mid && p2 <= r){
            if (temp[p1] < temp[p2]){
                arr[k] = temp[p1];
                p1++;
            }else{
                arr[k] = temp[p2];
                p2++;
            }
            k++;
        }
        while(p1 <= mid){
            arr[k] = temp[p1];
            p1++;
            k++;
        }
    }

    //quicksork
    private static void quickSort(int[] arr){
        quickSort(arr, 0, arr.length-1);
    }
    private static void quickSort(int[] arr, int l, int r){
        if (l >= r) return;
        int idx = help(arr, l, r);
        quickSort(arr, l, idx-1);
        quickSort(arr, idx+1, r);
    }
    private static int help(int[] arr, int l, int r){
        int k = arr[r];
        int p1 = l;
        int p2 = r - 1;
        while (p1 <= p2){
            if (arr[p1] <= k){
                p1++;
            }else if (arr[p2] > k){
                p2--;
            }else{
                int cur = arr[p1];
                arr[p1] = arr[p2];
                arr[p2] = cur;
                p1++;
                p2--;
            }
        }
        arr[r] = arr[p1];
        arr[p1] = k;
        return p1;
    }

}
全部评论
因为你的数组是int[],基本类型,用Integer[]就行了
点赞 回复 分享
发布于 2022-02-09 15:19

相关推荐

11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务