Insertion Sort

1. 排序简介

排序通常指把毫无规律的数据，按照一种特定的规律，整理成有序排列的状态。一般情况下，排序算法按照关键字的大小，以从小到大或从大到小的顺序将数据排列。

排序算法是最基础也最重要的算法之一，在处理大量数据时，使用一个优秀的排序算法可以节省大量时间和空间。因为不同的排序算法拥有不同的特点，所以我们根据情况选择合适的排序算法。

直观地讲，插入排序算法把给定数组中的元素依次插入到一个新的数组中，最终得到一个完整的有序数组。

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。

具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

图 1 展示了数组插入元素的操作流程。设基准元素为 base ，我们需要将从目标索引到 base 之间的所有元素向右移动一位，然后将 base 赋值给目标索引。

2. 插入排序效率分析

插入排序的平均时间复杂度是 $O(n^2)$，最好情况下的时间复杂度是 $O(n)$，最坏情况下的时间复杂度是 $O(n^2)$，它的空间复杂度是 $O(1)$。

插入排序还是一个稳定的排序算法。这里涉及到一个新的概念：排序算法的稳定性。

排序算法可以分为稳定的算法和不稳定的算法两类。

在一个数组中，我们假设存在多个有相同关键字的元素。如果使用算法进行排序后，这些具有相同关键字的元素相对顺序一定保持不变，那么我们称这个排序算法为稳定的排序算法。

冒泡排序、插入排序和归并排序等都是稳定的排序算法。而不能保证这些元素排序前后的相对位置相同的算法，就是不稳定的排序算法。选择排序，希尔排序和快速排序等都是不稳定的排序算法。

公众号：AI悦创【二维码】