用python列表实现插入并排序的算法,要求不使用sort函数,给出完整代码
时间: 2023-05-26 12:04:36 浏览: 57
以下是使用Python列表实现插入排序算法的完整代码:
```python
def insertion_sort(array):
for i in range(1, len(array)):
key = array[i]
j = i - 1
while j >= 0 and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
return array
if __name__ == "__main__":
array = [3, 2, 1, 5, 4]
sorted_array = insertion_sort(array)
print(sorted_array) # 输出:[1, 2, 3, 4, 5]
```
算法的核心是对于每个未排序的元素,将其插入到有序部分中正确的位置。具体地,在第`i`次迭代中,算法将`array[i]`插入到前面的有序序列中。插入的操作是通过从`i`开始向前扫描来完成的,如果前面的元素大于`array[i]`,则将其向右移动一位,直到找到插入的位置。最后,将`array[i]`插入到该位置。
时间复杂度为`O(n^2)`,是一种简单但不是高效的排序算法。
相关问题
用python列表实现用户插入并对插入后的列表排序的算法,要求不使用sort函数,给出完整代码
以下是完整的Python代码,实现了用户插入并对插入后的列表排序的算法,不使用sort函数。
```python
# 初始化列表
lst = []
# 获取用户输入,以空格分隔多个元素
user_input = input("请输入多个数字,以空格分隔:")
# 将用户输入的字符串转换成列表
lst = user_input.split()
# 将列表中的每个元素转换成整数
lst = [int(x) for x in lst]
# 定义插入排序函数
def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
# 调用插入排序函数
insertion_sort(lst)
# 输出排序后的列表
print("排序后的列表为:", lst)
```
运行结果如下:
```
请输入多个数字,以空格分隔:5 8 3 6 2
排序后的列表为: [2, 3, 5, 6, 8]
```
该算法中,通过input函数获取用户输入的元素,并使用split函数将其转换成列表;然后,通过插入排序算法对列表进行排序;最后,输出排序后的列表。
Python不使用sort函数实现数组排序
可以使用其他排序算法来实现数组排序,比如冒泡排序、插入排序或选择排序等。以下是一个使用冒泡排序算法来排序数组的示例代码:
```python
def bubble_sort(arr):
n = len(arr)
# 遍历数组元素
for i in range(n - 1):
# 每次遍历找出最大的元素并放到末尾
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 测试示例
array = [5, 2, 8, 12, 3]
bubble_sort(array)
print(array)
```
这段代码使用了冒泡排序算法,每次遍历都将最大的元素冒泡到末尾。输出结果为 `[2, 3, 5, 8, 12]`,表示数组已成功排序。你可以根据需要选择不同的排序算法来实现数组排序。