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; 
    }