Python实现十大经典排序算法_python 快速排序

冒泡排序选择排序插入排序希尔排序（对插入排序的改进）归并排序快速排序（对冒泡排序的改进）堆排序计数排序桶排序基数排序时间复杂度对比

冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

nums = [3, 7, 2, 8, 1, 4, 6, 5]
# 外层循环控制循环次数
for i in range(1, len(nums)):
    # 内层循环控制比较次数
    for j in range(len(nums)-i):
        if nums[j] > nums[j+1]:
            nums[j], nums[j+1] = nums[j+1], nums[j]
print(nums)

选择排序

1. 从待排序列表中找到最小的元素(升序排列，降序排列则找最大的元素)，存放到列表的起始位置，作为已排序的序列。

2. 继续从未排序序列中找到最小的元素，存放到已排序序列的末尾(同时也是未排序序列的起始位置)。

3. 重复第2步，直到所有元素都已经存放到了已排序序列，则列表排序完成。

• 第一次遍历找到最小元素

• 第二次在剩余数组中遍历找到次小元素

• ···

• 第n次在剩余数组中遍历找到第n小元素

# 外层循环控制循环次数
nums = [3, 7, 2, 8, 1, 4, 6, 5]
for i in range(len(nums)-1):
    min_idx = i
    # 内层循环找出最小元素
    for j in range(i+1, len(nums)):
        if nums[j] < nums[min_idx]:
            min_idx = j
    # 与第一个元素交换位置
    nums[i], nums[min_idx] = nums[min_idx], nums[i]
print(nums)

插入排序

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。

2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。

3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

• 将数组待排序元素依次插入到已排序部分，使已排序部分保持升序的性质

nums = [3, 7, 2, 8, 1, 4, 6, 5]
for i in range(1, len(nums)):
    j = i
    # 将遍历到的元素依次插入到该元素左边序列中
    while j > 0 and nums[j] < nums[j-1]:
        nums[j], nums[j-1] = nums[j-1], nums[j]
        # 继续往前遍历
        j -= 1
print(nums)

希尔排序（对插入排序的改进）

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

nums = [3, 7, 2, 8, 1, 4, 6, 5]
n = len(nums)
# 定义增量
gap = n // 2
while gap:
    for i in range(gap, n):
        # 分组插入排序
        while i >= gap and nums[i] < nums[i-gap]:
            nums[i], nums[i-gap] = nums[i-gap], nums[i]
            i -= gap
    # 缩小增量
    gap //= 2
print(nums)

归并排序

1. 假设有两个已经有序的列表，设定两个指针分别指向这两个列表的起始元素，申请内存空间新建一个空列表，比较两个指针指向的元素大小，将较小的元素添加到新列表中，然后将该指针向该列表的下一个元素偏移，继续比较两个指针指向的元素和添加较小的到新列表中。直到其中一个列表的数据全部被添加完时，把另一个列表中剩下的数据按顺序添加到新列表中。这就实现了将两个有序列表合并成一个新的有序列表的方法。

2. 对待排序列表进行拆分，递归地拆分直到子列表中只有一个元素。

3. 只有一个元素的子列表一定是有序的，使用1中的方法对有序的子列表进行合并。第一次合并后新列表是有两个元素的有序列表，递归地往回合并，直到所有数据都合并到一个新的有序列表中，列表排序完成。

分而治之：分解数组 递归求解 合并排序

• 分解原问题： 将数组声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】