算法 c++ 深度优先 归并排序 （dfs深度理解）

        归并排序与快排一样也是一种分治的算法，与快排的区别在于是取数组的中间元素分为左右两侧，先把两侧的排序好之后再进行归并。复杂程度只有O(n)。

        先把main函数中的输入输出定义函数完成。

#include

using namespace std;

const int N=1000010;

int n;

int q[N],tmp[N]

int main()

{

scanf("%d",&n);

for(int i=0;i

scanf("%d",&q[i]);

}

merge_sort(q,0,n-1);

for(int i=0;i

printf("%d ",q[i]);

}

return 0;

}

        归并排序最重要的一步就是归并。需要另外开辟一个临时保存数据的数组tmp，merge_sort的函数，它接受三个参数：一个整型数组q、左边界l和右边界r。该函数的作用是对数组q中从下标l到下标r的元素进行排序。函数首先判断左边界是否大于等于右边界，如果是，则说明已经到达了递归的基本情况，直接返回即可。否则，计算中间位置mid，然后递归地对左半部分和右半部分分别进行排序，在左右两部分排好序后，定义两个指针（注意不是真正意义上的指针，是两个标记，可以理解为数组的下标）。一个指向左半部分的首记为 i，另一个指向右半部分的首记为 j，比较q[ i ]和q[ j ]两个位置上数组元素的大小，如果q[ i ]

void merge_sort(int *q,int l,int r)

{

if(l>=r) return;

int mid=l+r>>1;

merge_sort(q,l,mid); merge_sort(q,mid+1,r);

int k=0,i=l,j=mid+1;

while(i<=mid&&j<=r)

if(q[i]<=q[j]) tmp[k++]=q[i++];

else tmp[k++]=q[j++];

while(i<=mid) tmp[k++]=q[i++];

while(j<=r) tmp[k++]=q[j++];

for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

}

        个人认为归并中的递归排序左右两半部分是比较难理解的。这里用图解来解释。比如先输入9个数据：6 5 7 1 4 3 2 8 9。即传入函数时是 l = 0，r = 8。不满足条件if ( l > = r )，于是取中间值后执行函数本身 merge_sort(q,l,mid); 与 merge_sort(q,mid+1,r);直到分为一个元素之后开始比较，每次递归的返回都将比较的结果填入tmp中直到左右两部分比较完成。

全部代码如下：

#include

using namespace std;

const int N=1000010;

int n;

int q[N],tmp[N];

void merge_sort(int *q,int l,int r)

{

if(l>=r) return;

int mid=l+r>>1;

merge_sort(q,l,mid); merge_sort(q,mid+1,r);

int k=0,i=l,j=mid+1;

while(i<=mid&&j<=r)

if(q[i]<=q[j]) tmp[k++]=q[i++];

else tmp[k++]=q[j++];

while(i<=mid) tmp[k++]=q[i++];

while(j<=r) tmp[k++]=q[j++];

for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

}

int main()

{

scanf("%d",&n);

for(int i=0;i

scanf("%d",&q[i]);

}

merge_sort(q,0,n-1);

for(int i=0;i

printf("%d ",q[i]);

}

return 0;

}

参考文章