java - 通过修改也具有平均 O(n) 时间复杂度的快速排序来查找数组的介质

Question

请帮我。我需要修改平均时间复杂度为 O(n) 的快速排序，它只对数组的一半进行排序，因为我只是想找到数组的介质。

在进行任何更改之前，这是我的快速排序算法：

   static void swap(int[] arr, int i, int j){
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
  
   static int partition(int[] arr, int low, int high){
      int pivot = arr[high]; 
      int i = (low - 1); 
   
      for(int j = low; j <= high - 1; j++){
         if (arr[j] < pivot) {
            i++; 
            swap(arr, i, j);
         }
      }
      swap(arr, i + 1, high);
      return (i + 1);
   }
  
   static void quickSort(int[] arr, int low, int high){
      if (low < high) {
         int pi = partition(arr, low, high);
         quickSort(arr, low, pi - 1);
         quickSort(arr, pi + 1, high);
      }
   }

标签： javaarrayssortingrecursiontime-complexity