python插入排序3+快速排序 python3

插入排序：

插入排序是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是使用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

arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print(arr)  # 输出：[1, 2, 3, 4, 5, 6]

在插入排序算法中，我们通过一个循环遍历未排序部分的每个元素，并将其依次插入已排序序列的正确位置。具体步骤如下：

1. 从第二个元素开始，将其作为key。
2. 将key和已排序部分的最后一个元素比较，若key较小，则将该元素向后移动。
3. 重复步骤2直到找到比key小的元素或到达已排序序列的开头。
4. 将key插入到正确位置。

快速排序：

快速排序是一种高效的排序算法，利用递归和分治的思想。它首先选择一个基准元素，然后将待排序序列分成两部分，左边的元素小于基准元素，右边的元素大于基准元素，然后递归地对两部分序列进行排序。以下是使用Python实现快速排序的示例代码：

def quick_sort(arr):
    if len(arr) <= 1:  # 基线条件：如果序列长度小于等于1，直接返回
        return arr
    pivot = arr[len(arr) // 2]  # 选择基准元素
    left = [x for x in arr if x < pivot]  # 小于基准元素的子序列
    middle = [x for x in arr if x == pivot]  # 等于基准元素的子序列
    right = [x for x in arr if x > pivot]  # 大于基准元素的子序列
    return quick_sort(left) + middle + quick_sort(right)  # 递归排序左、右子序列后拼接起来

arr = [5, 2, 4, 6, 1, 3]
arr = quick_sort(arr)
print(arr)  # 输出：[1, 2, 3, 4, 5, 6]

快速排序算法的关键在于如何选择基准元素及分治的过程。以下是快速排序算法的实现步骤：

1. 选择基准元素，一般选择序列中的中间元素。
2. 将序列分成两部分，左边的元素小于基准元素，右边的元素大于基准元素。
3. 递归地对左、右子序列进行快速排序。
4. 将左、右子序列和基准元素拼接起来。

总结：

插入排序和快速排序都是常见的排序算法，它们都可以使用Python来实现。插入排序的时间复杂度为O(n^2)，当序列基本有序时效果较好；快速排序的时间复杂度为O(nlogn)，在大多数情况下效率较高。

插入排序通过构建有序序列来逐个插入元素，而快速排序通过选择基准元素和分治的过程来将序列分成两部分进行递归排序。两者在实现上有一定的差异，但都可以有效地对序列进行排序。

当需要对一个较小规模的序列进行排序时，可以选择插入排序；当需要对一个较大规模的序列进行排序时，可以选择快速排序。因此，在实际应用中，需要根据不同的情况选择合适的排序算法来提高排序效率。

综上所述，插入排序和快速排序是两种常见的排序算法，在Python中都可以使用简单明了的代码实现。通过对比这两种算法的特点和实现过程，我们可以选择合适的算法来满足不同的排序需求。