java - 最好的 Java 快速排序？

Question

我见过很多快速排序算法，我想知道这两者之间的区别是什么，是否还有更简单的算法。除了一个用于 ints 而另一个用于 chars 之外......

这是第一个:

public class MyQuickSort {

private int array[];
private int length;

public void sort(int[] inputArr) {

    if (inputArr == null || inputArr.length == 0) {
        return;
    }
    this.array = inputArr;
    length = inputArr.length;
    quickSort(0, length - 1);
}

private void quickSort(int lowerIndex, int higherIndex) {

    int i = lowerIndex;
    int j = higherIndex;
    // calculate pivot number, I am taking pivot as middle index number
    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    // Divide into two arrays
    while (i <= j) {
        /**
         * In each iteration, we will identify a number from left side which
         * is greater then the pivot value, and also we will identify a number
         * from right side which is less then the pivot value. Once the search
         * is done, then we exchange both numbers.
         */
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchangeNumbers(i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSort(lowerIndex, j);
    if (i < higherIndex)
        quickSort(i, higherIndex);
}

private void exchangeNumbers(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void main(String a[]){

    MyQuickSort sorter = new MyQuickSort();
    int[] input = {24,2,45,20,56,75,2,56,99,53,12};
    sorter.sort(input);
    for(int i:input){
        System.out.print(i);
        System.out.print(" ");
    }
  }
 }

第二个:

class Quicksort{
static void qsort(char items[]){
    qs(items, 0, items.length-1);
}

//a recursive version of Quicksort for characters
private static void qs(char items[], int left, int right){
    int i, j;
    char x, y;

    i = left; j = right;
    x = items[(left+right)/2];

    do{
        while((items[i] < x) && (i < right)) i++;
        while((x < items[j]) && (j > left)) j--;

        if(i <= j){
            y = items[i];
            items[i] = items[j];
            items[j] = y;
            i++; j--;
        }
    } while(i <= j);

    if(left < j) qs(items, left, j);
    if(i < right) qs(items, i, right);
 }
}

public class QSDemo {
public static void main(String[] args) {

    char a[] = { 'd', 'x', 'a', 'r', 'p', 'j', 'i' };
    int i;

    System.out.println("Original array: ");
    for(i = 0; i < a.length; i++)
        System.out.print(a[i]);

    System.out.println();

    //now, sort the array
    Quicksort.qsort(a);

    System.out.println("Sorted array: ");
    for(i = 0; i < a.length; i++)
        System.out.print(a[i]);

    }
}

Answer 1

快速排序的性能如何主要取决于主元的选择。如果你完美地选择它们，你有 O(n log n) 这也是平均情况，但最坏的情况是 O(n^2)。因此，对于大数组，采用最佳策略选择枢轴的实现将优于其他实现，但对于小数组来说可能是一种开销。选择支点的好策略是什么？这取决于问题和您期望的数据。所以问这个问题类似于问哪种是“最好的”编程语言，答案是:这取决于问题。如果您正在寻找真正通用的方法，那么有一些策略可以减少糟糕的枢轴选择的概率，但它们并不能保证。或类似 Introsort 的混合动力车.