排序算法之归并排序

void mergeSort(int q[], int l, int r)
{
    //递归终止的条件
    if(l >= r) return;


    //第一步：分解成子问题
    int mid = l + r >> 1;


    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);


    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];


    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}
复制

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //创建数组并设置数组长度
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        //输入数组元素
        String[] ss = br.readLine().split(" ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        merge_sort(arr, 0, n - 1);
        for (int i = 0;i<arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }


    //归并排序模板
    private static void merge_sort(int[] q, int l, int r) {
        if (l >= r) return;


        int temp[] = new int[r - l + 1], k = 0;
        //1.中间点
        int mid = l + r >> 1;


        //2.递归排序左右两段
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1,r);


        //3.合并子问题
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) {
                temp[k++] = q[i++];
            } else {
                temp[k++] = q[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = q[i++];
        }


        while (j <= r) {
            temp[k++] = q[j++];
        }


        for (int m = l,x = 0;m<=r;m++,x++){
            q[m] = temp[x];
        }
    }
}
复制