小言_互联网的博客

ACM - Merge Sort (Basic algorithm) Describted by Java

428人阅读  评论(0)

Basic Algorithm - Merge_sort Module

import java.io.*;

public class Main{
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter pw = new PrintWriter(System.out);
    static int ans[], nums[];
    public static void main(String []args) throws IOException{
        st.nextToken();
        int n = (int)st.nval;
        ans = new int[n];
        nums = new int[n];
        for (int i = 0; i < n; i ++) {
            st.nextToken();
            nums[i] = (int)st.nval;
        }
        merge_sort(nums, 0, n - 1);
        for (int i = 0; i < n; i ++) {
            pw.print(nums[i] + " ");
            pw.flush();
        }
    }
    
    private static void merge_sort(int nums[], int l, int r){
        if (l >= r) return;
        int mid = l + r >> 1;
        int len = r - l + 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        int p = l, j = l;
        int q = mid + 1;
        for (int i = 0 ; i < len ; i++) {
            if (q > r || (nums[q] > nums[p] && p <= mid)) ans[j++] = nums[p++];
            else ans[j++] = nums[q++];
        }
        for (int i = l ; i <= r; i++) nums[i] = ans[i];
    }
}

转载:https://blog.csdn.net/qq_43515011/article/details/102570128
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场