数据结构之归并排序，C++兑现 - C++当前位置:& &&&数据结构之归并排序，C++兑现数据结构之归并排序，C++兑现&&网友分享于：&&浏览：11次数据结构之归并排序，C++实现下面是我写的用归并排序给20000个数排序，但是到调用函数时，就显示xxx.exe已停止工作，难道是要排序的数太多了？哪位高手给看看是怎么回事，谢谢了。#include&iostream&#include&stdlib.h&#include&time.h&#include&iomanip&#define
MAXSIZE 20000typedef struct{ &}RedTtypedef struct{RedType r[MAXSIZE+1];}Svoid Merge (RedType SR[],RedType TR[],int i,int m,int n)& { &
int j,k; &
for (j=m+1,k=i;i&=m&&j&=n;++k)&
if(SR[i].key&SR[j].key) TR[k]=SR[i++]; &
else TR[k]=SR[j++]; &
if (i&=m) &
while (k&=n&&i&=m) TR[k++]=SR[i++]; &
if (j&=n)&
while (k&=n&&j&=n) TR[k++]=SR[j++];}void MSort(RedType SR[], RedType TR1[], int s, int t) &{ & &
RedType TR2[20000]; &
if (s==t) TR1[t] = SR[s]; &
m=(s+t)/2;
// 将SR[s..t]平分为SR[s..m]和SR[m+1..t] &
MSort(SR,TR2,s,m);
// 递归地将SR[s..m]归并为有序的TR2[s..m] &
MSort(SR,TR2,m+1,t);
// 将SR[m+1..t]归并为有序的TR2[m+1..t] &
Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] &
}}& void main(){ &
int i,a[20001]; &
cout&&&\\(^o^)/产生20000随机数过程\\(^o^)/&&& &
srand((unsigned)time(NULL)); &
for(i=1;i&20001;i++) &
a[i]=rand()%32768; &
system(&pause&); &
for(i=1;i&20001;i++) &
cout&&setw(6)&&a[i]&&& &; &
if(i%10==0) cout&& &
Sqlist L; &
L.length=0; &
for(i=1;i&20001;i++) &
L.r[i].key=a[i];&
L.length++; &
system(&pause&); &
cout&&&Breaking Line Here......&&& &
MSort(L.r, L.r, 1, L.length); &
for(i=1;i&20001;i++) &
cout&&setw(6)&&L.r[i].key&&& &; &
if(i%10==0) cout&& &
}}------解决方案--------------------
栈溢出了，静态数组定义太大了，改用new吧。
------解决方案-------------------- TR2=new RedType[20000];new圆括号是只new了一个，而且初始化中括号是表示个数
------解决方案--------------------RedType* TR2 = new RedType[20000];动态申请数组时使用operator new[] （array new操作符）不是new()new RedType(20000);是用20000初始化变量RedType。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有归并排序动画，了解归并排序如何工作 - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 20时,
相比较于以前的排序动画，完善了归并排序动画，与大家分享
代码片段(7)
1.&[代码][Java]代码&&&&
private static void mergeSort(int[] data, int start,
if(start & end){
int mid = (start + end) / 2;
mergeSort(data, start, mid);
mergeSort(data, mid + 1, end);
merge(data, start, mid, end);
private static void merge(int[] data, int start, int mid, int end){
int capacity1 = mid - start + 1;
int capacity2 = end -
int dataRight[] = new int[capacity1 + 1];
int dataLeft[] = new int[capacity2 + 1];
int i, j = 0;
for(i = 0; i & capacity1; i++){
dataRight[i] = data[start + i];
dataRight[i] = 10000;
// 哨兵值，取一个比数据里面任何一个数都大的值
for(j = 0; j & capacity2; j++){
dataLeft[j] = data[mid + j + 1];
dataLeft[j] = 10000;
// 哨兵值，取一个比数据里面任何一个数都大的值
int indexA = 0;
int indexB = 0;
// notice the ArrayIndexOutofBounds, first we must check the indexA and indexB
for(int k = k & end + 1; k++){
if(dataRight[indexA] &= dataLeft[indexB] ){
data[k] = dataRight[indexA];
mergeHistogram.showHistogram(data, k);
Thread.sleep(20);
else if(dataRight[indexA] & dataLeft[indexB]){
data[k] = dataLeft[indexB];
mergeHistogram.showHistogram(data, k);
Thread.sleep(20);
mergeHistogram.showHistogram(data);
}catch(InterruptedException ex){
ex.printStackTrace();
Sorting_Animation.rar&~&5KB&&&&
3.&[图片] 归并排序1.png&&&&
4.&[图片] 归并排序2.png&&&&
5.&[图片] 归并排序3.png&&&&
6.&[图片] 归并排序4.png&&&&
7.&[图片] 归并排序5.png&&&&
开源中国-程序员在线工具：
开源从代码分享开始
wangdong20的其它代码【原创视频】归并排序_土豆_高清视频在线观看经典算法应用之1----归并排序（微软笔试题）
首先来看看原题
微软2010年笔试题
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定一数组，要求统计出该数组的逆序数对个数。
计算数列的逆序数对个数最简单的方便就最从前向后依次统计每个数字与它后面的数字是否能组成逆序数对。代码如下：
运行结果如下：
这种方法用到了双循环，时间复杂度为，是一个不太优雅的方法。因此我们尝试用其它方法来解决。
在《》中观察归并排序——合并数列，，与，的时候：
先取出前面数列中的。
然后取出后面数列中的，明显！这个和前面的，都可以组成逆序数对即和，和都是逆序数对。
然后取出前面数列中的。
然后取出后面数列中的，同理，可知这个和前面数列中的可以组成一个逆序数对。
这样就完成了逆序数对的统计，归并排序的时间复杂度是O(N *
LogN)，因此这种从归并排序到数列的逆序数对的解法的时间复杂度同样是O(N * LogN)，下面给出代码：
运行结果：
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}