用一个循环写一个快速排序

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。

当计数器交叉时，循环终止。它最终会终止，因为至少有一个计数器在每次迭代中移动。