冒泡排序,鸡尾酒排序,选择排序,插入排序,二分法插入排序,快速排

 int[] attr = {5,6,2,7,4,13,3,20,14,15,10,11,6,9,8,16};

冒泡排序

  大的下沉，小的上浮。
  每次循环都从头(0)开始比较到(attr.length-循环次数)位置，每次比较相邻两个元素，前一个元素大于后一个元素，则两个元素交换值。

       public void bubblingSort(int[] attr) {
        for (int i = attr.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (attr[j] > attr[j + 1]) {
                    int temp = attr[j];
                    attr[j] = attr[j + 1];
                    attr[j + 1] = temp;
                }
            }
        }
    }

鸡尾酒排序(升级版冒泡排序)

  大的下沉，小的上浮。
  奇次循环从头开始两两比较大的下沉，偶次循环从末尾开始两两比较小的上浮。

public void flipSort(int[] attr) {
        int start = 0;
        int end   = attr.length - 1;
        int temp;
        while (start < end) {
            for (int i = start; i < end; i++) {
                if (attr[i] > attr[i + 1]) {
                    temp = attr[i];
                    attr[i] = attr[i + 1];
                    attr[i + 1] = temp;
                }
            }
            end--;
            for (int j = end; j > start; j--) {
                if (attr[j] < attr[j - 1]) {
                    temp = attr[j - 1];
                    attr[j - 1] = attr[j];
                    attr[j] = temp;
                }
            }
            start++;
        }
    }

选择排序

  每次从无序序列中选择最大（最小）放到有序序列的末尾。
  每次循环都从头(0)开始比较到(attr.length-循环次数)位置，比较每次循环的最后一个元素和前面其他元素，如果有比最后一个元素大的值就和其交换。

 public void selectSort(int[] attr) {
        for (int i = attr.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (attr[j] > attr[i]) {
                    int temp = attr[j];
                    attr[j] = attr[i];
                    attr[i] = temp;
                }
            }
        }
    }

插入排序

  从无序序列中取出一个元素放入到有序列相应的位置中。
  默认无序序列第一个为有序序列，然后从无序序列第二个开始取元素k，从有序序列末尾元素开始依次和元素k比较，比k大则后移一位，直到不比k大时，将k插入到空位。重复执行以上循环到无序序列每个元素都插入到了有序序列中。

 public void insertSort(int[] attr) {
        for (int i = 1; i < attr.length; i++) {
            int get = attr[i];
            int j   = i - 1;
            while (j >= 0 && attr[j] > get) {
                attr[j + 1] = attr[j];
                j--;
            }
            attr[j + 1] = get;
        }
    }

二分法插入排序

  从无序序列中取出一个元素放入到有序列相应的位置中。
  默认无序序列第一个为有序序列，然后从无序序列第二个开始取元素k，然后取出有序序列中间位置的元素和元素k比较，比k大则取有序序列头到序列中间段重复上述比较，比k小则取有序序列中间位置到序列末尾段重复上述比较，直到取出的序列段只有一个元素z并确定k元素和z位置关系，再然后将k元素插入位置后的元素全部后移，最后将k插入到空位。重复执行以上循环到无序序列每个元素都插入到了有序序列中。

public void dichotomySort(int[] attr){
        for (int i = 1; i < attr.length; i++) {
            int temp = attr[i];
            int l = 0;
            int h = i - 1;
            int min = -1;
            while (l <= h){
                min =  (h + l) /2;
                if (attr[min] > temp){
                    h = min - 1;
                } else {
                    l = min + 1;
                }
            }
            for (int j = i - 1; j >= l; j--) {
                attr[j+1] = attr[j];
            }
            attr[l] = temp;
        }
    }

快速排序

  选取一个参考值key，然后将比key大的放到key之后，比key小的放到key之前。再然后以key的位置分两段进行之前的操作，直到无法再分为止。
  每次循环前选取一个key(通常选择序列中第一个)作为参考，然后从序列末尾（指针j）开始找到第一个比key小的值与key互换位置，再然后从序列头（指针i）开始找到第一个比序列大的值与key互换位置，继续以上互换直到i大于等于j结束本次循环，最后以key的位置为界将序列分为前后两段分别进行上述循环，直到序列无法继续分段为止（即开始指针大于等于结束指针）。

public void quickSort(int start, int end, int[] attr) {
        if (start >= end) {
            return;
        }
        int key = attr[start];
        int i   = start;
        int j   = end;

        while (i < j) {
            while (i < j && attr[j] >= key) {
                j--;
            }
            attr[i] = attr[j];
            while (i < j && attr[i] <= key) {
                i++;
            }
            attr[j] = attr[i];
        }
        attr[i] = key;
        quickSort(start, i - 1, attr);
        quickSort(i + 1, end, attr);
    }