leetcode存在重复元素快速排序实现总结

昨天写了leetcode存在重复元素问题，一开始暴力求解用两个for循环，时间复杂度太高了，想了想用快速排序，看了题解，题解直接调用c语言的qsort函数，于是手写了一个简单的快速排序算法，一开始栈上溢，发现是快速排序传入参数，数组的长度numsize直接作为数组的最后一个元素

bool containsDuplicate(int* nums, int numsSize){
quicksort(nums,0,numsSize);

后来在quicksort内修改

int temp;
        int i=low,j=high-1;
        if(low 
发现输出结果，基准值右边的两个数不会调换次序
 
如：输入{0，3，4，1，6，5}
得到输出{0，3，1，4，5，6}
 
最后发现原来是j=high-1，每次递归会使high-1，
 当最后一个子数组只剩2个元素时，high-1=low，使得最后的数组元素不会比较大小直接返回上次递归
 
修改后提交代码如下
 
void quicksort(int nums[],int low,int high){
        int temp;
        int i=low,j=high;
        if(lowi&&nums[j]>=temp)j--;
                if(j>i){
                nums[i]=nums[j];
                i++;
                }
                while(i 
提交时间复杂度还是太高，就像能不能在快速排序的时候就进行判断，如果排序时候遇到相同的数直接返回ture，这里一开始写返回false但是最后递归的时候深层的递归返回不会结束整个递归，只是结束当前递归返回上次递归，而最后的结果会被最上层的递归覆盖掉，于是加了if判断，若下层递归为ture及存在重复元素，直接返回ture，
 代码如下
 
#include 
#include 
bool quicksort(int nums[],int low,int high){
        int temp;
        int i=low,j=high;
        if(lowi&&nums[j]>=temp){
                if(nums[j]==temp)
                {
                    return true;
                }
                j--;
                }
                
                if(j>i){
                nums[i]=nums[j];
                i++;
                }
                while(i 
结果提交时间还是超了，这里对快速排序的优化并不能提高快速排序的平均复杂度nlogn，当数组很大且重复的数出现在靠后位置时，只是省略了快速排序后的单次循环，而快速排序本身的时间复杂度趋向n^2.
 
 
 
在最优情况下，每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为 [log2n]+1（ [x] 表示不大于 x 的最大整数），即仅需递归 log2n 次，需要时间为T（n）的话，第一次应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
 
 
 
 
快速排序最坏情况
 当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为
 ，最终其时间复杂度为O(n^2)。
 
 
很纳闷，于是查看了c语言提供的qsort源码，发现qsort并不是简单的快速排序，而是在快速排序的基础上进行了优化。
 
还是太年轻了。