分治算法（C++版）

#include<iostream>

using namespace std;

void printArray(int array[],int length)
{
for (int i = 0; i < length; ++i)
{
cout << array[i] << " ";
}
}

void merge(int array[],int first,int center,int end)
{
int n1 = center - first + 1;
int n2 = end - center;
int L[n1+1];
int R[n2+1];
for(int i = 0; i < n1; i++ )
{
L[i] = array[first+i];
}
for(int j = 0; j < n2; j++ )
{
R[j] = array[center+j+1];
}
L[n1] = 1000;
R[n2] = 1000;
int k1 = 0;
int k2 = 0;
for (int k = first; k <= end; ++k)
{
if(L[k1] <= R[k2])
{
array[k] = L[k1];
k1 = k1 + 1;
}else{
array[k] = R[k2];
k2 = k2 + 1;
}
}
}
void merge_sort(int array[],int first,int end)
{
if(first < end){
int center = (first + end)/2;
merge_sort(array,first,center);
merge_sort(array,center+1,end);
merge(array,first,center,end);
}
}

int main(int argc, char const *argv[])
{
int array[8] = {7,6,5,4,3,2,1,0};
cout << "原数列" << endl;
printArray(array,8);
cout << endl;
merge_sort(array,0,7);

//merge_sort()函数等价与下面注释,为了便于理解特举一个八个元素的数组详细说明
//如不懂分解原理，可参考递归函数
/*
merge(array,0,0,1);
merge(array,2,2,3);
merge(array,0,1,3);
merge(array,6,6,7);
merge(array,4,4,5);
merge(array,4,5,7);
merge(array,0,3,7);
cout << endl;
*/

cout << "排序后的数列" << endl;
printArray(array,8);


return 0;
}

巴特西

分治算法（C++版）

最新文章

热门文章