高等排序
归并排序
之前介绍的排序算法,如插入排序、选择排序具有高达 O ( N 2 ) O(N^2) O(N2)级的复杂度,使它们在面对大规模输入时无能为力。归并排序利用分治思想,可将排序复杂度降低到 O ( n l o g n ) O(nlogn) O(nlogn)量级,大大加快了排序速度。
基本原理:将一未排序序列归分为两个子序列,对子序列排序后,将他们按顺序合并,并对子序列递归进行上述过程。如何正确的合并两个已排序序列是归并排序的核心。
复杂度:划分到最后一层时,可得 N N N个单独元素,因此最多可划分至 l o g 2 N log_2N log2N层,每层总的元素均为 N N N,每层进行合并操作时,共需进行 N N N次比较,由此完成整个合并(排序完毕)共需 N l o g 2 N Nlog_2N Nlog2N次比较,即归并排序的时间复杂度为 N l o g N NlogN NlogN级。
排序图解:
C++实现:
void merge(vector<int> &a, int left,int mid,int right)
{
int n1 = mid - left; //两个序列长度
int n2 = right - mid;
vector<int> L;
vector<int> R;
for(int i = 0;i < n1;i++) L.push_back(a[left+i]);
for(int i = 0;i < n2;i++) R.push_back(a[mid+i]) ;
L.push_back(INT32_MAX); //两个序列后插入足大的数
R.push_back(INT32_MAX);
int i = 0;
int j = 0;
for(int k = left;k<right;k++) //
{
if(L[i]<=R[j])
{
//取左右两个首元素小者,放入已排序列,并将此首元素后移,且待i或j增加到INT32_MAX时,它注定不会再被放到已排序列了
a[k] = L[i++];
}else
{
a[k] = R[j++];
}
}
}
void mergeSort(vector<int> &a,int left,int right)
{
if(left + 1 < right)
{
int mid = (left + right)/2;
mergeSort(a,left,mid); //左
mergeSort(a,mid,right); //右
merge(a,left,mid,right); //合并
}
}
rust实现(待更新):