使用插入排序对给定数组从小到大排序,不需要输出排序后的数组,需输出从第二个元素开始每个元素 插入的的位置。思路及代码
时间: 2024-03-10 12:50:52 浏览: 52
有一个从小到大排好序的数组。现输入一个数,要求按原来的规律将它插入数组中。
插入排序的思路是从第二个元素开始遍历,将该元素插入到已经排好序的子数组中的合适位置。具体实现可以使用两层循环,外层循环遍历整个数组,内层循环从当前元素开始向前遍历已经排好序的子数组,找到该元素的正确位置并插入。
以下是使用插入排序对给定数组从小到大排序,并输出每个元素插入的位置的代码:
```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
print(f"Insert {key} into position {j+2}")
```
其中,arr是待排序的数组,insertion_sort函数会将其从小到大排序,并输出每个元素插入的位置。具体实现中,使用key保存当前遍历的元素,j从当前元素的前一个元素开始向前遍历已经排好序的子数组,找到该元素的正确位置并插入。在插入过程中,将j之后的元素都向后移动一位,最终将key插入到正确的位置上,并输出该元素插入的位置。
使用该函数,可以对给定数组进行排序并输出每个元素插入的位置,如下所示:
```python
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
```
输出结果为:
```
Insert 2 into position 1
Insert 4 into position 2
Insert 5 into position 3
Insert 6 into position 4
Insert 1 into position 1
Insert 3 into position 3
```
阅读全文