插入排序是一种简单直观的排序算法,其工作原理类似于我们平时整理扑克牌或书籍的方式。它的核心思想是将数组分为已排序和未排序两部分,每次从未排序部分取出一个元素,将其插入到已排序部分的适当位置,从而保持已排序部分的有序性。
插入排序的原理
1)初始状态:假设数组的第一个元素是已排序的,其余元素是未排序的。
2)遍历:从数组的第二个元素开始,依次取出每一个元素。
3)插入:对于每一个取出的元素,将其与已排序部分的元素进行比较,找到其应该插入的位置,并将其插入。
4)重复:重复上述步骤,直到所有元素都被插入到已排序部分,此时整个数组即为有序。
Python代码实现
def insertion_sort(arr): # 遍历从第二个元素到最后一个元素 for i in range(1, len(arr)): key = arr[i] # 当前需要插入的元素 j = i - 1 # 将key插入到已排序部分的适当位置 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] # 将arr[j]向右移动一位 j -= 1 arr[j + 1] = key # 插入key return arr # 测试代码
if __name__ == "__main__": arr = [12, 11, 13, 5, 6] print("排序前的数组:", arr) sorted_arr = insertion_sort(arr) print("排序后的数组:", sorted_arr)