归并排序

归并排序属于分治算法

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

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

归并排序演示:

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