 比较排序 Java 代码 ` `

``` 比较排序 Java 代码 /** @(#)BubbleSortAlgorithm.java 1.6 95/01/31 James Gosling** Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.**//** A bubble sort demonstration algorithm* SortAlgorithm.java, Thu Oct 27 10:32:35 1994** @author James Gosling* @version     1.6, 31 Jan 1995** Modified 23 Jun 1995 by Jason Harrison@cs.ubc.ca:*   Algorithm completes early when no items have been swapped in the *   last pass.*/class BubbleSort2Algorithm extends SortAlgorithm {    void sort(int a[]) throws Exception {    for (int i = a.length; --i>=0; ) {            boolean flipped = false;        for (int j = 0; j<i; j++) {        if (stopRequested) {            return;        }        if (a[j] > a[j+1]) {            int T = a[j];            a[j] = a[j+1];            a[j+1] = T;            flipped = true;        }        pause(i,j);        }        if (!flipped) {            return;        }        }    }}/** @(#)SelectionSortAlgorithm.java  1.0 95/06/23 Jason Harrison** Copyright (c) 1995 University of British Columbia* *//*** A selection sort demonstration algorithm* SortAlgorithm.java, Thu Oct 27 10:32:35 1994** @author Jason Harrison@cs.ubc.ca* @version     1.0, 23 Jun 1995**/class SelectionSortAlgorithm extends SortAlgorithm {    void sort(int a[]) throws Exception {    for (int i = 0; i < a.length; i++) {        int min = i;            int j;            /*             *  Find the smallest element in the unsorted list             */            for (j = i + 1; j < a.length; j++) {            if (stopRequested) {            return;                }        if (a[j] < a[min]) {                    min = j;                }            pause(i,j);        }            /*             *  Swap the smallest unsorted element into the end of the             *  sorted list.             */            int T = a[min];            a[min] = a[i];        a[i] = T;        pause(i,j);        }    }}/** @(#)InsertSortAlgorithm.java 1.0 95/06/23 Jason Harrison** Copyright (c) 1995 University of British Columbia* *//*** An insertion sort demonstration algorithm* SortAlgorithm.java, Thu Oct 27 10:32:35 1994** @author Jason Harrison@cs.ubc.ca* @version     1.0, 23 Jun 1995**/class InsertionSortAlgorithm extends SortAlgorithm {    void sort(int a[]) throws Exception {    for (int i = 1; i < a.length; i++) {        int j = i;        int B = a[i];        while ((j > 0) && (a[j-1] > B)) {                if (stopRequested) {            return;                }            a[j] = a[j-1];            j--;            pause(i,j);        }        a[j] = B;            pause(i,j);        }    }}/** @(#)ShellSortAlgorithm.java  1.1 2000/04/12 Jason Harrison** Copyright (c) 1995 University of British Columbia* *//*** A shell sort demonstration algorithm* SortAlgorithm.java, Thu Oct 27 10:32:35 1994* Note: Invented by Donald Lewis Shell [CACM, July, 1959, pages 30-32]* @author Jason Harrison@cs.ubc.ca* @version     1.0, 23 Jun 1995* @version     1.1, 12 Apr 2000 *              -- fixed java.lang.ArrayIndexOutOfBoundsException*                 Joel Berry <jmbshifty@yahoo.com> found this bug*//* http://www.auto.tuwien.ac.at/~blieb/woop/shell.html** Shellsort is a simple extension of insertion sort which gains speed* by allowing exchanges of elements that are far apart. The idea is* to rearrange the array to give it the property that every hth* element (starting anywhere) yields a sorted array. Such an array* is said to be h-sorted.** By h-sorting for some large values of h, we can move elements in* the array long distances and thus make it easier to h-sort for* smaller values of h. Using such a procedure for any sequence of* values h which ends in 1 will produce a sorted array.*/class ShellSortAlgorithm extends SortAlgorithm {    void sort(int a[]) throws Exception {    int h = 1;        /*          * find the largest h value possible          */        while ((h * 3 + 1) < a.length) {        h = 3 * h + 1;    }        /*          * while h remains larger than 0          */        while( h > 0 ) {            /*              * for each set of elements (there are h sets)             */            for (int i = h - 1; i < a.length; i++) {                /*                  * pick the last element in the set                 */                int B = a[i];                int j = i;                /*                 * compare the element at B to the one before it in the set                 * if they are out of order continue this loop, moving                 * elements "back" to make room for B to be inserted.                 */                for( j = i; (j >= h) && (a[j-h] > B); j -= h) {                    if (stopRequested) {                return;                    }                    a[j] = a[j-h];            pause(i,j);                }                /*                 *  insert B into the correct place                 */                a[j] = B;            pause(j);            }            /*              * all sets h-sorted, now decrease set size             */            h = h / 3;        }    }}/** @(#)QSortAlgorithm.java  1.6f 95/01/31 James Gosling** Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved.* *//*** A quick sort demonstration algorithm* SortAlgorithm.java, Thu Oct 27 10:32:35 1994** @author James Gosling* @version     1.6f, 31 Jan 1995*//*** 19 Feb 1996: Fixed to avoid infinite loop discoved by Paul Haeberli.*              Misbehaviour expressed when the pivot element was not unique.*              -Jason Harrison** 21 Jun 1996: Modified code based on comments from Paul Haeberli, and*              Peter Schweizer (Peter.Schweizer@mni.fh-giessen.de).  *              Used Daeron Meyer's (daeron@geom.umn.edu) code for the*              new pivoting code. - Jason Harrison** 09 Jan 1998: Another set of bug fixes by Thomas Everth (everth@wave.co.nz)*              and John Brzustowski (jbrzusto@gpu.srv.ualberta.ca).*/class QSortAlgorithm extends SortAlgorithm {    void sort(int a[], int lo0, int hi0) throws Exception {    int lo = lo0;    int hi = hi0;    pause(lo, hi);    if (lo >= hi) {        return;    }        else if( lo == hi - 1 ) {            /*             *  sort a two element list by swapping if necessary              */            if (a[lo] > a[hi]) {                int T = a[lo];                a[lo] = a[hi];                a[hi] = T;            }            return;    }        /*         *  Pick a pivot and move it out of the way         */    int pivot = a[(lo + hi) / 2];        a[(lo + hi) / 2] = a[hi];        a[hi] = pivot;        while( lo < hi ) {            /*             *  Search forward from a[lo] until an element is found that             *  is greater than the pivot or lo >= hi              */            while (a[lo] <= pivot && lo < hi) {        lo++;        }            /*             *  Search backward from a[hi] until element is found that             *  is less than the pivot, or lo >= hi             */        while (pivot <= a[hi] && lo < hi ) {        hi--;        }            /*             *  Swap elements a[lo] and a[hi]             */            if( lo < hi ) {                int T = a[lo];                a[lo] = a[hi];                a[hi] = T;                pause();            }        if (stopRequested) {                return;            }    }        /*         *  Put the median in the "center" of the list         */        a[hi0] = a[hi];        a[hi] = pivot;        /*         *  Recursive calls, elements a[lo0] to a[lo-1] are less than or         *  equal to pivot, elements a[hi+1] to a[hi0] are greater than         *  pivot.         */    sort(a, lo0, lo-1);    sort(a, hi+1, hi0);    }    void sort(int a[]) throws Exception {    sort(a, 0, a.length-1);    }} ```