高级排序算法详解

### 高级排序算法详解 #### 1. 快速排序的优化 快速排序是一种常用的排序算法，通常具有 $O(N*logN)$ 的时间复杂度。但在处理小规模分区时，传统的快速排序可能存在一些问题。 ##### 1.1 QuickSort2 方法 在某些情况下，使用 `manualSort()` 方法来处理包含三个或更少元素的子数组。当子数组只有一个元素（或更少）时，直接返回；如果范围是 2，则必要时交换单元格；如果范围是 3，则对三个单元格进行排序。因为中位数分区至少需要四个单元格，所以 `recQuickSort()` 例程不能用于对 2 或 3 的范围进行排序。 以下是相关代码示例： ```java 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 ``` `QuickSort2 Workshop` 小程序展示了使用三数取中分区的快速排序算法。与 `QuickSort1 Workshop` 小程序类似，但它首先对每个子数组的第一个、中间和最后一个元素进行排序，并选择这些元素的中位数作为枢轴值（前提是数组大小大于 3）。当对 100 个逆序排列的条进行排序时，性能有显著提升，子数组大致被分成两半，而不是像之前那样分成 1 个单元格和 $N - 1$ 个单元格。不过，在对随机数据进行排序时，它并不比 `QuickSort1` 快，其优势仅在排序有序数据时才明显。 ##### 1.2 处理小分区的方法 如果使用三数取中分区方法，快速排序算法对于三个或更少项的分区将不起作用，这里的数字 3 被称为截止点。 - **手动排序**：在之前的示例中，我们手动对包含两个或三个项的子数组进行排序。 - **插入排序**：另一种处理小分区的选择是使用插入排序。使用插入排序时，不受截止点为 3 的限制，可以将截止点设置为 10、20 或任何其他数字。可以通过实验不同的截止值，找到最佳性能。例如，`quickSort3.java` 程序使用插入排序来处理少于 10 个单元格的子数组。 以下是 `quickSort3.java` 程序的代码： ```java // quickSort3.java // demonstrates quick sort; uses insertion sort for cleanup // to run this program: C>java QuickSort3App //////////////////////////////////////////////////////////////// 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); // insertionSort(0, nElems-1); // the other option } //-------------------------------------------------------------- public void recQuickSort(int left, int right) { int size = right-left+1; if(size < 10) // insertion sort if small insertionSort(left, right); else // quicksort if large { long median = medianOf3(left, right); int partition = partitionIt(left, right, median); recQuickSort(left, partition-1); recQuickSort(partition+1, right); } } // end recQuickSort() //-------------------------------------------------------------- public long medianOf3(int left, int right) { int center = (left+right)/2; // order left & center if( theArray[left] > theArray[center] ) swap(left, center); // order left & right if( theArray[left] > theArray[right] ) swap(left, right); // order center & right if( theArray[center] > theArray[right] ) swap(center, right); swap(center, right-1); // put pivot on right return theArray[right-1]; // return median value } // end medianOf3() //-------------------------------------------------------------- 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( //------------- ```