#include <iostream>
using namespace std;
#include <ctime>
#define N 99
void swap(int arr[],int a,int b);
int* partition(int arr[],int L,int R);
void quickSort(int arr[],int L,int R)
{
if(L<R)
{
srand(time(NULL));
float a=rand()%(N+1)/(float)(N+1);
swap(arr,L+(int)(a*(R-L+1)),R);
cout<<L+(int)(a*(R-L+1))<<endl;
int* q=partition(arr,L,R);
quickSort(arr,L,q[0]-1);
quickSort(arr,q[1]+1,R);
}
}
int* partition(int arr[],int L,int R)
{
int less=L-1;
int more=R;
while(L<more)
{
if(arr[L]<arr[R])
{
swap(arr,++less,L++);
}else if(arr[L]>arr[R])
{
swap(arr,--more,L);
}else
{
L++;
};
}
swap(arr,more,R);
int num[2]={less+1,more};
int* p=NULL;
if(p!=NULL)
{
delete p;
p=NULL;
}
p=new int(sizeof(num)/sizeof(num[0]));
p=num;
return p;
};
void swap(int arr[],int a,int b)
{
arr[a]=arr[a]+arr[b];
arr[b]=arr[a]-arr[b];
arr[a]=arr[a]-arr[b];
}
int main(int argc,char** argv)
{
int arr[]={3,2,5,8,1,2,3,1,4,3,7,1};
int num=sizeof(arr)/sizeof(int);
quickSort(arr,0,num-1);
for(int i = 0;i < num;i++) {
cout<<arr[i]<<" ";
}
}
这个快速排序哪错了(*´I`*)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- MarkHan_ 2023-02-20 18:16关注
该回答引用ChatGPT
在你的代码中,有两个问题导致了程序出错:
1.在 partition 函数中,你使用了一个指针 p,在最后返回时将一个动态分配的内存地址赋值给了它。但是在分配内存时,你使用了 new int(sizeof(num)/sizeof(num[0])),这样分配出来的内存大小是 4,而不是你希望的数组大小 2。所以在返回时,你只返回了 num 数组中的前两个元素,导致数组无法正确分段。你可以直接返回一个 new int[2] 分配出来的空间来解决这个问题。
2.在使用 srand 函数时,应该在程序开头使用一次即可,而你在递归调用的时候,每次都调用一次 srand,导致生成的随机数不太随机。为了避免这种情况,你可以在程序开头使用 srand 函数,然后在调用 rand 生成随机数时,使用 L + rand() % (R-L+1) 来生成一个随机数,这样可以避免重复生成相同的随机数。
下面是修改后的代码,你可以参考一下:
#include <iostream> #include <cstdlib> #include <ctime> using namespace std; void swap(int arr[], int a, int b); int* partition(int arr[], int L, int R); void quickSort(int arr[], int L, int R) { if(L < R) { float a = (float)rand() / RAND_MAX; swap(arr, L + (int)(a*(R-L+1)), R); int* q = partition(arr, L, R); quickSort(arr, L, q[0]-1); quickSort(arr, q[1]+1, R); delete[] q; } } int* partition(int arr[], int L, int R) { int less = L - 1; int more = R; while(L < more) { if(arr[L] < arr[R]) { swap(arr, ++less, L++); } else if(arr[L] > arr[R]) { swap(arr, --more, L); } else { L++; } } swap(arr, more, R); int* p = new int[2]; p[0] = less + 1; p[1] = more; return p; } void swap(int arr[], int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } int main() { int arr[] = {3, 2, 5, 8, 1, 2, 3, 1, 4, 3, 7, 1}; int num = sizeof(arr) / sizeof(int); srand(time(NULL)); quickSort(arr, 0, num - 1); for(int i = 0; i < num; i++) { cout << arr[i] << " "; } cout << endl; return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报 编辑记录
悬赏问题
- ¥100 set_link_state
- ¥15 虚幻5 UE美术毛发渲染
- ¥15 CVRP 图论 物流运输优化
- ¥15 Tableau online 嵌入ppt失败
- ¥100 支付宝网页转账系统不识别账号
- ¥15 基于单片机的靶位控制系统
- ¥15 真我手机蓝牙传输进度消息被关闭了,怎么打开?(关键词-消息通知)
- ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
- ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
- ¥15 手机接入宽带网线,如何释放宽带全部速度