algorithm - 这个快速排序实现的时间复杂度是 O(n log n) 的最坏情况吗？

Question

我想说它最差的时间复杂度仍然是 n log n。仅仅因为我使用中间元素作为枢轴，所以即使数组已经排序，当它从分区方法返回时，它仍然是数组的一半。我可能是错的，我的 DS 不是最好的

 public static void quicksort(int [] arr, int low, int high){
      if(low < high){
          int pivot = partition(arr, low, high);
          quicksort(arr, low, pivot);
          quicksort(arr, pivot+1, high);
        }
    }

 public static int partition(int [] arr, int low, int high){
     
        int i = low; 
        int j = high;
        int mid = low + (high-low)/2;
        int pivot = arr[mid];
       
        while(true){
           while(arr[i] < pivot){
               i++;
           }
           while(arr[j] > pivot){
               j--;
           } 
            

        if( i >= j) return j;
            
        swap(arr, i, j);
        i++;
        j--;  
         
    }
 }

标签： algorithmsortingbig-oquicksort

Answer 1