快速排序实现2

这个算法实现中，对小的子数组使用插入排序，借此来提高性能。

Knuth推荐对小数组的切割点为9,正是程序中使用的值。实践中还需要根据测试请看选择更好的切割点。

 

import java.util.Random;

public class QuickSort2 {

    private long[] theArr;
    private int nElems;

    public QuickSort2(int max) {
        this.theArr = new long[max];
        this.nElems = 0;
    }

    public void insert(long value) {
        this.theArr[nElems++] = value;
    }

    public void display() {
        System.out.print("A=");
        for (int i = 0; i < nElems; i++) {
            System.out.print(theArr[i] + " ");
        }

        System.out.println();
    }

    public void quickSort() {
        this.recQuickSort(0, nElems - 1);
    }

    public void recQuickSort(int left, int right) {
        int size = right - left + 1;

        if (size <= 9) {
            // insert sort or sth. else.
            insertSort(left, right);
        } else {
            // quick sort
            long median = medianOf3(left, right);
            int partition = partitionIt(left, right, median);
            recQuickSort(left, partition - 1);
            recQuickSort(partition + 1, right);
        }
    }

    public void insertSort(int left, int right) {
        int in, out;
        for (out = left + 1; out <= right; out++) {
            long temp = theArr[out];
            in = out;

            while (in > left && theArr[in - 1] > temp) {
                theArr[in] = theArr[in - 1];
                --in;
            }
            theArr[in] = temp;
        }
    }

    /**
     * 因为使用了取头尾和中间点的中值作为枢纽点，并且在median3方法中
     * 已经对三个值进行了正确的排序，左右指针都不会越界，所以这里去除了对leftPtr &lt; right
     * 和rightPtr &gt; left的检测，稍微提高了性能。
     *
     */
    public int partitionIt(int left, int right, long pivot) {
        int leftPtr = left;
        int rightPtr = right - 1;
        while (true) {
            while (theArr[++leftPtr] < pivot) {
                //
            }

            while (theArr[--rightPtr] > pivot) {
                //
            }

            if (leftPtr >= rightPtr) {
                break;
            } else {
                swap(leftPtr, rightPtr);
            }
        }
        swap(leftPtr, right - 1);
        return leftPtr;
    }

    /**
     * 取三中值法，分别取头尾和中间的点，
     * 分别取得正确位置以后，再将中值放到最后一个位置进行快速排序。
     */
    public long medianOf3(int left, int right) {
        int center = (left + right) / 2;

        if (theArr[left] > theArr[center]) {
            swap(left, center);
        }

        if (theArr[left] > theArr[right]) {
            swap(left, right);
        }

        if (theArr[center] > theArr[right]) {
            swap(center, right);
        }

        swap(center, right - 1);
        return theArr[right - 1];
    }

    public void swap(int dex1, int dex2) {
        long temp = theArr[dex1];
        theArr[dex1] = theArr[dex2];
        theArr[dex2] = temp;
    }


    public static void main(String... args) {
        if (args.length < 1) {
            System.out.println("usage: java QuickSort2 number");
            return;
        }

        QuickSort2 qs = new QuickSort2(100);
        int count = Integer.parseInt(args[0]);
        Random rand = new Random();
        for (int i = 0; i < count; i++) {
            qs.insert(rand.nextInt(count * count));
        }
        qs.display();
        qs.quickSort();
        qs.display();
    }
}

 选取三中值是为了防止在极端情况下，比如每次选取的中值是所有数据中最大或者最小的情况，快速排序性能急剧下降。