归并排序模板

归并排序属于分治算法

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题;

step3 合并：将各个子问题的解合并为原问题的解;

归并排序模板

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];

}

归并排序演示:

3.gif

Java版本代码

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];

        }

    }

}