首页 > 代码库 > 归并排序的实现
归并排序的实现
归并排序也是一种很优越的排序方式,并且时间复杂度为O(nlogn),而且归并排序的思想很有意思很有启发,包括排序过程和时间复杂度的推导等等,具体可以google一下。下面给出二路归并的实现代码。
#include<iostream>using namespace std;void merge(int data[],int low,int high,int mid){ int a[mid-low+1],b[high-mid]; int i,j,k; for(int m = 0;m < mid-low+1;m ++) a[m] = data[low+m]; for(int n = 0;n <high-mid; n ++ ) b[n] = data[mid+1+n]; i = j = 0 ; k = low; while(i < mid-low+1 && j < high-mid) if(a[i] <= b[j]) data[k++] = a[i++]; else data[k++] = b[j++]; while(i < mid-low+1) data[k++] = a[i++]; while(j < high-mid) data[k++] = b[j++];} void mergesort(int data[],int low,int high){ int mid; if(low < high) { mid = int((low + high)/2); mergesort(data,low,mid); mergesort(data,mid+1,high); merge(data,low,high,mid); }}int main(){ int data[10] = {3,6,1,9,4,5,2,7,0,8}; mergesort(data,0,9); for(int i = 0;i < 10;i ++) cout<<data[i]<<" "; cout<<endl; return 0;}
运行结果如图:
归并排序的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。