Inplace quick sort

Question

編寫一個java程序，使用'in place'排序整數列表Quicksort算法。

每次使用java.util.Random類隨機生成列表。 允許用戶選擇陣列的大小。程序應該顯示使用不同的數據透視選項對該大小的數組進行排序的結果。尤其是，嘗試這些4個選擇 -

首先元件作爲樞軸
隨機選擇所述樞轉元件
選擇3種隨機選擇的元素的中間值作爲樞軸
平均第一中心和最後一個元素的（書技術）。

請不要給我實施，因爲我想自己嘗試。我想知道什麼是就地快速排序？它與常規quiksort有什麼不同？它是常規快速排序嗎？我很困惑。我希望有人提供純英文的簡碼或解釋也會有所幫助。

Answer 1

就地分揀 - 這是當你來自外部，給你，而不是創造一些新的陣列和以任何方式使用它們原來的陣列，上運行。就地分揀花費O（1）的空間，而不是爲O（n）+使用時附加的數據structres

實施例的就地排序：

public static void simpleBubbleSort(int[] arr) { 
     for (int i = 0; i < arr.length; i++) { 
      for (int j = 1; j < arr.length; j++) { 
       if (arr[j - 1] > arr[j]) { 
        swap(arr, j - 1, j); 
       } 
      } 
     } 
    } 

與之相對排序合併沿着方式創建陣列，並且最後將它們組合起來並返回NOT而不是原來的（給予我們的）數組，而是包含結果的數組。

public static int[] mergeSort(int[] arr) { 
     if (arr.length < 2) return arr; 

     int mid = arr.length/2; 
     int[] left = new int[mid]; 
     int[] right = new int[mid + arr.length % 2]; 

     int j = 0; 
     for (int i = 0; i < arr.length; i++) { 
      if (i < mid) { 
       left[i] = arr[i]; 
      } else { 
       right[j++] = arr[i]; 
      } 
     } 
     // keeps going until there's 1 element in each array[] 
     return mergeReturn(mergeSort(left), mergeSort(right)); 
    } 

    private static int[] mergeReturn(int[] leftArr, int[] rightArr) { 
     int leftPointer = 0, rightPointer = 0, combinedSize = leftArr.length + rightArr.length; 
     int[] merged = new int[combinedSize]; 

     for (int i = 0; i < combinedSize; i++) { 
      if (leftPointer < leftArr.length && rightPointer < rightArr.length) { 
       if (leftArr[leftPointer] < rightArr[rightPointer]) { 
        merged[i] = leftArr[leftPointer++]; 
       } else { 
        merged[i] = rightArr[rightPointer++]; 
       } 
      } else if (leftPointer < leftArr.length) { // adding the last element 
       merged[i] = leftArr[leftPointer++]; 
      } else { 
       merged[i] = rightArr[rightPointer++]; 
      } 
     } 
     return merged; 
    }