用Python实现四种简单的排序算法

2019-11-08

排序算法概述

  所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。
  在算法中，排序算法分为冒泡排序，选择排序，插入排序，快速排序，归并排序，希尔排序，基数排序，堆排序，计数排序，桶排序等。接下来，我们从最简单的冒泡排序说起。

冒泡排序

  冒泡排序(Bubble sort)重复地走访过要排序的元素列，依次比较两个相邻的元素。如果顺序错误，就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），故名“冒泡排序”。
  冒泡排序的平均时间复杂度为O(n^2^)。它是一种稳定排序算法。
Alt
  下面我们用Python来实现这个算法（注：我使用的版本为Python 3.7.4，下同）。我编写的是降序排列，代码实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 冒泡排序
nums = []

print('冒泡排序（降序排序）')
while True:
    print('请输入你想排列的数字个数：')
    try:
        x = int(input())
        for i in range(x):
            a = int(input('请输入第' + str(i + 1) + '个整数：'))
            nums.append(a)
    except ValueError:
        print('输入错误，请重新输入：')

    for j in range(len(nums) - 1):
        for k in range(len(nums) - j - 1):
            if nums[k] < nums[k + 1]:
                nums[k], nums[k + 1] = nums[k + 1], nums[k]
    print(nums)

    jud = input('您是否想要继续？(Y/N)')
    while jud != 'Y' and jud != 'N':
        jud = input('输入错误，请重新输入：')
    if jud == 'Y':
        nums.clear()
        continue
    else:
        print('再见！')
        break

选择排序

  选择排序(Selection sort)第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（或最大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。我们在这里讨论直接选择排序。
  选择排序的平均时间复杂度为O(n^2^)，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。与冒泡排序不同，选择排序是一种不稳定排序算法。
Alt  下面我们用Python来实现这个算法。升序排列代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 选择排序
nums = []

print('选择排序（升序排序）')
while True:
    print('请输入你想排列的数字个数：')
    try:
        x = int(input())
        for i in range(x):
            a = int(input('请输入第' + str(i + 1) + '个整数：'))
            nums.append(a)
    except ValueError:
        print('输入错误，请重新输入：')

    for j in range(len(nums)):
        mini = j
        for k in range(j + 1, len(nums)):
            if nums[mini] > nums[k]:
                mini = k
        nums[mini], nums[j] = nums[j], nums[mini]
    print(nums)

    jud = input('您是否想要继续？(Y/N)')
    while jud != 'Y' and jud != 'N':
        jud = input('输入错误，请重新输入：')
    if jud == 'Y':
        nums.clear()
        continue
    else:
        print('再见！')
        break

插入排序

  插入排序(Insertion sort)的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加1的有序数据。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种算法适用于少量数据的排序。我们在这里讨论直接插入排序。
  插入排序的平均时间复杂度为O(n^2^)。它也是一种稳定排序算法。
Alt  用Python实现升序插入排序如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 插入排序
nums = []

print('插入排序（升序排序）')
while True:
    print('请输入你想排列的数字个数：')
    try:
        x = int(input())
        for i in range(x):
            a = int(input('请输入第' + str(i + 1) + '个整数：'))
            nums.append(a)
    except ValueError:
        print('输入错误，请重新输入：')

    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break
    print(nums)

    jud = input('您是否想要继续？(Y/N)')
    while jud != 'Y' and jud != 'N':
        jud = input('输入错误，请重新输入：')
    if jud == 'Y':
        nums.clear()
        continue
    else:
        print('再见！')
        break

快速排序

  快速排序(Quick sort)是对冒泡排序的一种改进。它选择（或设立）一个分界值，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比分界值大，另一部分的所有数据都比分界值小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。它的核心思想是“分治+递归”。
  快速排序的平均时间复杂度为O(nlog2n)。它是一种不稳定排序算法。
Alt  我们用Python来实现升序快速排序，代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 快速排序
from typing import List

nums: List[int] = []
print('快速排序（升序排序）')


def quick_sort(data):
    if len(data) >= 2:
        mid = data[len(data) // 2]
        left = []
        right = []
        data.remove(mid)
        for num in data:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return data


while True:
    print('请输入你想排列的数字个数：')
    try:
        x = int(input())
        for i in range(x):
            a = int(input('请输入第' + str(i + 1) + '个整数：'))
            nums.append(a)
    except ValueError:
        print('输入错误，请重新输入：')

    print(quick_sort(nums))

    jud = input('您是否想要继续？(Y/N)')
    while jud != 'Y' and jud != 'N':
        jud = input('输入错误，请重新输入：')
    if jud == 'Y':
        nums.clear()
        continue
    else:
        print('再见！')
        break

写在最后

  在第一次听说排序算法的时候，“算法”这两个字于我而言像是难以企及的高度。我觉得它离我很遥远，无论是从学习进度上来说还是从难度上来说。想要去接触并了解几种简单的排序算法这一想法，萌生于昨天的Python程序设计基础课。老师先是让我们对两个数进行排序，接着是三个数、四个数……一次一次地编写程序太麻烦、太枯燥，也太低效了。我知道运用Python的列表包含的sort()方法可以直接把一堆数字进行升降序排列，那么，用排序算法的话又该如何去写呢？这对我来说，无疑是一个新的挑战。而挑战，往往是最有乐趣的。
  经过在网上查阅大量资料之后，我对这四种简单的排序算法有了新的认识，并且成功用Python实现。虽然耗时较长，但我觉得这是非常有意义的。另外，在查阅资料的过程中，我也了解到了每个基本的排序算法都会有自己的优化方法。学无止境，我在接下来的学习中还要再深入学习其他排序算法以及算法的优化。
  如果有什么好的想法，欢迎在下方评论留言，也可以通过发电子邮件的方式与我联系，共同讨论，共同进步。
  我的邮箱：1398635912@qq.com