快速排序：枢轴选择与性能优化

### 快速排序：枢轴选择与性能优化 #### 1. 枢轴值的选择 在快速排序算法中，`partitionIt()` 方法需要选择一个合适的枢轴值。以下是一些相关要点： - 枢轴值应该是实际数据项的键值，该数据项称为枢轴。 - 可以大致随机地选择一个数据项作为枢轴，为了简单起见，我们总是选择要分区的子数组最右端的项作为枢轴。 - 分区完成后，如果将枢轴插入到左右子数组的边界处，它将处于最终的排序位置。 例如，有如下未分区数组： ```plaintext 94 42 89 63 12 36 27 78 3 50 ``` 选择最右端的 36 作为枢轴，分区后得到： ```plaintext 3 27 12 63 94 89 78 42 50 36 ``` 为了将枢轴移动到正确的位置，我们可以简单地交换枢轴（36）和右子数组的左项（63），这样枢轴就位于左右组之间的正确位置，且分区不受干扰。 #### 2. 枢轴选择的代码实现 为了将枢轴选择过程融入 `recQuickSort()` 方法，我们将其明确表示，并将枢轴值作为参数传递给 `partitionIt()` 方法，代码如下： ```java public void recQuickSort(int left, int right) { if(right - left <= 0) // if size <= 1, return; // already sorted else // size is 2 or larger { long pivot = theArray[right]; // rightmost item // partition range int partition = partitionIt(left, right, pivot); recQuickSort(left, partition - 1); // sort left side recQuickSort(partition + 1, right); // sort right side } } // end recQuickSort() ``` 当选择数组的最右端项作为枢轴时，需要修改 `partitionIt()` 方法，将最右端项排除在分区过程之外。分区完成后，需要将枢轴从右端交换到分区位置。以下是完整的 `quickSort1.java` 程序： ```java // quickSort1.java // demonstrates simple version of quick sort // to run this program: C>java QuickSort1App //////////////////////////////////////////////////////////////// class ArrayIns { private long[] theArray; // ref to array theArray private int nElems; // number of data items //-------------------------------------------------------------- public ArrayIns(int max) // constructor { theArray = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { theArray[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { System.out.print("A="); for(int j = 0; j < nElems; j++) // for each element, System.out.print(theArray[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void quickSort() { recQuickSort(0, nElems - 1); } //-------------------------------------------------------------- public void recQuickSort(int left, int right) { if(right - left <= 0) // if size <= 1, return; // already sorted else // size is 2 or larger { long pivot = theArray[right]; // rightmost item // partition range int partition = partitionIt(left, right, pivot); recQuickSort(left, partition - 1); // sort left side recQuickSort(partition + 1, right); // sort right side } } // end recQuickSort() //-------------------------------------------------------------- public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; // left (after ++) int rightPtr = right; // right-1 (after --) while(true) { // find bigger item while( theArray[++leftPtr] < pivot ) ; // (nop) // find smaller item while(rightPtr > 0 && theArray[--rightPtr] > pivot) ; // (nop) if(leftPtr >= rightPtr) // if pointers cross, break; // partition done else // not crossed, so swap(leftPtr, rightPtr); // swap elements } // end while(true) swap(leftPtr, right); // restore pivot return leftPtr; // return pivot location } // end partitionIt() //-------------------------------------------------------------- public void swap(int dex1, int dex2) // swap two elements { long temp = theArray[dex1]; // A into temp theArray[dex1] = theArray[dex2]; // B into A theArray[dex2] = temp; // temp into B } // end swap( //-------------------------------------------------------------- } // end class ArrayIns //////////////////////////////////////////////////////////////// class QuickSort1App { public static void main(String[] args) { int maxSize = 16; // array size ArrayIns arr; arr = new ArrayIns(maxSize); // create array for(int j = 0; j < maxSize; j++) // fill array with { // random numbers long n = (int)(java.lang.Math.random() * 99); arr.insert(n); } arr.display(); // display items arr.quickSort(); // quicksort them arr.display(); // display them again } // end main() } // end class QuickSort1App ``` 该程序的 `main()` 方法创建了一个 `ArrayIns` 对象，插入 16 个随机长整型数据项，显示数组，使用 `quickSort()` 方法进行排序，然后再次显示结果。 #### 3. 代码优化分析 在 `partitionIt()` 方法的代码中，我们能够移除第一个内部 `while` 循环中对数组末尾的测试（`leftPtr < right`）。这是因为我们选择了最右端项作为枢轴，所以 `leftPtr` 总会在那里停止。然而，第二个 `while` 循环中对 `rightPtr` 的测试仍然是必要的。选择最右端项作为枢轴并非完全随机的选择，它通过移除不必要的测试来加快代码速度，从其他位置选择枢轴则无法提供此优势。 #### 4. QuickSort1 工作坊小程序 通过 QuickSort1 工作坊小程序，我们可以更直观地了解快速排序算法。 - **整体概览**：使用 `Size` 按钮将小程序设置为对 100 个随机条进行排序，按下 `Run` 按钮。排序过程完成后，显示大致如下：  观察算法如何将数组划分为两部分，然后对每一部分再进行划分和排序，创建越来越小的子数组。排序完成后，每条虚线提供了一个已排序子数组的可视化记录，虚线的水平范围显示了哪些条属于该子数组，其垂直位置是枢轴值。 - **详细步骤**：切换到 12 条显示并逐步执行排序过程，可以看到枢轴值与数组右侧枢轴的高度相对应，算法如何对数组进行分区、将枢轴交换到两个已排序组之间的空间、对较短的组进行排序（使用许多递归调用），然后