数据结构与算法-插入排序_业界新闻

发布时间:2024-07-29 13:09

阅读量:0

💝💝💝首先，欢迎各位来到我的博客，很高兴能够在这里和您见面！希望您在这里不仅可以有所收获，同时也能感受到一份轻松欢乐的氛围，祝你生活愉快！

文章目录

引言

插入排序是一种简单直观的排序算法，它的工作原理类似于人们整理手中的一叠卡片。该算法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常使用in-place排序（即只需用到O(1)的额外空间），其时间复杂度为O(n^2)，其中n是待排序数组的长度。

一、插入排序的基本思想

插入排序的基本思想是：

将数组分为已排序和未排序两个部分。
初始时，已排序部分只包含数组的第一个元素，其余元素视为未排序部分。
从未排序部分取出一个元素，与已排序部分的元素依次比较，找到合适的位置插入。
重复上述步骤，直到所有元素都被插入到已排序部分。

二、插入排序的步骤

假设有一个数组 arr 需要进行排序。

初始化：将第一个元素视为已排序部分，剩余元素视为未排序部分。
遍历：从未排序部分选取第一个元素 arr[j]。
比较与交换：将 arr[j] 与已排序部分的元素 arr[i] 进行比较，如果 arr[j] 更小，则交换位置，否则继续与前面的元素比较。
重复：重复上述步骤，直到 arr[j] 被正确插入到已排序部分。
完成：当所有元素都被正确插入到已排序部分时，排序完成。

三、插入排序的实现

接下来，我们将通过一个示例来详细了解插入排序的实现步骤。

1. 示例数组

考虑一个整数数组 arr = [5, 2, 4, 6, 1, 3]。

2. 伪代码

以下是插入排序的基本伪代码：

for i = 1 to n-1 do     key = arr[i]     j = i - 1     while j >= 0 and arr[j] > key do         arr[j+1] = arr[j]         j = j - 1     end while     arr[j+1] = key end for

3. Python 实现

下面是一个使用Python编写的插入排序算法的具体实现：

def insertion_sort(arr):     # 获取数组的长度     n = len(arr)      # 从第二个元素开始遍历数组     for i in range(1, n):         # 保存当前元素，它将被插入到已排序的部分         key = arr[i]          # 初始化j为当前元素的前一个位置         j = i - 1          # 将大于key的元素向右移动一位         while j >= 0 and arr[j] > key:             arr[j + 1] = arr[j]             j -= 1          # 将key插入到正确的位置         arr[j + 1] = key      return arr  # 示例数组 arr = [5, 2, 4, 6, 1, 3] # 调用函数 sorted_arr = insertion_sort(arr) print(sorted_arr)