归并排序（c++ 实现）

#include <iostream>

using namespace std;

void merge(int *data,int start,int end,int *result) { int leftl=start+(end-start)/2; //左边数组的最大下标 int lindex=start; //左边数组的起始下标 int rindex=leftl+1; //右边数组的起始下标 int reindex=start; //暂存数组的起始下标 while(lindex<=leftl&&rindex<=end) { if(data[lindex]<=data[rindex]) { result[reindex++]=data[lindex++]; } else { result[reindex++]=data[rindex++]; } } while(lindex<=leftl) { result[reindex++]=data[lindex++]; } while(rindex<=end) { result[reindex++]=data[rindex++]; } }

void merge_sort(int *data,int start,int end,int *result) { if(start==end) { return; } int mid=start+(end-start)/2; merge_sort(data,start,mid,result); merge_sort(data,mid+1,end,result); merge(data,start,end,result); //把排序后的区间数据复制到原始数据中去 for(int i = start;i <= end;++i) data[i] = result[i]; }

int main() { int data[] = {9,6,7,22,20,33,16,20}; const int length = 8; int result[length]; cout << "Before sorted:" << endl; for(int i = 0;i < length;++i) cout << data[i] << " "; cout << endl; cout << "After sorted:" << endl; merge_sort(data,0,length-1,result); for(int i = 0;i < length;++i) cout << result[i] << " "; cout << endl;

return 0; }