C++ 分治法排序

答案:5 悬赏:50

解决时间 2021-02-24 05:43

提问者网友：放荡不羁
2021-02-23 05:57

给1 2 2 3 4 5 3 4 排序，需要用C++,一定要用分治法排序，越简单越好。还会加分的

最佳答案

二级知识专家网友：没感情的陌生人
2021-02-23 06:59

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef int* IntPtr;
void Merge(int A[],int p,int q,int r)
{
int M=999999999;
int n1,n2;
n1=q-p+1;
n2=r-q;
IntPtr L,R;
L=new int[n1+1];
R=new int[n2+1];
int i,j,k;
for(i=1;i<=n1;i++)
L[i]=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=M;
R[n2+1]=M;
i=1;
j=1;

for (k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
A[k]=L[i];
i++;
}
else
{
A[k]=R[j];
j++;
}
}
}

void Mergesort(int A[],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
Mergesort(A,p,q);
Mergesort(A,q+1,r);
Merge(A,p,q,r);
}
}

void main()
{
int A[10];
srand(time(0));
for (int i=0;i<10;i++)
{
A[i]=rand();
cout<<A[i]<<endl;
}
cout<<endl;
Mergesort(A,0,9);
for (int j=0;j<10;j++)
{

cout<<A[j]<<endl;
}
}
看看怎样

全部回答

1楼网友：虚伪的现实
2021-02-23 11:05

// 利用Stl三行代码就收工了 #include <algorithm> #include <iostream> void main() { int arrInt[] = {1, 2, 2, 3, 4, 5, 3, 4}; std::sort(arrInt, arrInt + sizeof(arrInt)/sizeof(arrInt[0])); std::copy(arrInt, arrInt + sizeof(arrInt)/sizeof(arrInt[0]), std::ostream_iterator<const int>(std::cout, " ")); } // 说明: // stl排序函数内部混合使用了二分排序,插入排序,堆排序三种方式 // 如果排序数量超过限制(默认为32个元素),将使用二分排序 // 如果如果二分区间小于0,则采用堆排序 // 元素较少直接使用插入排序 // 这样做的目的在于提高排序的效率 // stl是模板库,里面所有的算法都是开源的,你可以看看她的实现,祝你成功

2楼网友：野心和家
2021-02-23 09:39

#include <iostream> using namespace std; void merge(int temp[],int a[],int left,int right,int middle) { int index1; int index2; int i,j,k; for(i=left;i<=middle;i++)//将待排序数组的左半部分赋值给中间数组的左半部分 temp[i]=a[i]; for(j=1;j<=right-middle;j++)//将待排序数组的右半部分按照逆序方式赋值给中间数组的右半部分 temp[right-j+1]=a[middle+j]; for(index1=left,index2=right,k=left;k<=right;k++)//从中间的数组的做边界和右边界同时有序赋值给待排序数组，不用考虑数组边界问题 { if(temp[index1]<temp[index2]) a[k]=temp[index1++]; else a[k]=temp[index2--]; } } void mergesort(int d[],int s[],int left,int right) { if(left<right) { int mid=(left+right)/2; mergesort(d,s,left,mid); //递归排序左半部分 mergesort(d,s,mid+1,right); //递归排序右半部分 merge(d,s,left,right,mid); //合并已排序好的左右两半部分 } } int main() { int d[4] ; int s[4] = {4,1,5,3}; mergesort(d,s,0,3); //函数调用 for(int i = 0; i < 4; i++) //数组输出 cout << s[i] << endl; getchar(); return 0; }

3楼网友：糜废丧逼
2021-02-23 08:14

分治法解决排序问题：vc6.0中运行正确. #include <iostream> #include <sys/timeb.h> using namespace std; void Merge(int *str,int p,int q,int r) { int n1,n2,i,j,k; n1=q-p+1; n2=r-q; int *Left=new int[n1+1],*Right=new int[n2+1]; for(i=0;i<n1;i++) Left[i]=str[p+i]; for(i=0;i<n2;i++) Right[i]=str[q+i+1]; for(i=j=0,k=p;k<=r;k++) if(i==n1) { while(k<=r) str[k++]=Right[j++]; break; } else if(j==n2) { while(k<=r) str[k++]=Left[i++]; break; } else if(Left[i]<=Right[j]) str[k]=Left[i++]; else str[k]=Right[j++]; } void MergeSort(int *str,int p,int r) { int q; if(p<r) { q=(p+r)/2; MergeSort(str,p,q); MergeSort(str,q+1,r); Merge(str,p,q,r); } } int main() { int str[10]={2,55,3,545,2,56,77,5,0,6},i; timeb t1,t2; ftime(&t1); cout<<"排序前:"; for(i=0;i<10;i++) cout<<str[i]<<" "; cout<<endl; MergeSort(str,0,9); cout<<"排序后:"; for(i=0;i<10;i++) cout<<str[i]<<" "; cout<<endl; ftime(&t2); cout<<"The total time:"<<(t2.time-t1.time)*1000+(t2.millitm-t1.millitm)<<endl; return 0; }

4楼网友：狠傷凤凰
2021-02-23 07:15

你这题很巧，你用二分法递归排序，最后会只剩下两个相邻的元素，而不会重叠指向一个元素，所以high - low == 0这一句始终不成立，造成死循环。加以个条件就好了 #include using namespace std; //要先写第一个元素的值为0的排除子函数，没写。 int arrange(int a[],int low,int high) { int flag=0; int mid =(low+high)/2; if((high-low)==0 || (high - low) == 1) //二分法排序的最后两种可能 { if(a[mid]==mid) return a[mid]; else return 0; } int left; int right; left=arrange(a,low,mid); //向左 right=arrange(a,mid,high); //向右 if(left||right) //整合，有一个非0就是找到值了 return left+right; else return 0; } int main() { int a[]={-8,-5,-2,-1,2,5,8,10,18,21}; int result; result=arrange(a,1,10); cout<

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！