package chap03.BubbleSort;

// bubbleSort.java

// demonstrates bubble sort

// to run this program: C>java BubbleSortApp

class ArrayBub {

    private long[] a;

    private int nElems;

    public ArrayBub(int max) {

        a = new long[max];

        nElems = 0;

    }

    public void insert(long value) {

        a[nElems] = value;

        nElems++;

    }

    public void display() {

        for (int j = 0; j < nElems; j++) {

            System.out.print(a[j] + " ");

        }

        System.out.println("");

    }

    // 冒泡排序

    public void bubbleSort() {

        int out, in;

        for (out = nElems - 1; out > 1; out--) {

            for (in = 0; in < out; in++) {

                if (a[in] > a[in + 1]) {

                    swap(in, in + 1);

                }

            }

        }

    }

    // 插入排序

    public void insertionSort() {

        int in, out;

        // out is dividing line

        for (out = 1; out < nElems; out++)

        {

            // remove marked item

            long temp = a[out];

            // start shifts at out

            in = out;

            while (in > 0 && a[in - 1] >= temp) {

                a[in] = a[in - 1];

                --in;

            }

            a[in] = temp;

        }

    } 

    // 选择排序

    public void selectionSort() {

        int out, in, min;

        for (out = 0; out < nElems - 1; out++) {

            min = out;

            for (in = out + 1; in < nElems; in++) {

                if (a[in] < a[min]) {

                    min = in;

                }

            }

            swap(out, min);

        }

    }

    private void swap(int one, int two) {

        long temp = a[one];

        a[one] = a[two];

        a[two] = temp;

    }

}

class BubbleSortApp {

    public static void main(String[] args) {

        int maxSize = 100;

        ArrayBub arr;

        arr = new ArrayBub(maxSize);

        arr.insert(77);

        arr.insert(99);

        arr.insert(44);

        arr.insert(55);

        arr.insert(22);

        arr.insert(88);

        arr.insert(11);

        arr.insert(00);

        arr.insert(66);

        arr.insert(33);

        arr.display();

        arr.bubbleSort();

        arr.display();

    }

}