用一個循環寫一個快速排序

Question

我的兄弟希望我只通過一個循環來優化我的代碼。我看不到Quicksort只能有一個循環並工作。 （他告訴我要去掉內環）

public class QuickSort { 
public static void Quick(int[] target, int lo, int hi) { 
    if (lo >= hi) { 
     return; 
     } 
    Random numberGenerator = new Random(); 
    int pivot = numberGenerator.nextInt(hi-lo)+lo; 
    int pivotValue = target[pivot]; 
    target[pivot]=target[hi]; 
    target[hi]=pivotValue; 
    pivot=hi; 
    int counter; 
    for(counter=lo; counter<pivot ; counter++){ 
     while(target[counter]>target[pivot]){ 
      if(pivot-counter==1){ 
       int temp=target[counter]; 
       target[counter]=target[pivot]; 
       target[pivot]=temp; 
       //return; //possibly the problem 
      } 
      else{ 
       int temp1 = target[pivot-1]; 
       int temp2 = target[pivot]; 
       target[pivot]=target[counter]; 
       target[pivot-1]=temp2; 
       target[counter]=temp1; 
       pivot=pivot-1; 
      } 
     } 
    } 
    Quick(target, lo, counter-1); 
    Quick(target, counter, hi); 
} 

public static void main(String[] args) { 
    int sizeOfArray = 10; 
    int numberOfTests = 1000; 

    int numFailed = 0; 
    for (int i = 0; i < numberOfTests; i++) 
    { 
     int[] iNeedSorting = new int[sizeOfArray]; 
     populateArrayWithRandomNums(iNeedSorting); 
     //System.out.printf("Test #%d\n", i); 
     //System.out.printf("Original Array: %s\n", intArrayToString(iNeedSorting)); 
     Quick(iNeedSorting, 0, iNeedSorting.length-1); 

     if (!isSorted(iNeedSorting)) {numFailed++;} 
     //System.out.printf("New Array: %s\n\n", intArrayToString(iNeedSorting)); 
    } 
    System.out.printf("%d test failed\n\n", numFailed); 
} 

}

Answer 1

據學者（或至少是我學習，我也做了一個快速檢查，以數據結構和算法的書快速排序算法），快速排序是關於遞歸。對數據集進行分區（需要一個循環），然後對其左側和右側進行遞歸排序。

Answer 2

快速排序在概念上是兩個循環：遍歷整個數組的內部分區循環，以及通常通過遞歸表示的外部循環循環。在這裏，你以經典的方式完成了部門部分，但是你的分區有點複雜。

您的外部for循環將計數器向左移動一步（假設您從左向右編寫數組）。您的內圈for循環將向右移動一個步驟（除非計數器幾乎到達樞軸並且進行最終交換的特殊情況除外）。沒有任何東西可以將櫃檯向右移回或向左轉回。所以你不會因爲兩個循環而做額外的工作，這是一個清晰而不是效率的問題。

寫入分區的一種常見方法是使用帶有兩個計數器而不是一個計數器的單個循環。一個計數器就是你使用的計數器：它的左邊的一切都小於數據透視。另一個計數器扮演着一個對稱角色：它右側的所有內容都大於主鍵。循環體中執行以下操作：

• 如果兩個target[left_counter]和target[right_counter]正在外的地方，交換他們;在此之後target[left_counter]和target[right_counter]位於陣列的所需側，因此增量爲left_counter並遞減right_counter;

• 否則：如果target[left_counter]位於期望的一側，則增量爲left_counter;如果target[right_counter]位於期望的一側，則遞減right_counter。

當計數器交叉時，循環終止。它最終會終止，因爲至少有一個計數器在每次迭代中移動。