阅读《算法第一步(Python版)》-排序算法

zx钟

发布于 2021-03-24 17:08:13

4220

发布于 2021-03-24 17:08:13

文章被收录于专栏：测试游记测试游记

排序算法

按照某种特定的方式进行排序

比较排序

通过比较操作来确定两个元素哪个应该放在序列中相对靠前的位置。

数据之间根据特定的原则进行比较，任意两个数据相比只能是大于、等于、小于这3种结果的其中一种，然后根据比较结果确定两者的相对位置。

传递性：a<=b且b<=c，则a<=c
完全性：对于任意两个元素a，b。要么a<=b，要么a>=b

拥有上述两个性质的集合叫作全序数据集合，简称全序集

局限

每次对其中的元素进行比较操作所获得的信息都是有限的。

在最差的情况下，任何一种比较排序的时间复杂度都至少是O(nlong(n))

优势

可以控制比较原则，可以对任何类型的数据进行排序
可以更好的控制如何排序
对数据进行比较可以与现实中的许多问题契合

几种简单排序算法

选择排序

选择排序是一种迭代算法，每次迭代从待排序的数据元素中选择最小的那个元素，排到当前待排序列的最前面「升序」，如此循环，直到所有的元素排完。

# -*- coding: utf-8 -*-
# @Time    : 2021/3/13 8:17 下午
# @Author  : zhongxin
# @Email   : 490336534@qq.com
# @File    : 选择排序.py

def selection_sort(arr):
    for s in range(0, len(arr)):
        m = s
        for i in range(s + 1, len(arr)):
            if arr[i] < arr[m]:
                m = i
        arr[s], arr[m] = arr[m], arr[s]


if __name__ == '__main__':
    arr = [3, 2, 1, 5, 8, 7, 9, 10, 13]
    selection_sort(arr)
    print(arr)

冒泡排序

因为在用此算法排序升序的时，每次迭代过程中最小的元素会经过一次次地交换慢慢「浮」到数列的顶端，就好像一个个气泡冒出来那样

每次迭代都将所有待排序元素从头到尾走访一遍

每次走访过程中，两两比较相邻的元素，如果这两者的相对顺序错误，就交换。

迭代过程

第一轮迭代：从尾一直访问至头，使最小的元素移到第一位

第二轮迭代：从尾一直尾到第二个元素「第一个元素已经是最小的值了」，让最小的元素移到第二位

…

第n-1次迭代：访问范围缩减到最后两个元素，迭代终止

实现代码

# -*- coding: utf-8 -*-
# @Time    : 2021/3/13 8:25 下午
# @Author  : zhongxin
# @Email   : 490336534@qq.com
# @File    : 冒泡排序.py

def bubble_sort(arr):
    for i in range(0, len(arr) - 1):
        for j in range(len(arr) - 1, i, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]


if __name__ == '__main__':
    arr = [3, 2, 1, 5, 8, 7, 6, 10, 4]
    bubble_sort(arr)
    print(arr)

增加打印

def bubble_sort(arr):
    for i in range(0, len(arr) - 1):
        for j in range(len(arr) - 1, i, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                print(f'第{i}次迭代-{j}:{arr}')

第0次迭代-8:[3, 2, 1, 5, 8, 7, 6, 4, 10]
第0次迭代-7:[3, 2, 1, 5, 8, 7, 4, 6, 10]
第0次迭代-6:[3, 2, 1, 5, 8, 4, 7, 6, 10]
第0次迭代-5:[3, 2, 1, 5, 4, 8, 7, 6, 10]
第0次迭代-4:[3, 2, 1, 4, 5, 8, 7, 6, 10]
第0次迭代-2:[3, 1, 2, 4, 5, 8, 7, 6, 10]
第0次迭代-1:[1, 3, 2, 4, 5, 8, 7, 6, 10]
第1次迭代-7:[1, 3, 2, 4, 5, 8, 6, 7, 10]
第1次迭代-6:[1, 3, 2, 4, 5, 6, 8, 7, 10]
第1次迭代-2:[1, 2, 3, 4, 5, 6, 8, 7, 10]
第2次迭代-7:[1, 2, 3, 4, 5, 6, 7, 8, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 10]

从上可以看出，两次迭代就完成了排序

如果没有发生元素交换，则表示已经完成了排序，终止循环

def bubble_sort(arr):
    for i in range(0, len(arr) - 1):
        flag = False
        for j in range(len(arr) - 1, i, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
                flag = True
        if not flag:
            break

插入排序

# -*- coding: utf-8 -*-
# @Time    : 2021/3/13 8:54 下午
# @Author  : zhongxin
# @Email   : 490336534@qq.com
# @File    : 插入排序.py

def insertion_sort(arr):
    if len(arr) == 1:
        return
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break


if __name__ == '__main__':
    arr = [2, 1, 5, 8, 7, 13]
    insertion_sort(arr)
    print(arr)

插入排序

时间复杂度

最差时间复杂度：待排序的是一个倒序数组

时间复杂度为O(n^2)

最佳时间复杂度：待排序的是一个正序数组

选择排序：O(n^2)

冒泡排序、插入排序：O(n)

平均时间复杂度：三者都为O(n^2)

快速排序

首先实现分区，取第一个元素，将比它小的放在左侧，比他大的放在右侧

# -*- coding: utf-8 -*-
# @Time    : 2021/3/13 9:33 下午
# @Author  : zhongxin
# @Email   : 490336534@qq.com
# @File    : 快速排序-分区.py

def partition(arr, low, high):
    """

    :param arr:待排序数组
    :param low:待排序起始下标
    :param high:待排序终止下标
    :return:
    """
    if low >= high:
        return -1
    pi = low
    li = low + 1
    ri = high
    while ri >= li:
        if arr[li] > arr[pi]:
            arr[ri], arr[li] = arr[li], arr[ri]
            ri -= 1
        else:
            li += 1
    pi = li - 1
    arr[low], arr[pi] = arr[pi], arr[low]
    return pi


if __name__ == '__main__':
    arr = [5, 8, 3, 2, 11, 19, 2, 0, 27]
    p = partition(arr, 0, len(arr) - 1)
    print(p)
    print(arr) # [2, 0, 3, 2, 5, 19, 11, 27, 8]

采用分而治之的方式，将左右分区继续进行左右分区，直至完成排序

def partition(arr, low, high):
    """

    :param arr:待排序数组
    :param low:待排序起始下标
    :param high:待排序终止下标
    :return:
    """
    if low >= high:
        return -1
    pi = low
    li = low + 1
    ri = high
    while ri >= li:
        if arr[li] > arr[pi]:
            arr[ri], arr[li] = arr[li], arr[ri]
            ri -= 1
        else:
            li += 1
    pi = li - 1
    arr[low], arr[pi] = arr[pi], arr[low]
    return pi


def q_sort_iteration(arr, low, high):
    if low >= high:
        return -1
    regions = [[low, high]]
    i = 0
    while i < len(regions):
        low = regions[i][0]
        high = regions[i][1]
        p = partition(arr, low, high)
        if p != -1:
            regions.append([low, p - 1])
            regions.append([p + 1, high])
        i += 1


if __name__ == '__main__':
    arr = [5, 8, 3, 2, 11, 19, 2, 0, 27]
    p = q_sort_iteration(arr, 0, len(arr) - 1)
    print(p)
    print(arr)

调试

递归快速排序

# -*- coding: utf-8 -*-
# @Time    : 2021/3/13 10:07 下午
# @Author  : zhongxin
# @Email   : 490336534@qq.com
# @File    : 递归快速排序.py
def partition(arr, low, high):
    """

    :param arr:待排序数组
    :param low:待排序起始下标
    :param high:待排序终止下标
    :return:
    """
    if low >= high:
        return -1
    pi = low
    li = low + 1
    ri = high
    while ri >= li:
        if arr[li] > arr[pi]:
            arr[ri], arr[li] = arr[li], arr[ri]
            ri -= 1
        else:
            li += 1
    pi = li - 1
    arr[low], arr[pi] = arr[pi], arr[low]
    return pi


def q_sort_iteration(arr, low, high):
    if low >= high:
        return -1
    p = partition(arr, low, high)
    q_sort_iteration(arr, low, p - 1)
    q_sort_iteration(arr, p + 1, high)


if __name__ == '__main__':
    arr = [5, 8, 3, 2, 11, 19, 2, 0, 27]
    q_sort_iteration(arr, 0, len(arr) - 1)
    print(arr)

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-03-14，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自测试游记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度