快速排序显示超出时间限制

Question

int partitions(int *a,int low,int high);

void quickSort(int* a,int low,int high){

    if(low<high){

        int piv=partitions(a,low,high);//划分

        quickSort(a,low,piv-1);

        quickSort(a,piv+1,high);

    }else return;

}

int partitions(int *a,int low,int high){

    //一次划分

  // int idx=low+rand()%(high-low+1);

   // swap(&a[low],&a[idx]);

    //假定每次都取a[low]进行划分

    int x=a[low];

    while(low<high){

        while(low<high&&a[high]>=x) --high;

        if(low<high){

            a[low]=a[high];

            // swap(&a[low],&a[high]);

            //low++;

        }//把比x小的数放到左边

        while(low<high&&a[low]<=x) ++low;

        if(low<high){

            a[high]=a[low];

           // swap(&a[low],&a[high]);

          //  high--;

        }//把比x大的数放到右边

    }

    a[low]=x;

    return low;

}

bool containsDuplicate(int* nums, int numsSize) {

quickSort(nums,0,numsSize-1);

for(int i=1;i<numsSize;i++){

    if(nums[i]==nums[i-1]) return true;

}

return false;

}
为什么假定每次low位置为枢纽的快排解决会显示超出时间限制，但是使用随机枢纽就能够通过呢

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

在假定每次都取a[low]作为枢纽的快速排序中，如果输入数组已经是有序的情况下（最好的情况），每次的划分都只能将数组分成一个较小的部分和一个较大的部分，而不会实现均匀地将数组划分成两部分，这样会导致快速排序的时间复杂度退化为O(n^2)。而使用随机选择枢纽的方式能够减少最坏情况的出现概率，保证每次划分的均衡性，避免出现时间复杂度过高的情况。这也是为什么使用随机枢纽能够通过时间限制的原因。 以下是对应的实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int partitions(int *a, int low, int high);
void quickSort(int* a, int low, int high){
    if(low < high){
        int piv = partitions(a, low, high); //划分
        quickSort(a, low, piv-1);
        quickSort(a, piv+1, high);
    }
}
int partitions(int *a, int low, int high){
    int x = a[low];
    while(low < high){
        while(low < high && a[high] >= x) --high;
        if(low < high){
            a[low] = a[high];
            ++low;
        }
        while(low < high && a[low] <= x) ++low;
        if(low < high){
            a[high] = a[low];
            --high;
        }
    }
    a[low] = x;
    return low;
}
bool containsDuplicate(int* nums, int numsSize) {
    quickSort(nums, 0, numsSize-1);
    for(int i = 1; i < numsSize; i++){
        if(nums[i] == nums[i-1]) return true;
    }
    return false;
}

希望能够帮助到您。