使用python代码举例说明插入排序

插入排序是一种简单的排序算法，它的基本思想是将待排序的元素插入到已经排好序的序列中，从而得到一个新的有序序列。

下面是一个使用 Python 代码实现插入排序的示例：

def insert_sort(arr):
    # 从第二个元素开始循环，因为第一个元素默认是有序的
    for i in range(1, len(arr)):
        # 从后往前比较，如果当前元素比前一个元素小，就交换位置
        while i > 0 and arr[i] < arr[i-1]:
            arr[i], arr[i-1] = arr[i-1], arr[i]
            i -= 1
    return arr

# 测试代码
print(insert_sort([3, 5, 2, 4, 1]))  # [1, 2, 3, 4, 5]
print(insert_sort([1, 2, 3, 4, 5]))  # [1, 2, 3, 4, 5]
print(insert_sort([5, 4, 3, 2, 1]))  # [1, 2, 3, 4, 5]

在上面的代码中，我们使用了一个外层循环和一个内层循环。外层循环每次拿出一个元素来，内层循环则用来寻找这个元素应该插入的位置。每次内层循环都会将当前元素与前面的元素进行比较，如果当前元素小，就交换位置，直到找到一个比当前元素大的元素或者到达序列的开头为止。

插入排序的时间复杂度是 O(

相关问题

使用python代码举例说明希尔排序

希尔排序是一种插入排序算法，其特点在于使用了较大的间隔将数组分组，然后对每组内的元素进行插入排序。这样可以让数组的局部有序，最终使整个数组有序。

下面是一个使用 Python 实现希尔排序的示例代码：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

# 测试
print(shell_sort([5, 2, 3, 1, 4]))  # 输出 [1, 2, 3, 4, 5]

在上面的代码中，首先我们定义了一个名为 `shell_sort` 的函数，该函数接受一个数组作为参数。然后我们使用 `gap` 变量记录间隔的大小，初始时将其设为数组长度的一半。接着我们进入一个 `while` 循环，当 `gap` 大于 0 时继续执行。在循环内部，我们使用一个 `for` 循环遍历数组中的每一项，对于每一项我们使用插入排序的方式将其插入到正确的位置。最后我们将 `gap` 除以 2，继续下一轮循环。当 `gap` 变为 0 时，循环结束，数组就已经被排好序了。