3.3 分治模式的完美诠释:归并排序

2019-03-23  本文已影响0人  Aurochsy

Chapter3: 更好的查找与排序算法

3. 分治模式的完美诠释:归并排序

1. 基本思想

对于一次递归的调用来说

归并排序示意图 某层递归调用上的合并示意图

2. 代码实现

#include<iostream>
#include<cstdlib>
using namespace std;

void mergeSort(int* arr,int begin,int end); 
void merge(int* arr,int begin,int mid,int end);

int main(){
    int arr[6]={1,3,2,5,4,7};
    int arrLen=sizeof(arr)/sizeof(arr[0]);
    
    mergeSort(arr,0,arrLen-1);
    
    for(int i=0;i<arrLen;i++){
        printf("%d ",arr[i]);
    }
    return 0;
} 

void mergeSort(int* arr,int begin,int end){
    if(begin<end){//注意这个出口条件,不然会陷入死循环 
        int mid=begin+((end-begin)>>1);
        mergeSort(arr,begin,mid);//递归调用起到划分作用
        mergeSort(arr,mid+1,end);
        merge(arr,begin,mid,end);
    }
}

//合并函数
void merge(int* arr,int begin,int mid,int end){
    int len=end-begin+1;//当前划分状态下的数组长度 
    int tmpArr[len];//辅助数组
     
    int leftP=begin;//左指针 
    int rightP=mid+1;//右指针 
    int i=0;//辅助数组当前存取的下标 
    //printf("initial. len=%d\n",len);
    
    while((leftP<=mid)&&(rightP<=end)){
        if(arr[leftP]<=arr[rightP]){
            tmpArr[i]=arr[leftP];
            i++;
            leftP++;
            //或直接写为 tmpArr[i++]=arr[leftP++];
        }
        else{
            tmpArr[i]=arr[rightP];
            i++;
            rightP++; 
        }
    }
    while(leftP<=mid){//如果左数组有剩余元素 
        tmpArr[i]=arr[leftP];
        i++; 
        leftP++;
    }
    while(rightP<=end){//如果右数组有剩余元素 
        tmpArr[i]=arr[rightP];
        i++;
        rightP++;
    }
    /*将排序好的辅助数组复制到原数组中,
    因为递归要用到上一层排好序的原数组,并所以这一步必不可少*/ 
    i=0;  
    while(begin<=end){
        arr[begin++]=tmpArr[i++];
    }
    //注意每次递归数组的开始位置不一样,为begin,不一定是0,所以不能用下面的赋值方法 
//  for(i=0;i<len;i++){
//      arr[i]=tmpArr[i];
//  }       

}

3. 快速排序和归并排序的比较

快速排序关键在于划分,归并排序关键在于合并

快速排序划分的左右两个数组左边数组的元素一定小于右边数组的元素,但是在左数组或右数组内元素不一定有序

归并排序划分的左右两个数组左边的数组的元素不一定小于右边的元素,但是在左右数组内的元素分别是有序的

快速排序的思想

4. 参考资料

[1] 图解排序算法(四)之归并排序

上一篇 下一篇

猜你喜欢

热点阅读