【编程之路】常见的排序算法（一）

几种常见的排序算法

本文将介绍五种基础的排序算法，分别是：冒泡、选择、插入、快速、归并。

1.冒泡排序

冒泡排序应该是入门级的排序算法了。

class solution:
    def sort_arr(self, arr):
        n = len(arr)
        for i in range(n):
            # 每次将最大值放到最右边
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
            print(arr)
        return arr

if __name__ == '__main__':
    a = solution()
    b = a.sort_arr([8, 7, 6, 5, 4, 3, 2, 1])
    print('输出排序后的结果', b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

可以看一下每一轮的结果。

做一点小优化，增加一个标记位。

class solution:
    def sort_arr(self, arr):
        n = len(arr)
        for i in range(n):
            sign = False
            # 每次将最大值放到最右边
            for j in range(0, n-i-1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    sign = True
            # 一轮下来无任何变化
            if not sign:
                break
            print(arr)
        return arr

if __name__ == '__main__':
    a = solution()
    b = a.sort_arr([8, 7, 6, 5, 4, 3, 2, 1])
    print('输出排序后的结果', b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.选择排序

第一次从待排序的数据元素中选出最大（或最小）的一个元素，存放在序列的起始位置；然后再从剩余的未排序元素中寻找到最大（或最小）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

选择排序是不稳定的排序方法。

class solution:
    def sort_arr(self, arr):
        n = len(arr)
        for i in range(n-1):
            index = i
            # 从后面挑出最大的元素
            for j in range(i+1, n):
                if arr[index] < arr[j]:
                    index = j
            arr[i], arr[index] = arr[index], arr[i]
            print(arr)
        return arr

if __name__ == '__main__':
    a = solution()
    b = a.sort_arr([3, 2, 5, 6, 1, 4])
    print('输出排序后的结果', b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.插入排序

插入排序的原理是默认前面的元素都是已经排序好的，然后从后面逐个读取插入到前面排序好的合适的位置，就相当于打扑克的时候每获取一张牌的时候就插入到合适的位置 一样。

插入排序可以分为两种，一种是直接插入，还一种是二分法插入。直接插入的原理比较简单，就是往前逐个查找直到找到合适的位置然后插入；二分法插入是先折半查找，找到合适的位置然后再插入。

class solution:
    def InsertSort(self, arr):
        n = len(arr)
        for i in range(n):
            res = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > res:
                arr[j+1] = arr[j]
                j = j - 1
            arr[j+1] = res
            print(arr)
        return arr

if __name__ == '__main__':
    a = solution()
    b = a.InsertSort([12, 11, 13, 5, 6])
    print('排好序后的结果', b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.快速排序

快速排序原理是首先要找到一个中枢，把小于中枢的值放到它前面，大于中枢的值放到它的右边，然后再以此方法对这两部分数据分别进行快速排序。

class solution:
    def quick_sort(self, arr, left, right):
        if left >= right:
            return
        low = left
        high = right
        # 中枢值
        key = arr[low]
        while left < right:
            while left < right and arr[right] >= key:
                right = right - 1
            arr[left] = arr[right]
            while left < right and arr[left] <= key:
                left = left + 1
            arr[right] = arr[left]
        arr[left] = key
        self.quick_sort(arr, low, left-1)
        self.quick_sort(arr, left+1, high)

if __name__ == '__main__':
    arr = [8, 4, 7, 3, 12, 9, 11, 13, 5, 6, 5]
    a = solution()
    a.quick_sort(arr, 0, len(arr)-1)
    print('排好序后的结果', arr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

下面是一种伪快排的写法。（不推荐，效率低下）

class solution:
    def quick_sort(self, arr):
        a = []
        b = []
        if len(arr) < 2:
            return arr
        else:
            res = arr[0]
            for num in arr[1:]:
                if num > res:
                    b.append(num)
                else:
                    a.append(num)
        return self.quick_sort(a) + [res] + self.quick_sort(b)

if __name__ == '__main__':
    arr = [8, 4, 7, 3, 12, 9, 11, 13, 5, 6, 5]
    b = solution().quick_sort(arr)
    print(b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.归并排序

归并排序其实本质上是分治法的一种典型应用。

• 分割：递归地把当前序列平均分割成两半。
• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

def merge_sort(arr):
    n = len(arr)
    if n < 2:
        return arr
    mid = n // 2
    left = arr[:mid]
    right = arr[mid:]
    left_sort = merge_sort(left)
    right_sort = merge_sort(right)
    return merge(left_sort, right_sort)

def merge(left, right):
    res = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    if left:
        res.extend(left)
    if right:
        res.extend(right)
    return res

if __name__ == '__main__':
    arr = [8, 4, 7, 3, 12, 9, 11, 13, 5, 6, 5]
    arr = merge_sort(arr)
    print(arr)
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

---

参考资料

【1】python 冒泡排序算法(超级详细)
【2】python 排序之快速排序
【3】快速排序的四种 python 实现
【4】快速排序的 Python 实现
【5】python 实现归并排序(MergeSort)