插入排序

1. 插入排序

/**
 * 插入排序
 * O(n) 、O(n^2)、O(n^2)
 * 直接插入排序是一种简单的排序算法，
 * 其核心思想是将待排序的元素逐个插入到已排序部分的适当位置，直到所有元素都插入完毕
 * @param arr
 * @return
 */
public static int[] insertSort(int[] arr){
    int n = 0;
    if (arr == null || (n = arr.length) <= 1){
        return arr;
    }
    // 从第二个元素开始遍历（第一个元素默认已排序）
    for (int i = 1; i < n; i++){
        //待插入元素
        int key = arr[i];
        // 从当前元素的前一个元素开始，向前比较
        int j = i - 1;
        //将比key大的元素向后移动
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];  // 向后移动
            j--;  // 继续向前比较
        }
        // 将key插入到正确的位置
        arr[j + 1] = key;
    }
    return arr;
}