这个快速排序哪错了(*´I`*)

Question

#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]<<"  ";
        }
}

Answer 1

该回答引用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;
}