排序算法

常见的排序算法有冒泡、选择、插入排序算法。

一、冒泡排序

冒泡算法的运作规律如下：

①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
③、针对所有的元素重复以上的步骤，除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

public int[] bubbleSort(int[] array) {
        //i代表总的进行多少轮比较
        for (int i = 1; i < array.length; i++) {
                boolean flag = true;
                for (int j = 0; j < array.length - i; j++) {
                        if (array[j] > array[j + 1]) {
                                int tmp = array[j];
                                array[j] = array[j + 1];
                                array[j + 1] = tmp;
                                flag = false;
                        }
                }
                if (flag) {
                        break;
                }
        }
        return array;
}

二、选择排序

选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。分为三步：

①、从待排序序列中，找到关键字最小的元素
②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束

public int[] selectionSort(int[] array) {
        // 总共要经过N-1轮比较，每次拿当前i位置的值去后面查到最小的值比较,找出最小值的位置，再交换。
        for (int i = 0; i < array.length - 1; i++) {
                int min = i;
                // 找到后面的最小元素，如遇到比i对应还小的，记录下标，直到找完为止。
                for (int j = i + 1; j < array.length; j++) {
                        if (array[min]>array[j]) {
                                min = j;// 记录目前能找到的最小值元素的下标
                        }
                }
                // 最小值和当前i位置所在的值进行交换
                if (i != min) {
                        int temp = array[i];
                        array[i] = array[min];
                        array[min] = temp;
                }
        }
        return array;
}

三、插入排序

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等

public int[] insertSort(int[] array) {
    //从第一个元素开始，把当前值与依次前面的值对此，前面的值只要比他大就往后移动，直到合适位置，直接插入
    for(int i = 1;i < array.length;i++){
    int temp = array[i];
    int j = i;
    //判断前面的值是否与需要插入的值比较，只要不小于插入的值，都往后移动位置。
    while(j > 0 && array[j-1] >= temp){
            array[j] = array[j-1];//移动值
        j--;
    }
    array[j] = temp;
}
        return array;
}