java - 最好的Java Quicksort？

我见过很多快速排序算法，我想知道这两种算法之间的区别是什么，如果有更多的，也许更简单的算法。除了一个是整数，另一个是字符…
这是第一个：

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]);

    }
}

最佳答案

快速排序的性能如何主要取决于轴的选择如果你完美地选择了它们，你就得到了o（n logn），这也是平均情况，但最坏的情况是o（n^2）。因此，对于大型阵列，具有最佳支点选择策略的实现将优于其他实现，但对于小型阵列，这可能是一个开销选择支点的好策略是什么？这取决于问题和您期望的数据。所以问这个问题类似于问哪个是“最好的”编程语言，答案是：这取决于问题。如果您正在寻找真正的通用方法，那么有一些策略可以减少糟糕的轴心点选择的可能性，但它们不能保证这一点。或者像Introsort这样的混血儿。