4.插入排序

算法 > 排序算法算法排序算法

发布时间 : 2024-04-14 17:27

字数:1.9k 阅读 :

评论:

4.插入排序

4.插入排序

4.1 基础知识

核心思想

每一轮将未排序区的元素插入已排序区的合适位置，不断扩大已排序区域，缩小未排序区域，直到完成排序。

算法步骤

初始状态：
- 将整个数组分为已排序区和未排序区，初始时已排序区只包含第一个元素，未排序区为剩余的元素。
每一轮插入元素：
- 从未排序区选择第一个元素，将其插入已排序区的合适位置。插入时，从已排序区的末尾开始比较，依次向前找到合适的位置。
更新已排序区和未排序区：
- 将已排序区的范围扩大，未排序区的范围缩小。已排序区的末尾即为刚刚插入的元素的位置。
重复直至排序完成：
- 重复上述步骤，直至未排序区为空。每一轮插入操作都会将未排序区的一个元素插入到已排序区，最终完成整个数组的排序。

时间复杂度

插入排序的最坏情况下的时间复杂度为O(n^2)，平均和最好情况下为O(n)。在已排序或近乎已排序的情况下，插入排序的性能较好。

空间复杂度

插入排序是一种原地排序算法，空间复杂度为O(1)。

稳定性

插入排序是稳定的。相同元素的相对顺序在排序前后不会改变。

适用场景

插入排序适用于小规模数据或基本有序的数据集。由于其简单且稳定的特性，插入排序在实际应用中常被用于对已近乎有序的数据进行排序，或者作为其他高级排序算法的一部分。

代码步骤

外层循环：
- 通过外层循环，控制待插入的元素的索引。从第二个元素开始（索引为1），因为第一个元素被认为已经是有序的。
当前待插入元素：
- 在每一轮开始时，将当前待插入的元素记录为 currentElement。
内层循环找插入位置：
- 通过内层循环，在已排序区域中寻找合适的插入位置。从已排序区的末尾开始，比较已排序区的元素与 currentElement 的大小，如果已排序区的元素较大，就将该元素向后移动一个位置。
插入当前元素：
- 在找到合适的插入位置后，将 currentElement 插入到已排序区域的正确位置。这是通过在内层循环结束后，将 currentElement 赋值给 array[j + 1] 实现的，其中 j + 1 是 currentElement 应该插入的位置。
输出插入后的数组：
- 在每次插入后，输出当前数组的状态，显示排序的过程。
重复直到完成：
- 通过不断重复上述步骤，直到整个数组完全有序。每一轮都会将当前待插入的元素插入到已排序区域的正确位置。

总结说明

尽管插入排序的最坏情况时间复杂度较高，但在某些场景下，由于其稳定性和对部分有序数据的高效处理，它仍然是一个实用的排序算法。在面对小规模数据或已基本有序的数据时，插入排序可以是一个简单而有效的选择。然而，对于大规模数据集，其他高效的排序算法可能更为合适。

4.2 思路框架

static void InsertionSort(ref int[] array)
{
    循环：从数组的第二个元素开始，因为第一个元素默认已排序
    {
        将当前元素值保存到临时变量中
        
        定义指针，用于比较当前元素和已排序部分的元素，初始值是排序区末尾元素索引

        循环：将当前元素与排序区元素逐个比较并移动，只要没越界且当前元素值比排序区的小就一直移动
        {
            覆盖当前指正后一元素值且指针往前移
        }

        出循环代表找到合适的插入位置，将当前元素值覆盖到指正后一元素中
    }
}

require("Lesson01_SortHelpTool")

-- 插入排序函数
function InsertionSort(array)

    for i = 2, #array do

        local currentElement = array[i]

        local j = i - 1

        while j >= 1 and array[j] > currentElement do
            array[j + 1] = array[j]
            j = j - 1
        end

        array[j + 1] = currentElement

    end
    
end

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")

InsertionSort(SortHelpTool.arrayToSort)

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")

4.3 纯净代码

static void InsertionSort(ref int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        int currentElement = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > currentElement)
        {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = currentElement;
    }
}

4.4 带注释代码

using System;
using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用插入排序函数
        InsertionSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 插入排序函数
    static void InsertionSort(ref int[] array)
    {
        // 从1开始，默认第一个数已经排序，代表取出来的未排序区的第一个元素，数组有多长，就有多少-1轮的插入操作
        for (int i = 1; i < array.Length; i++)
        {
            // 当前待插入元素
            int currentElement = array[i];

            // i - 1代表从已排序区的末尾开始比较
            int j = i - 1;

            // 在已排序区寻找插入位置，只要未到已排序区头，且当前比较的已排序区元素大于当前待排序元素，就继续往前移动比较，找到合适位置的插入
            while (j >= 0 && array[j] > currentElement)
            {
                // 移动元素，为当前元素腾出插入位置
                array[j + 1] = array[j];
                // 继续往前移动比较
                j--;
            }

            // 插入当前元素到正确位置，j+1是因为while中将已经将比currentElement大的元素都向后移动了一个位置并让j--继续往前进行比较，所以插入位置就是j+1。
            array[j + 1] = currentElement;

            // 输出排序中的数组
            Console.WriteLine($"第{i}轮 插入元素{currentElement}到正确位置 插入后的数组:");
            SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
        }
    }
}

4.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

第1轮插入元素2到正确位置插入后的数组:
2 5 8 1 7 3 10 4 6 9
第2轮插入元素8到正确位置插入后的数组:
2 5 8 1 7 3 10 4 6 9
第3轮插入元素1到正确位置插入后的数组:
1 2 5 8 7 3 10 4 6 9
第4轮插入元素7到正确位置插入后的数组:
1 2 5 7 8 3 10 4 6 9
第5轮插入元素3到正确位置插入后的数组:
1 2 3 5 7 8 10 4 6 9
第6轮插入元素10到正确位置插入后的数组:
1 2 3 5 7 8 10 4 6 9
第7轮插入元素4到正确位置插入后的数组:
1 2 3 4 5 7 8 10 6 9
第8轮插入元素6到正确位置插入后的数组:
1 2 3 4 5 6 7 8 10 9
第9轮插入元素9到正确位置插入后的数组:
1 2 3 4 5 6 7 8 9 10

排序后的数组:
1 2 3 4 5 6 7 8 9 10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com