Java排序算法大全，java排序算法,7种内部排序的Java语

Java排序算法大全，java排序算法,7种内部排序的Java语

7种内部排序的Java语言描述，使用泛型。

Java 内部排序

/** *  */package alg.sort;/** * @author ZhangY *  */public class Sort{    private static int CUTOFF = 10;    /**     * Simple insertion sort     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void insertionSort(T[] a)    {        insertionSort(a, 0, a.length - 1);    }    /**     * Simple bubble sort     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void bubbleSort(T[] a)    {        for (int i = 0; i < a.length - 1; i++) // the last one is no need for                                                // comparing to itself        {            for (int j = a.length - 1; j > i; j--)            {                if (a[j].compareTo(a[j - 1]) < 0)                {                    swapReferences(a, j, j - 1);                }            }        }    }    /**     * Shell sort, using Shell's (poor) increments.     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void shellSort(T[] a)    {        int j;        for (int gap = a.length / 2; gap > 0; gap /= 2)        {            for (int i = gap; i < a.length; i++)            {                T tmp = a[i];                for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap)                {                    a[j] = a[j - gap];                }                a[j] = tmp;            }        }    }    /**     * Simple selection sort     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void selectionSort(T[] a)    {        for (int i = 0; i < a.length - 1; i++)        {            int minIdx = i;            for (int j = i + 1; j < a.length; j++)            {                if (a[j].compareTo(a[minIdx]) < 0)                    minIdx = j;            }            if (minIdx != i)            {                swapReferences(a, i, minIdx);            }        }    }    /**     * Standard heap sort     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void heapSort(T[] a)    {        for (int i = a.length / 2; i >= 0; i--) /* buildHeap */        {            percDown(a, i, a.length);        }        for (int i = a.length - 1; i > 0; i--)        {            swapReferences(a, 0, i); /* deleteMax */            percDown(a, 0, i);        }    }    /**     * Merge sort algorithm     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void mergeSort(T[] a)    {        @SuppressWarnings("unchecked")        T[] tmpArray = (T[]) new Comparable[a.length];        mergeSort(a, tmpArray, 0, a.length - 1);    }    /**     * Quick sort algorithm     *      * @param a     *            an array of Comparable items     */    public static <T extends Comparable<? super T>> void quickSort(T[] a)    {        quickSort(a, 0, a.length - 1);    }    /**     * Internal method for heap sort that is used in deleteMax an buildHeap     *      * @param a     *            an array of Comparable items.     * @param i     *            the position from which to percolate down.     * @param n     *            the logical size of binary heap.     */    private static <T extends Comparable<? super T>> void percDown(T[] a,            int i, int n)    {        int child;        T tmp;        for (tmp = a[i]; leftChild(i) < n; i = child)        {            child = leftChild(i);            if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0)                child++;            if (tmp.compareTo(a[child]) < 0)                a[i] = a[child];            else                break;        }        a[i] = tmp;    }    /**     * Internal method for heap sort.     *      * @param i     *            the index of an item in the heap     * @return the index of the left heap     */    private static int leftChild(int i)    {        return 2 * i + 1;    }    /**     * Internal method that makes recursive calls.     *      * @param a     *            an array of Comparable items.     * @param tmpArray     *            an array to place the merged result.     * @param left     *            the left-most index of the sub-array.     * @param right     *            the right-most index of the sub-array.     */    private static <T extends Comparable<? super T>> void mergeSort(T[] a,            T[] tmpArray, int left, int right)    {        if (left < right)        {            int center = (left + right) / 2;            mergeSort(a, tmpArray, left, center);            mergeSort(a, tmpArray, center + 1, right);            merge(a, tmpArray, left, center + 1, right);        }    }    /**     * Internal method that merges two sorted halves of a sub-array     *      * @param a     *            an array of Comparable items     * @param tmpArray     *            an array to place the merged result.     * @param leftPos     *            the left-most index of the sub-array.     * @param rightPos     *            the index of the start of the second half.     * @param rightEnd     *            the right-most index of the sub-array.     */    private static <T extends Comparable<? super T>> void merge(T[] a,            T[] tmpArray, int leftPos, int rightPos, int rightEnd)    {        int leftEnd = rightPos - 1;        int tmpPos = leftPos;        int numElements = rightEnd - leftPos + 1;        // Main loop        while (leftPos <= leftEnd && rightPos <= rightEnd)        {            if (a[leftPos].compareTo(a[rightPos]) <= 0)            {                tmpArray[tmpPos++] = a[leftPos++];            } else            {                tmpArray[tmpPos++] = a[rightPos++];            }        }        while (leftPos <= leftEnd)            // Copy rest of first half            tmpArray[tmpPos++] = a[leftPos++];        while (rightPos <= rightEnd)            // Copy rest of second half            tmpArray[tmpPos++] = a[rightPos++];        // Copy tmpArray back        for (int i = 0; i < numElements; i++, rightEnd--)        {            a[rightEnd] = tmpArray[rightEnd];        }    }    /**     * Internal quick sort method that makes recursive calls. Uses     * median-of-three partitioning and a cutoff of 10     *      * @param a     *            an array of Comparable items     * @param left     *            the left-most index of the sub-array.     * @param right     *            the right-most index of the sub-array.     */    private static <T extends Comparable<? super T>> void quickSort(T[] a,            int left, int right)    {        if (left + CUTOFF <= right)        {            T pivot = median3(a, left, right);            // Begin partitioning            int i = left, j = right - 1;            for (;;)            {                while (a[++i].compareTo(pivot) < 0)                {                }                while (a[--j].compareTo(pivot) > 0)                {                }                if (i < j)                {                    swapReferences(a, i, j);                } else                {                    break;                }            }            swapReferences(a, i, right - 1); // Restore pivot            quickSort(a, left, i - 1); // Sort small elements            quickSort(a, i + 1, right);// Sort large elements        } else        // Do an insertion sort on the sub-array        {            insertionSort(a, left, right);        }    }    private static <T extends Comparable<? super T>> T median3(T[] a, int left,            int right)    {        int center = (left + right) / 2;        if (a[center].compareTo(a[left]) < 0)            swapReferences(a, left, center);        if (a[right].compareTo(a[left]) < 0)            swapReferences(a, left, right);        if (a[right].compareTo(a[center]) < 0)            swapReferences(a, center, right);        // Place pivot at position right-1        swapReferences(a, center, right - 1);        return a[right - 1];    }    /**     * Internal insertion method     *      * @param a     *            an array of Comparable items     * @param left     *            the left-most index of the array     * @param right     *            the right-most index of the array     */    private static <T extends Comparable<? super T>> void insertionSort(T[] a,            int left, int right)    {        if (left < right)        {            int j;            for (int p = left + 1; p <= right; p++)            {                T tmp = a[p];                for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--)                    a[j] = a[j - 1];                a[j] = tmp;            }        }    }    /**     * Internal method: Swap the position of two elements of an array by     * referencing     *      * @param a     *            an array for swapping the element     * @param i     *            the first element's index     * @param j     *            the second element's index     * @return the array after swapping     */    private static <T> T[] swapReferences(T[] a, int i, int j)    {        T tmp = a[i];        a[i] = a[j];        a[j] = tmp;        return a;    }}