归并排序 O(nlogn)

本文主要是介绍归并排序 O(nlogn)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

该算法是采用分治法的一个非常典型的应用。

归并排序可以理解为反复调用二路归并算法而实现的。所谓二路归并，就是将两个有序序列合并成为一个有序序列。

二路归并属于迭代式算法。每次迭代需要比较两个待合并序列的首元素，将小者取出添加至新序列的末尾。如此反复，直到一序列为空。最后，将另一非空的序列整体接至输出向量的末尾。

#include <bits/stdc++.h>
using namespace std;
int array[8]={6,3,2,7,1,5,8,4};
int temp[8];
void merge(int *a,int lo,int mi,int hi,int *temp){int i=lo; int m=mi;int j=mi+1; int n=hi;int k=0;while((i<=m)||(j<=n)){if((i<=m)&&(!(j<=n)||(a[i]<=a[j]))) temp[k++]=a[i++];if((j<=n)&&(!(i<=m)||(a[i]>a[j]))) temp[k++]=a[j++];}/*while(i<=m&&j<=n){if(a[i]<=a[j])temp[k++]=a[i++];elsetemp[k++]=a[j++];}while(i<=m) temp[k++]=a[i++];while(j<=n) temp[k++]=a[j++];*/for(int z=0;z<k;z++) a[lo+z]=temp[z];
}
void mergeSort(int *a,int lo,int hi,int *temp){if(lo>=hi) return;int mi=(hi+lo)/2;mergeSort(a,lo,mi,temp);mergeSort(a,mi+1,hi,temp);merge(a,lo,mi,hi,temp);
}
int main(){mergeSort(array,0,7,temp);for(int i=0;i<8;i++)cout<<array[i];cout<<endl;
} 

 

这篇关于归并排序 O(nlogn)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---