首页 > 代码库 > 归并排序的实现

归并排序的实现

  归并排序也是一种很优越的排序方式,并且时间复杂度为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;}

  运行结果如图:技术分享

归并排序的实现