插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常使用in-place排序(即只需用到O(1)的额外空间的排序),因为在排序的过程中,会将元素一边移动,一边向前寻找插入位置。
下面是插入排序的详细描述:
1. **初始化**:将数组视作有序,从第一个元素开始,该元素可以认为已经被排序。
2. **比较与移动**:取出下一个元素,在已经排序的元素序列中从后向前扫描。
3. **插入**:如果该元素(已排序)大于新元素,将该元素移到下一位置,继续比较,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后。
4. **重复**:重复步骤2和3,直到所有元素都被排序。
5. **结束**:当最后一个元素被插入到序列中时,整个排序过程结束。
插入排序的效率依赖于已经排序的元素的数量。如果数组已经是基本有序的,插入排序将非常高效。在最坏的情况下,即数组完全逆序,每个新元素都需要与已排序的元素依次比较并插入到最前面,此时插入排序的时间复杂度为O(n^2),其中n是数组的长度。
插入排序的优点是实现简单,对于小规模数据排序是有效的,特别是当输入数组基本有序时。但它的缺点是移动元素的次数较多,对于大规模数据排序效率较低。在实际应用中,它通常用作较小数据集的排序算法,或者作为其他排序算法(如快速排序)的辅助排序算法。
```python
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
return arr
# 测试
arr = [5, 2, 8, 3, 9, 1]
sorted_arr = insertion_sort(arr)
print(sorted_arr)
```