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中的方法对有序的子列表进行合并。第一次合并后新列表是有两个元素的有序列表，递归地往回合并，直到所有数据都合并到一个新的有序列表中，列表排序完成。

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

• 分解原问题： 将数组푨[ퟏ, 풏] 排序问题分解为푨[ퟏ, 풏 / ퟐ ]和푨[ 풏 / ퟐ + ퟏ, 풏]排序问题

• 解决子问题：递归解决子问题得到两个有序的子数组

• 合并问题解：将两个有序子数组合并为一个有序数组

nums = [3, 7, 2, 8, 1, 4, 6, 5]
​
def merge_sort(nums):
    # 递归结束条件
    if len(nums) < 2:
        return nums
    left = merge_sort(nums[:len(nums)//2])
    right = merge_sort(nums[len(nums)//2:])
    return merge(left, right)
​
def merge(left, right):
    l = r = 0
    res = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l += 1
        else:
            res.append(right[r])
            r += 1
    # 添加剩余部分
    res += left[l:]
    res += right[r:]
    return res
​
print(merge_sort(nums))

1. 从待排序列表中选取一个基准数据(通常选取第一个数据)。

2. 将待排序列表中所有比基准数据小的元素都放到基准数据左边，所有比基准数据大的元素都放到基准数据右边(升序排列，降序反之)。用基准数据进行分割操作后，基准数据的位置就是它最终排序完成的位置，第一轮排序完成。

3. 递归地对左右两个部分的数据进行快速排序。即在每个子列表中，选取基准，分割数据。直到被分割的数据只有一个或零个时，列表排序完成。

• 首先设定一个分界值，通过该分界值将数组分成左右两部分

• 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值

• 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理

• 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了

nums = [3, 7, 2, 8, 1, 4, 6, 5]
​
def quick_sort(li):
    if len(li) < 2:
        return li
    mid = li.pop(len(li)//2)
    l, r = [], []
    for x in li:
        if x < mid:
            l.append(x)
        else:
            r.append(x)
    return quick_sort(l) + [mid] + quick_sort(r)
​
# 逐一赋值
def quick_sort(nums):
    l, r = 0, len(nums)-1
    # 数组为空或只有一个元素
    if l >= r:
        return nums
    # 定义初始值
    key = nums[l]
    while l < r:
        # 找到小的值放到左边
        while l < r and nums[r] >= key:
            r -= 1
        nums[l] = nums[r]
        # 找到大的值放到右边
        while l < r and nums[l] <= key:
            l += 1
        nums[r] = nums[l]
    # 将初始值赋值给相遇的位置
    nums[l] = key
    return quick_sort(nums[:l]) + [key] + quick_sort(nums[l+1:])
​
# 两者交换
def quick_sort(nums):
    l, r = 0, len(nums)-1
    if l >= r:
        return nums
    # 定义初始索引
    p = l
    while l < r:
        while l < r and nums[r] >= nums[p]:
            r -= 1
        while l < r and nums[l] <= nums[p]:
            l += 1
        # 用索引交换
        nums[l], nums[r] = nums[r], nums[l]
    nums[l], nums[p] = nums[p], nums[l]
    return quick_sort(nums[:l]) + [nums[l]] + quick_sort(nums[l+1:])

1. 将待排序列表中的数据按从上到下、从左到右的顺序构造成一棵完全二叉树。

2. 将完全二叉树中每个节点(叶节点除外)的值与其子节点(子节点有一个或两个)中较大的值进行比较，如果节点的值小于子节点的值，则交换他们的位置(大顶堆，小顶堆反之)。

3. 将节点与子节点进行交换后，要继续比较子节点与孙节点的值，直到不需要交换或子节点是叶节点时停止。比较完所有的非叶节点后，即可构建出堆结构。

4. 将数据构造成堆结构后，将堆顶与堆尾交换，然后将堆尾从堆中取出来，添加到已排序序列中，完成一轮堆排序，堆中的数据个数减1。

5. 重复步骤2,3,4，直到堆中的数据全部被取出，列表排序完成。

nums = [3, 7, 2, 8, 1, 4, 6, 5]
def heap_sort(nums):
    n = len(nums)
    # 最后一个非叶节点的索引
    first = n//2-1
    # 构造最大堆
    for start in range(first, -1, -1):
        max_heapify(nums, start, n-1)
    # 将最大堆转化为有序数组
    for end in range(n-1, 0, -1):
        # 将堆顶和堆尾换过来
        nums[end], nums[0] = nums[0], nums[end]
        # 重新调整成最大堆
        max_heapify(nums, 0, end-1)
    return nums
​
# 大顶堆
def max_heapify(nums, start, end):
    root = start
    while True:
        # 左子节点的索引
        child = root*2+1
        if child > end:
            break
        # 获取左右子节点的较大者
        if child+1 <= end and nums[child] < nums[child+1]:
            child += 1
        # 要交换
        if nums[root] < nums[child]:
            nums[root], nums[child] = nums[child], nums[root]
            # 将根节点换为子节点继续构造
            root = child
        else:
            break
            
# 小顶堆
def min_heapify(nums, start, end):
    root = start
    while True:
        child = root*2+1
        if child > end:
            break
        if child+1 <= end and nums[child] > nums[child+1]:
            child += 1
        if nums[root] > nums[child]:
            nums[root], nums[child] = nums[child], nums[root]
            root = child
        else:
            break

1. 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。

2. 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。

3. 走访完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。

4. 创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。

 def count_sort(nums):
        max_v, min_v = max(nums), min(nums)
        cnt = [0] * (max_v-min_v+1)
        res = [0] * len(nums)
        # 记录每个元素出现次数
        for x in nums:
            cnt[x-min_v] += 1
        # 包括当前元素在内有多少个元素在桶里
        # 模拟索引
        for i in range(1, len(cnt)):
            cnt[i] += cnt[i-1]
        for x in nums:
            # 计数-1得索引
            res[cnt[x-min_v]-1] = x
            # 存入一个数 计数-1
            cnt[x-min_v] -= 1
        return res

1. 求出待排序列表中的最大值和最小值，得到数据的范围。

2. 根据数据的范围，选择一个适合的值构建有限数量的桶，确定每个桶的数据范围。如数据范围是[0,100)，将数据分成10个桶，第一个桶为[0,10)，第二个桶为[10,20)，以此类推。

3. 将待排序列表中的数据分配到对应的桶中。

4. 对每一个桶内的数据进行排序，这里可以采用任意一种排序算法，建议采用时间复杂度小的排序算法。

5. 将所有桶中的数据依次取出，添加到一个新的有序序列中，列表排序完成。

def bucket_sort(nums):
    # 找到最大值最小值
    max_v, min_v = max(nums), min(nums)
    # 计数数组
    cnt = [0 for _ in range(min_v, max_v+1)]
    res = []
    for x in nums:
        cnt[x-min_v] += 1
    for i in range(len(nums)):
        # 添加元素
        if cnt[i]:
            res += [i+min_v] * cnt[i]
    return res

1. 求出待排序列表中的最大值，并求出最大值的位数，有多少位就需要进行多少轮分桶和合并。

2. 开辟内存空间，创建用于分配数据的桶。整数排序时，每一位的范围都在0~9之间，所以需要创建10个桶。

3. 从数据的个位开始(从最高位开始也可以，结果一样)，按个位数对数据进行分桶，不考虑其它位的数据大小。

4. 待排序列表中的所有数据都分桶完成后，将所有桶中的数据进行合并，合并时按先进先出的原则取出桶中的数据。

5. 重复步骤3,4，继续按其他位对前面处理过的数据进行分桶和合并。一直到对每一位数据都进行分桶和合并完成，最终得到一个有序序列，列表排序完成。

def radix_sort(nums):
    # 最大数字长度作为排序次数
    for k in range(len(str(max(nums)))):
        # 0-9建立10个桶
        buckets = [[] for _ in range(10)]
        # 从低位到高位获取对应数字 放入对应的桶
        for x in nums:
            buckets[x//(10**k)%10].append(x)
        # 先进先出的原则取出桶中的数据
        nums = [x for bucket in buckets for x in bucket]
    return nums