归并排序实现

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


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之,将数组不断分割,最后将两部分数组合并,通过判断第一部分和第二部分数组当前元素的大小来合并,不断合并直到完成排序。

归并排序是稳定的排序方式,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注