python插入排序，输入一系列数字进行排序

插入排序是一种简单直观的排序算法，它的工作原理类似于整理扑克牌的过程。对于Python实现插入排序，我们可以按照以下步骤：

1. **遍历数组**：从第二个元素开始，假设当前元素为`arr[i]`。

2. **比较和插入**：将当前元素与前面已排序的部分逐个比较，找到合适的位置插入，使其保持有序。如果`arr[i]`小于前一个元素，就将其移动到前面；反之则继续向前查找并插入。

3. **递归过程**：重复以上步骤，直到所有元素都插入到正确位置，整个数组就排好序了。

以下是简单的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

# 测试
numbers = [4, 2, 9, 6, 5, 1]
sorted_numbers = insertion_sort(numbers)
print("Sorted array:", sorted_numbers)

相关问题

python希尔排序

希尔排序是一种插入排序的改进算法，它通过将待排序的元素按照一定间隔分组，然后对每组进行插入排序的方式来进行排序。希尔排序的代码如下：

nums = [5,3,6,4,1,2,8,7]

def ShellSort(nums):
    step = len(nums)//2   #初始化增量为数组长度的一半
    while step > 0:       #增量必须是大于0的整数
        for i in range(step,len(nums)):  #遍历需要进行插入排序的数
            ind = i
            while ind >= step and nums[ind < nums[ind-step]:   #对每组进行插入排序
                nums[ind],nums[ind-step = nums[ind-step],nums[ind]
                ind -= step
        step //= 2   #增量缩小一半
    print(nums)

ShellSort(nums)

以上代码使用了希尔排序的思想来对给定数组nums进行排序。具体步骤如下：
1. 初始化增量step为数组长度的一半。
2. 当增量step大于0时，进行以下操作：
- 遍历数组中需要进行插入排序的元素，从第step个元素开始。
- 对每组进行插入排序，即将当前元素与其前step个元素比较并交换位置，直到找到合适的位置或者前面没有更小的元素为止。
- 重复上述过程，直到将整个数组排序完成。
3. 增量step缩小一半，并继续进行上述操作，直到增量为1。
4. 打印排序后的数组。

希尔排序的时间复杂度一般为O(n^1.3)～O(n^2)，具体取决于增量的选择。希尔排序的空间复杂度为O(1)，它是一个不稳定的排序算法。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [【python算法系列三】 希尔排序算法](https://blog.csdn.net/m0_70372647/article/details/124808637)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [undefined](undefined)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [python排序算法——希尔排序（附代码）](https://blog.csdn.net/AOAIYI/article/details/128717484)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]

用python代码表示直接插入排序（输入数据在运行时输入）：将第i个数据插入已经排好序的有序数据中，从而得到一个新的、个数多1的有序数据。算法适用于少量数据的排序，首先将第一个作为已经排好序的，然后每次以后的取出插入到前面并排序。

好的，下面是一个使用 Python 实现直接插入排序算法的示例代码。这个版本允许用户在程序运行时输入待排序的数据。

### 直接插入排序算法解释
直接插入排序是一种简单直观的排序方法，它的工作原理是从第二个元素开始遍历整个序列，并将其逐个插入到之前已排序的部分中合适的位置上。对于每个新元素，我们需要从当前有序部分的最后一项向前扫描，找到它的正确位置后进行插入。

下面是具体的Python代码实现：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # 将key插入到已经排好序的序列中
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

if __name__ == "__main__":
    input_str = input("请输入一系列整数（用空格分开）：")
    
    try:
        numbers = list(map(int, input_str.split()))
        print("原始数组:", numbers)

        insertion_sort(numbers)
        
        print("排序后的数组:", numbers)

    except ValueError as e:
        print(f"无效输入: {e}")

#### 运行流程：
1. 用户被提示输入一组由空格分隔开来的整数值；
2. 程序读取用户的输入并将它们转换成一个整型列表；
3. 调用 `insertion_sort()` 函数对该列表进行排序；
4. 输出原数组以及经过排序处理的新数组；

如果您希望了解更多的关于此算法的信息或是遇到其他相关的问题，请随时提问！

---