用列表实现插入排序算法
时间: 2024-02-03 20:02:57 浏览: 16
以下是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
arr = [5, 2, 4, 6, 1, 3]
print(insertion_sort(arr)) # 输出 [1, 2, 3, 4, 5, 6]
相关问题
python用列表实现插入排序算法
以下是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 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = insertion_sort(arr)
print(sorted_arr)
```
以上代码将输出已排序的列表:
```
[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
```
用列表实现插入排序算法,python
实现插入排序的 Python 代码如下所示:
```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
```
在这个函数中,我们首先迭代数组并针对每一个元素执行该操作:我们为这个元素设置关键值,也就是要排序的值,然后将其与此前的那些元素进行比较,以确定关键值在有序数组(稍后生成)中所处的位置。
在代码中,我们使用 while 循环,将 j 从当前位置减一(它的初始值是i-1)开始迭代,如果存在当前元素 arr[j] 比关键值 key 大的情况(因为 arr 已经部分排序过了),我们移动 arr[j] 一个位置到其右边,以便在之后的循环迭代中给关键值 key 腾出合适的位置。
最后,我们为关键值 key 腾出的位置赋值,并按照序列 idx 一直迭代到其末尾。接着将有序列表返回即可。
下面是该算法使用的示例。假设数组 a 中有7个值,需要对它们进行排序。调用 insertion_sort 函数,将需要排序的数组 a 传入,可得到其按递增顺序排列的新数组。
```python
a = [9, 5, 1, 4, 3, 7, 6]
sorted_a = insertion_sort(a)
print(sorted_a) # 输出为 [1, 3, 4, 5, 6, 7, 9]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)