归并排序实现c++版

青旅半醒 2022-05-18 02:24 210阅读 0赞

### |基本思路 ###

归并排序利用了递归的思想（而是分而治之的思想），将数组一分为二，先将左半部分（坐标为0~mid）排好序，再将右半部分排好序（都是调用函数），最后将两部分合并起来。整体算法时间复杂度为O(nlogn)，空间复杂度为O（n）。

### **|归并排序的c++具体实现** ###

#include<bits/stdc++.h>
    using namespace std;
    
    //归并过程
    void merge(int arr[], int l, int mid, int r){
    	int help[r-l+1];//辅助数组
    	int i = 0;
    	int lIndex = l;
    	int rIndex = mid+1;
    	while(lIndex <= mid && rIndex <= r){
    		help[i++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++]:arr[rIndex++];	
    	}
        //左边和右边肯定有一边到头了，不可能同时，因为每次只移动一边
    	while(lIndex <= mid){
    		help[i++] = arr[lIndex++];
    	} 
    	while(rIndex <= r){
    		help[i++] = arr[rIndex++];
    	}
        //将排好序的辅助数组赋值给原始数组，不需要返回值
    	for(i = 0; i < r-l+1; i++){
    		arr[l+i] = help[i];
    	}
    }
    
    //递归
    static void mergeSort(int arr[], int l, int r){
    	if(l == r){
    		return;
    	}
    	int mid = (l + r) / 2;
        //左半部分归并排序
    	mergeSort(arr, l, mid);
        //右半部分归并排序
    	mergeSort(arr, mid+1, r);
        //左右部分归并
    	merge(arr, l, mid, r);
    }
    
    //归并排序整个数组
    void mergeSort(int arr[], int n){
        //如果数组为空或只有一个元素，不需要排序
    	if(arr == NULL || n < 2){
    		return;
    	}
    	mergeSort(arr,0,n-1);
    }
    
    
    int main(){
    	int n; 
    	while(cin >> n){
    		int arr[n];
    		for(int i = 0; i < n; i++) cin >> arr[i];
    
    		mergeSort(arr, n);
    
    		for(int i = 0; i < n; i++){
    			cout << arr[i] << " ";
    		} 
    		cout << endl;
    	}
    	return 0;
    }

### **|补充：递归思想** ###

递归过程就是系统辅助你压栈的过程，保护好现场，以后好继续。

一个函数调用过程之前，会把自己的所有信息全部压入栈中，保留现场，子过程返回以后会利用这些信息彻底还原现场继续跑，跑完之后再从栈中拿出一个函数再还原现场，最终串起来所有子过程和父过程。

递归过程分析时间复杂度：(看是否满足master方程)

T(N) = aT(N/b) + O(N^d)

N是原始问题的样本量，a是子过程的发生次数，N/b是子过程的样本量，O(N^d)是除子过程调用外剩下的过程。

log(b,a) > d ----------> O(N^log(b,a))

log(b,a) = d ----------> O(N^d\*logN)

log(b,a) < d -----------> O(N^d)

--------------------

感谢左神的讲解，终于记住了递归排序的具体实现步骤！！自己实现的过程中发现一些细节需要注意，不然总是出错，尤其是要注意边界。递归的思想左神也讲得超棒！为左神打电话！（人还帅哈哈哈）继续加油吧ヾ(◍°∇°◍)ﾉﾞ