征婚网站开发,网站安全建设模板,推广网站设计推广方案,专业网站建设排名1. 概念及原理 插入排序是一种简单直观的排序算法#xff0c;其基本思想是将一个元素插入到已经排序好的部分#xff0c;然后不断地重复这个过程#xff0c;直到整个数组有序。下面是插入排序的算法原理#xff1a;
初始状态#xff1a; 数组被分为已排序和未排序两个部分…
1. 概念及原理 插入排序是一种简单直观的排序算法其基本思想是将一个元素插入到已经排序好的部分然后不断地重复这个过程直到整个数组有序。下面是插入排序的算法原理
初始状态 数组被分为已排序和未排序两个部分初始时已排序部分只包含第一个元素未排序部分包含其余元素。迭代过程 从未排序部分选择一个元素将其与已排序部分的元素依次比较找到合适的位置插入。插入过程中已排序部分中的元素不断向右移动为新元素腾出位置。重复 重复上述过程直到未排序部分为空整个数组有序。 下面是一个简单的例子演示了插入排序的过程 初始数组[12, 11, 13, 5, 6]
第一次迭代已排序部分[12]未排序部分[11, 13, 5, 6]。选择11与12比较交换位置得到已排序部分[11, 12]未排序部分[13, 5, 6]。第二次迭代已排序部分[11, 12]未排序部分[13, 5, 6]。选择13与12比较不需要交换位置得到已排序部分[11, 12, 13]未排序部分[5, 6]。以此类推最终得到已排序的数组[5, 6, 11, 12, 13]。 插入排序的时间复杂度为O(n^2)其中n是数组的长度。这是因为对于每个元素它需要与已排序部分的元素依次比较最坏情况下需要比较n次。在最优情况下即数组已经有序时时间复杂度为O(n)因为不需要移动已排序部分的元素。插入排序是一种稳定的排序算法适用于小型数组或基本有序的数组。
2. 示意图 3. 代码实现
def insertion_sort(arr):# 遍历数组从第二个元素开始for i in range(1, len(arr)):key arr[i]j i - 1# 将比当前元素大的元素向右移动while j 0 and key arr[j]:arr[j 1] arr[j]j - 1# 将当前元素插入到正确的位置arr[j 1] key# 示例用法
my_array [12, 11, 13, 5, 6]
insertion_sort(my_array)print(排序后的数组:, my_array)
