十大排序算法思想与 Python 实现（上）-阿里云开发者社区

十大排序算法思想与 Python 实现（上）

2022-10-20 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 一般排序算法最常考的：快速排序和归并排序。这两个算法体现了分治算法的核心观点，而且还有很多出题的可能。

排序算法

一般排序算法最常考的：快速排序和归并排序。这两个算法体现了分治算法的核心观点，而且还有很多出题的可能。

1. 常见的排序算法

排序算法很多，除了能写出常见排序算法的代码，还需要了解各种排序的时空复杂度、稳定性、使用场景、区别等。

1.1 选择排序

1.1.1 思想

对于给定的一组序列，第一轮比较选择最小（或最大）的值，然后将该值与索引第一个进行交换；接着对不包括第一个确定的值进行第二次比较，选择第二个记录与索引第二个位置进行交换，重复到只剩最后一个记录位置。

案例：幼儿园排队，老师先让站成一队，带第一个小朋友依此跟其他小朋友逐个比较，选出个子最矮的，然后依此进行

1.1.2 实现

def selection_sort(gList):
    """选择排序
    :param gList: 给定的一组序列
    :return: 返回排好序的序列
    """
    length = len(gList)
    for i in range(length - 1):
        flag = i
        for j in range(i+1, length):
            if gList[flag] > gList[j]:
                flag = j
        # 如果最小值的索引与最小值相对应，则无需再次交换
        if flag != i:
            gList[flag], gList[i] = gList[i], gList[flag]
    return gList

1.1.3 选择排序分析

时间复杂度： 最好、最坏、平均的时间复杂度都为O(n2)
空间复杂度:O(1)
稳定性： 不稳定

1.2 冒泡排序

1.2.1 思想

对于给定的一组序列含 n 个元素，从第一个开始对相邻的两个记录进行比较，当前面的记录大于后面的记录，交换其位置，进行一轮比较和换位之后，最大记录在第 n 个位置；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个时为止。

案例：冒泡，像气泡一样往上升

1.2.2 实现

def bubble_sort(gList):
    """冒泡排序"""
    length = len(gList)
    for i in range(length):
        for j in range(i+1, length):
            if gList[i] > gList[j]:
                gList[i], gList[j] = gList[j], gList[i]
    return gList

1.2.3 冒泡排序分析

时间复杂度：
最好时间复杂度：O(n)
最坏时间复杂度: O(n2)
平均时间复杂度: O(n2)
空间复杂度: O(1)
稳定性： 稳定的排序

1.3 插入排序

1.3.1 思想

对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

案例：抓扑克牌

1.3.2 实现

def insertion_sort(gList):
    """插入排序"""
    length = len(gList)
    for i in range(1, length):
        temp = gList[i]  # 当前的待插入的值
        j = i - 1  # 前一个值
        while j >= 0:
            if gList[j] > temp:
                gList[j+1] = gList[j]  # 插入的动作
                gList[j] = temp  # 插入完毕
            j -= 1
    return gList

1.3.3 插入排序分析

时间复杂度
最好时间复杂度：O(n)
最坏时间复杂度: O(n2)
平均时间复杂度: O(n2)
空间复杂度:O(1)
稳定性： 稳定的排序

1.4 归并排序 ☆☆★

1.4.1 思想

利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。其中“归”代表的是递归的意思，即递归地将数组折半地分离为单个数组。

给定一组序列含 n 个元素，首先将每两个相邻的长度为 1 的子序列进行归并，得到 n/2（向上取整）个长度为 2 或 1 的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。

1.4.2 实现

def merge_sort(gList: list) -> list:
    """归并排序
    :param gList: 给定序列
    :return: 升序排列后的集合
    """
    def merge(left: list, right: list) -> list:
        """merge left and right
        :param left: left list
        :param right: right list
        :return: merge reslut
        """
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result
    if len(gList) <= 1:
        return gList
    num = len(gList) // 2
    left = merge_sort(gList[:num])
    right = merge_sort(gList[num:])
    return merge(left, right)
if __name__ == '__main__':
    gList = [3, 5, 2, 4, 1]
    print("----排序前:", gList)
    print("----归并排序后: ", merge_sort(gList))

1.4.3 归并排序分析

时间复杂度: 最好、最坏和平均情况O(nlogn)
空间复杂度:O(n)
稳定性: 稳定

题目：100 个有序数列如何合成一个大数组？

1.5 快速排序☆★★

1.5.1 思想

高效的排序算法，它采用**“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的。其原理**是：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

1.5.2 实现

# -*- coding: utf-8 -*-
def quick_sort(gList, left=0, right=None) -> list:
    """快速排序
    :param gList: 给定一组序列
    :param left:
    :param right:
    :return: 升序排序后的序列
    """
    if right is None:
        right = len(gList)-1
    if left > right:
        return gList
    key = gList[left]
    low = left
    high = right
    while left < right:
        while left < right and gList[right] >= key:
            right -= 1
        gList[left] = gList[right]
        while left < right and gList[left] <= key:
            left += 1
        gList[right] = gList[left]
    gList[right] = key
    quick_sort(gList, low, left-1)
    quick_sort(gList, left+1, high)
    return gList
if __name__ == '__main__':
    gList = [3, 5, 2, 4, 1, 6, 7]
    print("----排序前:", gList)
    print("----快速排序后: ", quick_sort(gList))

1.5.3 快速排序分析

时间复杂度：
最坏时间复杂度：O(n2)
最好时间复杂度：O(nlogn)
平均时间复杂度: O(nlogn)
空间复杂度：O(logn)
稳定性：不稳定

扩展：随机快排

1.6 希尔排序

1.6.1 思想

希尔排序也称为“缩小增量排序”。它的基本原理是：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，再对所有元素进行一次直接插入排序。

1.6.2 实现

# -*- coding: utf-8 -*-
def shell_sort(gList) -> list:
    """希尔排序"""
    length = len(gList)
    step = 2
    group = length // step
    while group > 0:
        for startPos in range(group):
            gap_insertion_sort(gList, startPos, group)
        group = group // 2
    return gList
def gap_insertion_sort(gList, start, gap):
    for i in range(start+gap, len(gList), gap):
        curr_value = gList[i]
        pos = i
        while pos >= gap and gList[pos-gap] > curr_value:
            gList[pos] = gList[pos-gap]
            pos = pos - gap
        gList[pos] = curr_value
if __name__ == '__main__':
    gList = [5, 4, 2, 1, 7, 3, 6]
    print("-----yuzhou1su-----", gList)
    print("-----希尔排序后:", shell_sort(gList))

1.6.3 希尔排序分析

时间复杂度：
最好时间复杂度：O(n)
最坏时间复杂度：O(ns)(1<s<2)
平均时间复杂度：O(nlogn)
空间复杂度:O(1)
稳定性: 不稳定