Python实现经典排序算法-超详细

目前已经有很多非常成熟的排序算法，虽然使用python时，有sort这样的方法可以实现排序。但在实际工作中，还是难免需要手写一些排序过程。跳槽在面试时，手撕一个排序算法，也是经常需要做的事情。

本文总结了以下排序算法的Python实现：（持续更新）

冒泡排序
选择排序
插入排序
快速排序

冒泡排序

冒泡排序（Bubble Sort）是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

在最好的情况下，也就是数列本身是排好序的，需要进行 n – 1 次比较；在最坏的情况下，也就是数列本身是逆序的，需要进行 n(n-1)/2 次比较。因此冒泡排序总的时间复杂度是 O(n^2)。

步骤：

从第一组两个相邻元素开始比较，依次往后交换
每经过一次排序较大的元素就会被放到后面，直到最大的元素被放到最后，那么下一次排序的时候也就不用用它（最后一个数）和它相邻的前面的数进行比较了，最后的元素就成了“稳定元素”
重复以上步骤，每一次排序完成，最后的“稳定元素”都会增加一个，直到没有可以交换的元素，那么排序就完成了

上面动图中

橙色表示被排序好的数字
绿色表示迭代过程中的数字
蓝色表示等待排序的数字

以下是冒泡排序的Python实现

# 冒泡排序
def bubbleSort(nums):
    if len(nums) <= 1:
        return nums

    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
bubbleSort(listnum)

选择排序

选择排序(Selection sort) 的基本思想是每一趟在 n – i + 1 (i = 1,2,***,n – 1)个记录中选取关键字最小(或最大)的记录作为有序序列的第 i 个记录，直到所有元素排序完成。选择排序是不稳定的排序算法。

选择排序的时间复杂度为 O(n^2)，但性能上略优于冒泡排序。

步骤：

把要排序的序列分为有序序列和无序序列
遍历序列,每一次从无序序列找到最小元素,定义为minIndex=i,放到无序序列最前面,
直到无序区间内没有元素,也就是所有元素都排好序

上面动图中：

橙色表示被排序好的数字
绿色表示迭代过程中的数字
蓝色表示等待排序的数字
红色表示一轮迭代中的minIndex，最小值的索引。

以下是选择排序的Python实现

# 选择排序
def selectionSort(nums):
    if len(nums) <= 1:
        return nums

    for i in range(0, len(nums)):
        # 最小值位置索引
        minIndex = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
selectionSort(listnum)

数据采集工作，爬取公司评级文件与法律文书，并对爬取的PDF文件进行OCR识别处理

插入排序

每次选择一个元素，并且将这个元素和整个数组中的所有元素进行比较，然后插入到合适的位置，插入排序的时间复杂度 O(n^2)

步骤：

从第一个元素开始,认为第一个元素已经被排序
取出下一个元素,在已排好序的序列中从后往前扫描
如果该元素(已排好序)大于新元素,将该元素移到下一位置
重复步骤3,直到找到已排好序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2-5

上面动图中：

橙色表示被排序好的数字
绿色表示与迭代过程中比较的数字
蓝色表示等待排序的数字
红色表示迭代过程中的数字。

以下是选择排序的Python实现

# 插入排序
def insertSort(nums):
    if len(nums) <= 1:
        return nums

    for i in range(1, len(nums)):
        pos = 0
        for j in range(i - 1, -1, -1):
            if nums[i] > nums[j]:
                pos = j + 1
                break
        temp = nums[i]
        for x in range(i, pos - 1, -1):
            nums[x] = nums[x - 1]
        nums[pos] = temp
    return nums

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
insertSort(listnum)

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分的记录都比另一部分小，然后再分别对这两个部分进行快速排序，最终实现整个序列的排序。

步骤解析：

一开始选定数组的最后一个元素5作为基准值，也就是最终排序结果应该是以5为界限划分为左右两边
从左边开始，寻找比5大的值，然后与5进行调换(因为如果比5小的值本来就应该排在5前面，比5大的值调换之后就去到了5的后面)，一路过来找到了7，将7与5调换，结束此次遍历
从右边开始，由于7已经是上一轮排好序的便不再动它，从10开始，一路向左遍历，寻找比5小的值，然后与5进行调换(因为如果比5大的值本来就应该排在5后面，比5小的值调换之后就去到了5的后前面)，一路过来找到了4，将4与5调换，结束此次遍历
从左边开始，由于3和4都是前两轮已经排好序的便不再动它，从2开始，一路向右遍历，寻找比5大的值，然后与5进行调换（道理同步骤2），一路过来找到了9，将9与5调换，结束此次遍历
从右边开始，由于排在9后面的那几个数字都是上几轮排好序的便不再动它，从1开始，一路向右遍历，寻找比5小的值，然后与5进行调换(道理同步骤3)，一下子就找到了1，将1与5调换，结束此次遍历
这个时候，发现5的左右两边都是排好序了的，所以结束此轮排序，5的左右两边抽出来各自进行下一轮的排序，规则同上，直到无法再拆分下去，即完成了整体的快速排序

上面动图中：

橙色表示被排序好，小于基准的数字
紫色表示被排序好，大于基准的数字
黄色表示基准数字
绿色表示与迭代过程中比较的数字
蓝色表示等待排序的数字
红色表示迭代过程中的数字。

以下是快速排序的Python实现，里面使用了递归调用的方法。

# 快速排序
def quicksort(nums):
    if len(nums) <= 1:
        return nums

    # 左子数组
    left = []
    # 右子数组
    right = []
    # 基准数,数组最后一位
    base = nums.pop()
    # 对原数组进行划分
    for x in nums:
        if x < base:
            left.append(x)
        else:
            right.append(x)
    # 递归调用
    return quicksort(right) + [base] + quicksort(left)

listnum = [5, 3, 8, 7, 9, 2, 18, 6, 8, 10, 55, 12, 58, 47]
quicksort(listnum)

参考资料

The End

已发布

2019年8月18日

分类

技术分享

标签：