归并排序代码实现

谁践踏了优雅 2024-03-29 15:22 61阅读 0赞

## 归并排序 ##

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式  
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式  
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围  
1≤n≤100000  
输入样例：  
5  
3 1 2 4 5  
输出样例：  
1 2 3 4 5

**算法思路**  
算法的时间复杂度的话：最差的时间复杂度也有O(nlogn)

这个题需要记住的是这个归并排序的模板，原理的话  
将一段序列不断的迭代划分成两个区间，直到子区间为空或者只剩一个元素。

那么也就意味着所有子区间都成了有序的序列。

（没有元素和一个元素算作序列有序）

然后不断将已有序的子序列递归合并，最终得到完全有序的序列

**C++**

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    int tmp[N], q[N];
    int n;
    
    void merge_sort(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;
        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 (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    }
    
    int main()
    {
        
        scanf ("%d", &n);    
        for (int i = 0; i < n; ++i) scanf ("%d", &q[i]);
        
        merge_sort(q, 0, n - 1);
        
        for (int i = 0; i < n; ++i) printf("%d ", q[i]);
        return 0;
    }

**Java**

import java.io.*;
    import java.util.*;
    
    public class Main
    {
        
        static int N = (int)1e6 + 10;
        static int tmp[] = new int [N], q[] = new int [N];
        int n;
    
        public static void main(String[] args) throws IOException
        {
        
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(reader.readLine().trim());
            String [] strs = reader.readLine().trim().split(" ");
            for (int i = 0; i < n; ++ i) q[i] = Integer.parseInt(strs[i]);
            merge_sort(q, 0, n - 1);
            for (int i = 0; i < n; ++ i) System.out.print(q[i] + " ");
        }
        static void merge_sort(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;
            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 (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
        }
    
    }