为什么插入排序是稳定的
时间: 2023-11-24 20:50:47 浏览: 248
插入排序是稳定的,因为在排序过程中,对于相等的元素,不会改变它们之间的相对位置。具体来说,插入排序是通过将一个元素插入到已排序的序列中来排序的。当插入一个元素时,如果它与已排序的序列中的某个元素相等,那么它会被插入到相等元素的后面,从而保持了它们之间的相对位置不变。因此,插入排序是稳定的。
以下是一个Python实现插入排序的例子:
```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
```