首页 > 代码库 > 数据结构-归并排序
数据结构-归并排序
归并排序的基本思想:首先,将R[0..n-1]看成是n个长度为1的有序表,将相邻的有序表进行归并,得到n/2个长度为2的有序表;然后,再将这些有序表成对归并,得到n/4个长度为4的有序表,如此循环下去,最后得到一个长度为n的有序表。
注意的是:Merge()实现了一次归并,接下来需要利用MergePass()解决一趟归并问题。在某趟归并中,设各子表长度为length(最后一个字表的长度可能小于length),则归并前R[0..n-1]中共有[n/length]个有序的字子表:R[0..length-1],R[length..2length-1],...,R[(n/length)*length..n-1]。调用Merge()将相邻的一对子表进行归并时,必须对表的个数可能是奇数、以及最后一个子表的长度小于length这两种特殊情况进行特殊处理:若子表个数为奇数,则最后一个子表无须和其他子表进行归并;若子表个数为偶数,则要注意到最后一对子表中后一个子表的区间上界是n-1.
#include <iostream> using namespace std; void Merge(int* a,int low,int mid,int high){ int* a1 = new int[high-low+1]; int k = 0; //k为a1的下标 int i = low,j = mid+1; while(i <= mid && j <= high){ //两个小数组扫描 if(a[i] <= a[j]){ a1[k] = a[i]; k++; i++; } else{ a1[k] = a[j]; k++; j++; } } while(i <= mid){ a1[k] = a[i]; i++; k++; } while(j <= high){ a1[k] = a[j]; j++; k++; } for(int i=low,k=0;i<=high;i++,k++){ //一节一节拷贝回原数组 a[i] = a1[k]; } delete[] a1; } void MergePass(int* a,int ChildLength,int n){ int i; for(i=0;i+2*ChildLength-1<n;i=i+2*ChildLength){ //归并ChildLength长的两相邻子表 Merge(a,i,i+ChildLength-1,i+2*ChildLength-1); } if(i+ChildLength-1 < n){ //余下两个子表,后者长度小于ChildLength Merge(a,i,i+ChildLength-1,n-1); } } void MergeSort(int* a,int n){ for(int i=1;i<n;i*=2){ MergePass(a,i,n); } } int main(){ int a[] = {5,1,2,4,8,7,6,9,3,0,7,6}; int n = sizeof(a)/sizeof(*a); MergeSort(a,n); for(int i=0;i<n;i++){ cout << a[i] << " "; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。