用python列表实现插入并排序的算法，要求不使用sort函数，给出完整代码

以下是使用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函数。

# 初始化列表
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

实现插入排序的 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 传入，可得到其按递增顺序排列的新数组。

a = [9, 5, 1, 4, 3, 7, 6]
sorted_a = insertion_sort(a)
print(sorted_a)  # 输出为 [1, 3, 4, 5, 6, 7, 9]