C++修煉筆記----------利用合并排序提升排序效率（分而治之---Divide-Conquer ）

    最近在看算法導論，看到了分而治之這一塊。将排序的性能提升到n*log(n)。

    反正剛好在熟悉C++，就拿來實作一下吧。

#include <string>

#include <iostream>

#include <vector>

using namespace std;

void Merge(int a[],int p, int q, int r)

{

int n1 = q - p + 1;

int n2 = r -q;

int ary_l[10];

int ary_r[10];

for (int i = 0;i<n1;i++)

{

ary_l[i] = a[p+i];

}

for (int j = 0;j<n2;j++)

{

ary_r[j] = a[q+1+j];

}

int i = 0;

int j = 0;

ary_l[n1] = ary_r[n2] = 100;

for (int k = p; k<=r;k++ )

{

if (ary_l[i] <= ary_r[j])

{

a[k] = ary_l[i];

i = i + 1;

}

else

{

a[k] = ary_r[j];

j = j +1;

}

}

}

void Merge_sort(int ary[] ,int p , int r)

{

int q = (p+r)/2;

if (p < r)

{

Merge_sort(ary,p,q);

Merge_sort(ary,q+1,r);

Merge(ary,p,q,r);

}

}

int main() {

int a[8];

for (int i = 0;i<8;i++)

{

cin>>a[i];

}

int te=0;

Merge_sort(a,0,7);

cout<<a[0]<<a[1]<<a[2]<<a[3]<<a[4]<<a[5]<<a[6]<<a[7];

cin>>te;

return 0;

}

    看到後面有個思考題，求一個數組的逆序數。提示用分而治之的思想。

   個人覺得在  将Merge裡面的else  加上一行  count += n1 - i + 1； 就可以了。

    幾百年沒碰過C++了。當時糾結了C++的數組長度不能是變量，list，vector又不能直接指派。迷茫中請教了一下同學。原來先申請一個足夠大的數組就可以了。真的要變成小白了。