直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增 1 的有序表。¹

一、实现思路#

1.1 步骤#

• 将整个数组分成两部分，左边有序部分和右边无序部分；
• 在排序的过程中，不用管右边部分的顺序，只需要保证左边始终有序；

• 从左到右遍历整个数组，每遍历到一个新的元素，都将其取出(1)；

  1. 因为无法马上确定其位置，需要对其进行排序

• 然后在保证顺序的左边部分中寻找其应该的位置；

• 即，从该元素位置触发，向左遍历有序的部分，并判断是否应该插入；
• 如不能插入，则将判断的元素向右移位，反之插入；
• 如此反复直至所有元素都遍历完成，那么整个数组都是有序的了；

1.2 图解#

1.2.1 动画图解#

1.2.2 流程图图解#

flowchart TB
    START(["开始"])
    END(["结束"])
    in1[/"接收参数：T* arr, int n"/]
    if1{"判断：j ≥ 0 ?"}
    if2{"判断：tmp < arr[i] ?"}
    if3{"判断：i < n ?"}
    def1("定义：T tmp")
    def2("定义：int j")
    def3("定义：int i")
    op1["右移：arr[j + 1] = arr[j]"]
    op2["插入：arr[j + 1] = tmp"]
    op3["j--"]
    op4["i++"]
    op5["赋值：j = i - 1"]
    op6["赋值：tmp = arr[i]"]
    op7["赋值：i = 1"]

    START --> in1 --> def2 --> def3 --> op7 --> if3 --True--> END
    if3 --True--> def1 --> op6 --> op5 --> if1 --False--> op2 --> op4 --> if3
    if1 --True--> if2 --False--> op2
    if2 --True--> op1 --> op3 --> if1

二、实现代码#

2.1 多语言版本#

typedef int T;
void straight_insertion_sort(T* arr, const int length) {
    // 外循环：遍历所有要被排序的元素
    for (int i = 1; i < length; i++) {
        T tmp = arr[i]; // 取出待排序的元素
        int j = i - 1; // 向左寻找的起始索引
        // 内循环：向左边寻找待排序元素应该的位置
        while (j >= 0 && tmp < arr[j]) { // 到该插入时停止内循环(1)
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = tmp; // 插入
    }
}

template <typename T = int>
void straight_insertion_sort(T* arr, const int& length) {
    // 外循环：遍历所有要被排序的元素
    for (int i = 1; i < length; i++) {
        T tmp = arr[i]; // 取出待排序的元素
        int j = i - 1; // 向左寻找的起始索引
        // 内循环：向左边寻找待排序元素应该的位置
        while (j >= 0 && tmp < arr[j]) { // 到该插入时停止内循环(1)
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = tmp; // 插入
    }
}

def straight_insertion_sort[T](lst: list[T]) -> None:
    # 外循环：遍历所有要被排序的元素
    for i in range(1, len(lst)):
        tmp = lst[i]  # 取出待排序的元素
        j = i - 1  # 向左寻找的起始索引
        # 内循环：向左边寻找待排序元素应该的位置
        while j >= 0 and tmp < lst[j]:  # 到该插入时停止内循环(1)
            lst[j + 1] = lst[j]  # 右移
            j -= 1
        lst[j + 1] = tmp  # 插入

public static <T extends Comparable<T>> void direct_insertion_sort(T[] arr) {
    // 外循环：遍历所有要被排序的元素
    for (int i = 1; i < arr.length; i++) {
        T tmp = arr[i]; // 取出待排序的元素
        int j = i - 1; // 向左寻找的起始索引
        // 内循环：向左边寻找待排序元素应该的位置
        while (j >= 0 && tmp.compareTo(arr[j]) < 0) { // 到该插入时停止内循环(1)
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = tmp; // 插入
    }
}

static void straight_insertion_sort<T>(T[] arr) where T : IComparable<T>
{
    // 外循环：遍历所有要被排序的元素
    for (int i = 0; i < arr.Length; i++)
    {
        T tmp = arr[i]; // 取出待排序的元素
        int j = i - 1; // 向左寻找的起始索引
        // 内循环：向左边寻找待排序元素应该的位置
        while (j >= 0 && tmp.CompareTo(arr[j]) < 0) // 到该插入时停止内循环(1)
        {
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = tmp; // 插入
    }
}

function straight_insertion_sort<T extends number | string>(arr: T[]): void {
    // 外循环：遍历所有要被排序的元素
    for (let i = 1; i < arr.length; i++) {
        let tmp = arr[i]; // 取出待排序的元素
        let j = i - 1; // 向左寻找的起始索引
        // 内循环：向左边寻找待排序元素应该的位置
        while (j >= 0 && tmp < arr[j]) { // 到该插入时停止内循环(1)
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = tmp; // 插入
    }
}

2.2 测试用例#

9
6 28 13 72 85 39 41 6 20

6 6 13 20 28 39 41 72 85

三、算法性质#

3.1 时空复杂度#

3.1.1 时间复杂度分析#

假设数组大小为 \(n\) 。

外循环从左边第 \(2\) 个元素(1)开始到右边遍历了数组的每一个元素，即 \(n-1\) 个元素被外循环遍历。在每一个内循环中，假设此时待排序元素的索引为 \(i\)，该元素会反向对左边已遍历（排好序）的元素进行再次遍历，遍历 \(i-1\) 次(2)。但每次内循环会在元素插入的时候终止，我们并不知道是在什么时候终止的，但我们知道，这是随机的（取决于数据）。

1. 第 1 个元素本身就是有序的，遍历它没有什么意义，直接跳过
2. 💡 思考：遍历有序的部分是否可以改进以提高算法性能呢？

当数组初始为顺序时，每个内循环只需要比较 \(1\) 次，反之，当数组逆序的时候，就需要完成全部的遍历过程，即每次内循环要比较 \(i-1\) 次，平均下来，每次内循环比较了 \(\frac{i-1}{2}\) 次，因此时间复杂度：

数组顺序时，有最好情况：

数组逆序时，有最坏情况：

平均情况：

3.1.2 空间复杂度分析#

整个算法的过程中，我们只用了 \(1\) 个临时变量来存储被取出来的那个元素，因此空间复杂度：

3.2 稳定性与排序方式#

3.2.1 稳定性分析#

能否稳定取决于具体的实现，实现细节没把握好也可能导致不稳定。关键在于对元素比较出现相等情况时是否应该插入的判断。

3.2.2 排序方式分析#

排序方式属于内部排序，没有用到外部的空间。

四、相关习题#

4.1 编程题#

• 洛谷 - P7910 [CSP-J 2021]
• 力扣 - 147
• 力扣 - 面试题 05.01

4.2 选择题#

• 牛客 - 试题广场

欢迎在评论区留下你的想法

下面没有更多评论啦😆