package helloclean.basetest;

/**
 * 简单排序: 冒泡,选择,插入 排序
 */
public 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 i = 0; i < nElems; i ++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    //冒泡排序
    public void bubbleSort() {
        int out, in;
        for(out = nElems -1; out > 0; out --) {
            for(in = 0; in < out; in  ++) {
                if(a[in] > a[in + 1]) {
                    swap (in,in + 1);
                }
            }
        }
    }


    //选择排序
    public void selectionSort() {
        int out, in, min;

        for(out = 0; out < nElems; out ++) {
            min = out;
            for(in = out + 1; in < nElems; in ++) {
                if(a[in] < a[min]) {
                    min = in;
                }
            }
            swap(out,min);
        }
    }


    //插入排序
    public void insertionSort() {
        int in,out;
        for(out = 1; out < nElems; out ++) {
            long temp = a[out];
            in = out;
            while (in > 0 && a[in - 1] >= temp) {
                a[in] = a[in -1];
                -- in;
            }
            a[in] = temp;
        }
    }


    /**
     * 二分查找,返回下标,如果没有找到,返回数组的长度
     * @param key
     * @return
     */
    public int find(long key) {
        int lowBound = 0;
        int highBound = nElems -1;
        int curIn;

        while (true) {
            curIn = (lowBound + highBound) / 2;
            if(a[curIn] == key) {
                System.out.println("找到数据 " + key + " 其下标为: " + curIn);
                return curIn;
            } else if (lowBound > highBound) {
                System.out.println("没有找到数据,返回数组的长度: " + nElems);
                return nElems;
            } else {
                if(a[curIn] < key) {
                    lowBound = curIn + 1;
                } else {
                    highBound = curIn -1;
                }
            }
        }
    }

    private void swap(int x, int y) {
        long temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        ArrayBub arrayBub = new ArrayBub(maxSize);

        arrayBub.insert(100);
        arrayBub.insert(1);
        arrayBub.insert(50);
        arrayBub.insert(40);
        arrayBub.insert(10);
        arrayBub.insert(60);
        arrayBub.insert(70);

        arrayBub.disPlay();

//        arrayBub.bubbleSort();

//        arrayBub.selectionSort();

        arrayBub.insertionSort();

        arrayBub.disPlay();

        arrayBub.find(70);

        arrayBub.find(90);
    }
}
10-01 18:18