バブル+高速+スタックソート

12858 ワード

package xie.struct;



import java.util.ArrayList;



public class Sort<T extends Comparable<T>> {

    public static final int QuickSort = 1;

    public static final int SelectMin = 4;

    public static final int MaoPao = 3;

    public static final int HeapSort = 2;

    

    

    private ArrayList<T> data;// 



    public Sort() {

    }



    public void runSort(int mode) {

        switch (mode) {

        case 1:

            System.out.println(" :");

            this.QuickSort(data, 0, data.size() - 1);

            break;

        case 2:

            System.out.println(" :");

            this.heapSort();

            break;

        case 3:

            System.out.println(" :");

            this.MaoPao();

            break;

        case 4:

            break;

        default:

            break;

        }

    }



    public void setData(ArrayList<T> a) {

        this.data = a;

    }



    public void addData(T data) {

        this.data.add(data);

    }



    public String toString() {

        for (int i = 0; i < data.size(); i++)

            System.out.print(data.get(i) + "/");

        return null;



    }

    

    public void MaoPao()

    {

        int i,j; 

        int n=this.data.size();

        for(i=0;i<n;i++)  

            for(j=1;j<n-i;j++){

                if(this.data.get(j-1).compareTo(this.data.get(j))>0)

                {

                T swap=this.data.get(j);

                this.data.set(j,this.data.get(j-1));

                this.data.set(j-1,swap);

                }

            }

    }

    

    



    /*

     *  

     */

    private void QuickSort(ArrayList<T> a, int left, int right) {

        if (left < right) {

            int low = left;

            int high = right;

            T key = a.get(low);

            while (low < high) {

                while (low < high && a.get(high).compareTo(key) >= 0)

                    high--;

                a.set(low, a.get(high));

                while (low < high && a.get(low).compareTo(key) < 0)

                    low++;

                a.set(high, a.get(low));

            }

            a.set(low, key);

            QuickSort(a, left, low - 1);

            QuickSort(a, low + 1, right);

        }

    }



    /*

     * 

     *  

     */



    private void buildHeap() {

        int len = this.data.size();

        int i;

        for (i = len / 2 - 1; i >= 0; i--)

            this.adjustHeap(i);



    }



    private void adjustHeap(int index) {

        int len = this.data.size();

        int left = index * 2 + 1;

        int right = index * 2 + 2;

        int smaller = left;

        T swap;

        if (left > len - 1)

            return;

        if (right < len

                && this.data.get(left).compareTo(this.data.get(right)) > 0) {

            smaller = right;

        }

        if (smaller < len

                && this.data.get(index).compareTo(this.data.get(smaller)) > 0) {

            swap = this.data.get(smaller);

            this.data.set(smaller, this.data.get(index));

            this.data.set(index, swap);

            this.adjustHeap(smaller);

        }

    }



    private void heapSort() {

        this.buildHeap();

        int len = this.data.size();

        while (len > 0) {

            System.out.print(this.data.get(0)+"/");

            this.data.set(0, this.data.get(len - 1));

            this.data.remove(len - 1);

            len--;

            this.adjustHeap(0);

        }

    }



    /*

     * 

     *  

     */



    public static void main(String args[]) {

        ArrayList<String> array = new ArrayList<String>();

        array.add("A");

        array.add("D");

        array.add("G");

        array.add("H");

        array.add("S");

        array.add("J");

        array.add("B");

        Sort<String> sort = new Sort<String>();

        sort.setData(array);

        sort.runSort(Sort.QuickSort);

        sort.toString();

        

        sort.setData(array);

        sort.runSort(Sort.MaoPao);

        sort.toString();

        

        sort.setData(array);

        sort.runSort(Sort.HeapSort);

    }

}

 
クイックソート出力:A/B/D/G/H/J/S/
泡立ちソート出力:A/B/D/G/H/J/S/
ヒープソート出力:A/B/D/G/H/J/S/