排序算法

 * 插入排序
 * @param array
 * @return arr
 */
public static int[] insertSort(int[] array) {
    //对array进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(array, array.length); 
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        for (int j = i - 1; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j + 1] = arr[j];
            } else {
                arr[j + 1] = temp;
                break;
            }
        }
    }
    return arr;
}

 * 冒泡排序
 * @param array
 * @return
 */
public static int[] bubbleSort(int[] array) {
    int[] arr = Arrays.copyOf(array, array.length);
    int temp;
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序边界的位置，每次只需要比较到这里为止
    int sortBorder = arr.length - 1;
    for (int i = 0; i < arr.length; i++) {
        //有序标记，每一轮的初始值为true,有交换则改为false
        boolean isSorted = true;
        for (int j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;
                //把无序数列的边界更新为最后一次交换元素的位置
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        //如果没有减缓，数组就是有序的，跳出循环
        if (isSorted) {
            break;
        }
    }
    return arr;
}