排序算法

通过前面的学习我们已经掌握了Python的基础知识，接下来的学习可以分为两个方向，一个是利用Python丰富的第三方模块做一些综合作品，这些作品可以有趣、有用，在这个过程中也能锻炼我们的逻辑思维能力、掌握更多的计算机相关的知识、提升我们的信息素养。比如我们可以利用tkinter来模拟康威生命游戏这个经典的生物实验，也可以利用pygame来做出来飞机大战这样的趣味游戏，这些内容相信你在网站上也看到过了，之后我也会继续更新这类综合作品。另外一个方向是研究算法，可以考虑信息学奥林匹克竞赛，不过信奥赛的官方编程语言是C/C++，目前还不支持Python，但原理是相同的，有了Python的基础再去学习C++会更容易上手。接下来我会用我们学到的Python知识来讲解几个排序算法，让你对这块内容有个初步的认识，从而根据自身的情况选择下一步的学习方向。排序算法，顾名思义就是将原本乱序的数据，通过算法变为有序的数据，或是从小到大排列，或是从大到小排列。排序算法的核心是排序的逻辑，不同的逻辑思路就会有不同的排序算法了，我们接下来会讲解多种排序算法，这也再次告诉我们解决同一个问题可以有很多种不同的方法。

冒泡排序

其实之前我们已经学习过一个排序算法了，你还有印象吗？是的，冒泡排序！我们简单回顾一下，还是打开我们之前用到的这个算法可视化的网站，算法可视化网站在新窗口打开。第一个就是冒泡排序，它的逻辑是：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。代码为：

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

选择排序

选择排序的逻辑也比较好理解，具体为：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。代码为：

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序

插入排序跟打扑克牌有点像，每次来了新牌之后都从头对比一遍看看新牌适合插入到哪个位置，总结下它的逻辑为：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）代码为：

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

归并排序

归并排序（merge sort）是一种基于分治策略的排序算法，包含“划分”和“合并”阶段两部分逻辑。具体逻辑为：

划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为1时终止划分，开始合并，持续地讲左右两个较短的有序数组合并为一个较长的有序数组，直至结束。代码为

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
 
def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

参考资料：

https://blog.csdn.net/HinsCoder/article/details/141073587
https://www.cnblogs.com/chengxiao/p/6194356.html
https://www.cnblogs.com/1873cy/p/18435125

快速排序

快速排序（quick sort）也是一种基于分治策略的排序算法，运行高效，应用广泛。快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体逻辑为：

对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
对左子数组和右子数组分别递归执行“哨兵划分”。
持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。代码为：

def partition(self, nums: list[int], left: int, right: int) -> int:
    """哨兵划分"""
    # 以 nums[left] 为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1  # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i  # 返回基准数的索引

def quick_sort(self, nums: list[int], left: int, right: int):
    """快速排序"""
    # 子数组长度为 1 时终止递归
    if left >= right:
        return
    # 哨兵划分
    pivot = self.partition(nums, left, right)
    # 递归左子数组、右子数组
    self.quick_sort(nums, left, pivot - 1)
    self.quick_sort(nums, pivot + 1, right)

参考资料：

https://www.hello-algo.com/chapter_sorting/quick_sort/
https://www.zhihu.com/question/483978234/answer/3251244691

# 排序算法

# 冒泡排序

# 选择排序

# 插入排序