比较排序 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
*/
/* https://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);
    }
}