数据结构（十）：直接插入排序

• 直接插入排序是将未排序的数据插入至已排好序序列的合适位置

直接插入排序例子

• 流程：

  • 首先比较数组的前两个数据，并排序
  • 比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置
    　 - 比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置

• 举例：

  • 假设数组如下

  25	11	45	26	12	78

  • 第一趟排序：比较 25 11，位置互换

  11	25	45	26	12	78

  • 第二趟排序：45 大于 11 25，位置不变
  • 第三趟排序：26 大于 11 25，小于 45，将其插入 25 和 45 之间

  11	25	26	45	12	78

  • ........

直接插入排序代码

int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 直接插入排序
for (int i = 1; i < arr.length; i++) {
    int tmp = arr[i];
    int j;
    for (j = i - 1; j >= 0; j--) {
    // 判断是否大于tmp，大于则后移一位
        if (arr[j] > tmp) {
            arr[j + 1] = arr[j];
        } else {
            break;
        }
    }
    arr[j + 1] = tmp;
}

直接插入排序性能

• 如果排序是随机的，那么根据概率相同原则，直接插入排序时间复杂度为 O(n²)，相比冒泡排序和简单选择排序性能要好一些