插入排序python算法
时间: 2023-12-25 09:30:05 浏览: 51
插入排序是一种简单的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
以下是插入排序的Python实现:
```python
def insertion_sort(arr):
# 遍历从1到n的所有元素
for i in range(1, len(arr)):
# 当前需要排序的元素
key = arr[i]
# 比较key的位置和key值大于等于i时的元素
j = i - 1
while j >= 0 and key < arr[j] :
# 如果key小于当前元素,交换元素的位置并更新i的位置
arr[j + 1] = arr[j]
j -= 1
# 元素交换完毕后,就移动到了正确的位置,将其放置在该位置上
arr[j + 1] = key
return arr
```
这段代码的基本步骤是:从第二个元素开始,假设第一个元素已排序,并将其放入它应处的地方。然后将该元素后的所有元素依次向前移动一位。继续此过程,直到数组中的所有元素都已排序。这种方法的一个优点是,即使对于非常大范围的数组,它也非常有效。插入排序的一个主要缺点是它的工作量是数组的一半,因此对于非常大的数组来说效率较低。
使用这个函数的基本方式如下:
```python
arr = [5, 3, 7, 6, 2, 8, 9, 1, 4]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # 输出:[1, 2, 3, 4, 5, 6, 7, 8, 9]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)