二路归并排序 谁能告诉我错哪里了吗？
#include "stdafx.h"
#include "iostream"
#define NUM 8
using namespace std;
void merge(int *a,int head,int tail)
{
int b[20];
int i = head;
int t = tail;
int mid = tail/2;
int j = tail/2+1;
int k = 0;
while(i<=mid && j<=t)
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;
}
else{
b[k] = a[j];
j++;
}
k++;
}
while(i<=mid){
b[k] = a[i];
i++;
k++;
}
while(j<=t){
b[k]=a[j];
k++;
j++;
}
for(i = head,k = 0;i<=tail;i++,k++)
a[i] = b[k];
//return b;
}
void merge_sort(int *a,int head,int tail)
{
int mid;
if(head<tail){
mid = (head+tail)/2;
merge_sort(a,head,mid);
merge_sort(a,mid+1,tail);
merge(a,head,tail);
}
}
int _tmain(int argc, _TCHAR *argv[])
{
int a[]={4,5,7,1,2,3,6,7,8,9,10,45,2};
//quick_sort(a,0,8);
//bubble_sort(a,0,5);
merge_sort(a,0,12);
for(int i =0 ;i<=12;i++)
cout<<a[i]<<" ";
return 0;
}
[解决办法]
http://topic.csdn.net/u/20090705/23/84cc02da-676d-44aa-a619-7936f30ab2e6.html
以前写的，参考：
- C/C++ code
#pragma warning(disable:4786)#include <iostream> #include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#include <math.h>using namespace std;const int NUM=20;int arr[] = {1,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};void merge(int v[],int left,int mid,int right) //合并[left,mid]和[mid+1,right]{ int i,j,k=0; i=left; //i为第一路的下标 j=mid+1; //j为第二路的下标 int *temp=new int[right-left+1]; while(i<=mid&&j<=right) temp[k++]=(v[i]<=v[j])?v[i++]:v[j++]; //依次合并2路到temp数组 while(i<=mid) temp[k++]=v[i++]; while(j<=right) temp[k++]=v[j++]; for(i=left,j=0;i<=right;++i,++j) //合并完数据写回v数组 v[i]=temp[j]; delete []temp;}void merge_sort(int v[],int num){ int i,size,j,mid,right; for(i=1;i<num;i*=2) //log(n)趟归并 { size=i-1; j=0; while(j<num) { mid=j+size; right=j+2*size+1; if(mid>=num) //下标不能溢出 mid=num-1; if(right>=num) right=num-1; merge(v,j,mid,right); j=right+1; } }}void main(){ int j; merge_sort(arr, NUM); for(j=0; j<NUM; j++) printf("%d ", arr[j]); printf("\n");}
[解决办法]