排序算法（1）：直接插入排序

小明 2025-05-03 09:57:39 14

原���链接（原文也是我写的哈，强烈推荐去原文链接看）：直接插入排序 - Fucking Code

（）

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

一、实现思路

1.1 步骤

  • 将整个数组分组两部分，左边和右边部分；
  • 在排序的过程中，无需管右边部分的顺序，只需要保证左边始终有序；
  • 遍历从左到右，每遍历到一个新的元素，都将其取出；
  • 然后在保证顺序的左边部分中寻找其应该的位置；
  • 即，从该元素位置向左遍历，并判断是否应该插入；
  • 如不能插入，则将判断的元素向右移位，反之插入；
  • 如此反复直至遍历完成，那么整个数组都是有序的了。

    1.2 流程图

    注：以下面 C++ 语言的实现过程为准

    （）

    二、实现代码

    2.1 多语言版本

    推荐学习 C++ 版本，更利于理解算法的本质。另外，下面 Python 的实现方式与其它三个略微有些不同，请注意。

    🟣 C 17
    typedef int T;
void straight_insertion_sort(T* arr, const int n) {
    int j; // 当前被比较元素的索引
    for (int i = 1; i = 0 && tmp  

    🔴 C++ 20
     

    template 
void straight_insertion_sort(T* arr, const int& n) {
    int j; // 当前被比较元素的索引
    for (int i = 1; i = 0 && tmp  

    🔵 Python 3
     

    def straight_insertion_sort[T](lst: list[T]) -> None:
    for i in range(1, len(lst)):
        tmp = lst[i]  # 取出不确定位置的元素
        for j in range(i - 1, -1, -1):
            if tmp >= lst[j]:  # 到该插入的位置了
                lst[j + 1] = tmp  # 插入
                break
            lst[j + 1] = lst[j]  # 右移
        else:  # 此处容易忘记，遍历完了表示 tmp 是最小的，虽然但是，它还没有插入啊！
            lst[0] = tmp  # 特殊情况的插入

     

    🟠 Java 21
     

    public static  void straight_insertion_sort(T[] arr) {
    int j; // 当前被比较元素的索引
    for (int i = 1; i = 0 && tmp.compareTo(arr[j])  

    🟢 C# 12
     

    static void straight_insertion_sort(T[] arr) where T : IComparable
{
    int j; // 当前被比较元素的索引
    for (int i = 0; i = 0 && tmp.CompareTo(arr[j])  

    🟡 TypeScript 5
     

    function straight_insertion_sort(arr: T[]): void {
    let j; // 当前被比较元素的索引
    for (let i = 1; i = 0 && tmp  

    2.2 测试用例
     

    🔻输入数据
     

    9
6 28 13 72 85 39 41 6 20

     

    🔺输出数据
     

    6 6 13 20 28 39 41 72 85

     

    三、算法性质
     

    3.1 时空复杂度
    复杂度😀最好情况😭最坏情况🫤平均情况
    时间复杂度 O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2)
    空间复杂度 O ( 1 ) O(1) O(1) O ( 1 ) O(1) O(1) O ( 1 ) O(1) O(1)
    3.1.1 时间复杂度分析

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

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

    数组顺序时的最好情况：

    O ( T n ) = O ( 1 + 1 + 1 + . . . + 1 ) = O ( n − 1 ) = O ( n ) O(T_n) = O(1 + 1 + 1 + ... + 1) = O(n-1) = O(n) O(Tn​)=O(1+1+1+...+1)=O(n−1)=O(n)

    数组逆序时的最坏情况：

    O ( T n ) = O ( 1 + 2 + 3 + . . . + ( n − 1 ) ) = O ( n ( n − 1 ) 2 ) = O ( n 2 ) O(T_n) = O(1 + 2 + 3 + ... + (n-1)) = O\Big(\frac{n(n-1)}{2}\Big) = O(n^2) O(Tn​)=O(1+2+3+...+(n−1))=O(2n(n−1)​)=O(n2)

    平均情况：

    O ( T n ) = O ( 1 2 + 2 2 + 3 2 + . . . + n − 1 2 ) = O ( n ( n − 1 ) 4 ) = O ( n 2 ) O(T_n) = O\Big(\frac{1}{2} + \frac{2}{2} + \frac{3}{2} + ... + \frac{n-1}{2}\Big) = O\Big(\frac{n(n-1)}{4}\Big) = O(n^2) O(Tn​)=O(21​+22​+23​+...+2n−1​)=O(4n(n−1)​)=O(n2)

    3.1.2 空间复杂度分析

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

    O ( S n ) = O ( 1 ) O(S_n) = O(1) O(Sn​)=O(1)

    3.2 稳定性与排序方式

    算法稳定性排序方式
    直接插入排序可以稳定内部排序
    3.2.1 稳定性分析

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

    3.2.2 排序方式分析

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

    四、相关习题

    注：习题不保证与上述算法一定相关，只是可能相关

    4.1 编程题

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

      4.2 选择题

      • 牛客 - 试题广场

        1. 直接插入排序 · 百度百科 ↩︎

The End

标签：

微信