排序算法总结

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

冒泡排序 BubbleSort

基本思想

基本思想：每次比较两个相邻的元素，如果它们的顺序不对，就交换。

实现

从小到大排序：3, 1, 5, 7, 2, 4, 9, 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# coding:utf-8
def bubbleSort(numbers):
    n = len(numbers)
    for j in range(n):
        for i in range(1, n - j):
            if numbers[i - 1] > numbers[i]:
                numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
        print j,numbers
    return numbers

if __name__ == '__main__':
    a = [1, 2, 4, 3, 5]
    bubbleSort(a)

'''
运行结果：
0 [1, 3, 5, 2, 4, 7, 6, 9]
1 [1, 3, 2, 4, 5, 6, 7, 9]
2 [1, 2, 3, 4, 5, 6, 7, 9]
3 [1, 2, 3, 4, 5, 6, 7, 9]
4 [1, 2, 3, 4, 5, 6, 7, 9]
5 [1, 2, 3, 4, 5, 6, 7, 9]
6 [1, 2, 3, 4, 5, 6, 7, 9]
7 [1, 2, 3, 4, 5, 6, 7, 9]'''

优化

注意到经过一次排序，数组就已经是有序的了。可以针对上述代码进行优化：

优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bubbleSort_2(numbers):
    n = len(numbers)
    for j in range(n):
        flag = 1
        for i in range(1, n - j):
            if numbers[i - 1] > numbers[i]:
                numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
                flag = 0
        print j, numbers
        if flag:
            break
    return numbers
'''
运行结果：
0 [1, 3, 5, 2, 4, 7, 6, 9]
1 [1, 3, 2, 4, 5, 6, 7, 9]
2 [1, 2, 3, 4, 5, 6, 7, 9]
3 [1, 2, 3, 4, 5, 6, 7, 9]
'''

优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def bubbleSort_3(numbers):
    n = len(numbers)
    k = n
    for j in range(n):
        flag = 1
        for i in range(1, k):
            if numbers[i - 1] > numbers[i]:
                numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
                k = i
                flag = 0
        print j, numbers
        if flag:
            break
    return numbers
'''
运行结果：
0 [1, 3, 5, 2, 4, 7, 6, 9]
1 [1, 3, 2, 4, 5, 6, 7, 9]
2 [1, 2, 3, 4, 5, 6, 7, 9]
3 [1, 2, 3, 4, 5, 6, 7, 9]
'''

选择排序 SelectionSort

基本思想

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 以此类推，直到所有元素均排序完毕。

实现

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def selectSort(numbers):
    n = len(numbers)
    for j in range(n):
        min_index = j
        for i in range(j, n):
            if numbers[i] < numbers[min_index]:
                min_index = i
        numbers[j], numbers[min_index] = numbers[min_index], numbers[j]
        print j, numbers
    return numbers
'''
运行结果：
0 [1, 3, 5, 7, 2, 4, 9, 6]
1 [1, 2, 5, 7, 3, 4, 9, 6]
2 [1, 2, 3, 7, 5, 4, 9, 6]
3 [1, 2, 3, 4, 5, 7, 9, 6]
4 [1, 2, 3, 4, 5, 7, 9, 6]
5 [1, 2, 3, 4, 5, 6, 9, 7]
6 [1, 2, 3, 4, 5, 6, 7, 9]
7 [1, 2, 3, 4, 5, 6, 7, 9]
'''

插入排序 InsertionSort

基本思想

基本思想：对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

  1. 认为第0个元素有序
  2. 从第1个元素开始，取出当前元素now，和有序的数组从后往前对比
  3. 如果now大于等于有序数组最后一个元素，则continue；否则，将有序数组元素逐个后移，找到元素now应该插入的位置，插入now

实现

从小到大排序：3, 1, 5, 7, 2, 4, 9, 6

代码：

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
def insertionSort(numbers):
    n = len(numbers)
    print(0, numbers)
    for j in range(1, n):  # 从1开始
        if numbers[j - 1] > numbers[j]:  # 只处理这种情况。如果这2个元素本身有序，则continue
            now_element = numbers[j]
            index = j
            for i in range(j - 1, -1, -1):  # 从后往前遍历[j-1, 0]
                if numbers[i] > now_element:
                    numbers[i + 1] = numbers[i]  # 后移一位
                    index = i
                else:
                    break
            numbers[index] = now_element
        print(j, numbers)
    return numbers
  
'''
运行结果：
0 [3, 1, 5, 7, 2, 4, 9, 6]
1 [1, 3, 5, 7, 2, 4, 9, 6]
2 [1, 3, 5, 7, 2, 4, 9, 6]
3 [1, 3, 5, 7, 2, 4, 9, 6]
4 [1, 2, 3, 5, 7, 4, 9, 6]
5 [1, 2, 3, 4, 5, 7, 9, 6]
6 [1, 2, 3, 4, 5, 7, 9, 6]
7 [1, 2, 3, 4, 5, 6, 7, 9]
'''

快速排序 QuickSort

基本思想

采用分治思想

实现

从小到大排序：3, 1, 5, 7, 2, 4, 9, 6

代码：

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
def quickSort(numbers, start, end):
    print(numbers)
    if start >= end:
        return numbers
    key = numbers[start]  # 取最左边元素为基数
    l = start
    r = end
    while l < r:
        while numbers[r] >= key and l < r:  # 必须先while r，再l
            r -= 1
        while numbers[l] <= key and l < r:  # 找到第一个比key大的元素索引
            l += 1
        numbers[l], numbers[r] = numbers[r], numbers[l]
    numbers[start], numbers[l] = numbers[l], numbers[start]
    quickSort(numbers, start, l - 1)
    quickSort(numbers, r + 1, end)
    return numbers

'''
运行结果：
[3, 1, 5, 7, 2, 4, 9, 6]
[2, 1, 3, 7, 5, 4, 9, 6]
[1, 2, 3, 7, 5, 4, 9, 6]
[1, 2, 3, 7, 5, 4, 9, 6]
[1, 2, 3, 7, 5, 4, 9, 6]
[1, 2, 3, 6, 5, 4, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
'''

归并排序 MergeSort

基本思想

采用分治思想

实现

从小到大排序：3, 1, 5, 7, 2, 4, 9, 6

代码：

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
def merge_sort(ary):
    if len(ary) <= 1 : return ary
    num = int(len(ary)/2)       #二分分解
    left = merge_sort(ary[:num])
    right = merge_sort(ary[num:])
    return merge(left,right)    #合并数组

def merge(left,right):
    '''
    合并操作，
    将两个有序数组left[]和right[]合并成一个大的有序数组
    '''
    l,r = 0,0           #left与right数组的下标指针
    result = []
    while l<len(left) and r<len(right) :
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    print(left,right,"==>",result)
    return result

'''
运行结果：
[3] [1] ==> [1, 3]
[5] [7] ==> [5, 7]
[1, 3] [5, 7] ==> [1, 3, 5, 7]
[2] [4] ==> [2, 4]
[9] [6] ==> [6, 9]
[2, 4] [6, 9] ==> [2, 4, 6, 9]
[1, 3, 5, 7] [2, 4, 6, 9] ==> [1, 2, 3, 4, 5, 6, 7, 9]
[1, 2, 3, 4, 5, 6, 7, 9]
'''

堆排序 HeapSort

基本思想

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。

实现

从小到大排序：3, 1, 5, 7, 2, 4, 9, 6

代码：

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
def heap_sort(ary):
    n = len(ary)
    first = int(n / 2 - 1)  # 最后一个非叶子节点
    for start in range(first, -1, -1):  # 构造大根堆
        max_heapify(ary, start, n - 1)
    for end in range(n - 1, 0, -1):  # 堆排，将大根堆转换成有序数组
        ary[end], ary[0] = ary[0], ary[end]
        max_heapify(ary, 0, end - 1)
    return ary


# 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
# start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary, start, end):
    root = start
    while True:
        child = root * 2 + 1  # 调整节点的子节点
        if child > end: break
        if child + 1 <= end and ary[child] < ary[child + 1]:
            child = child + 1  # 取较大的子节点
        if ary[root] < ary[child]:  # 较大的子节点成为父节点
            ary[root], ary[child] = ary[child], ary[root]  # 交换
            root = child
        else:
            break
    print(ary, "start: ", start, "end", end)

'''
运行结果：
[3, 1, 5, 7, 2, 4, 9, 6] start:  3 end 7
[3, 1, 9, 7, 2, 4, 5, 6] start:  2 end 7
[3, 7, 9, 6, 2, 4, 5, 1] start:  1 end 7
[9, 7, 5, 6, 2, 4, 3, 1] start:  0 end 7
[7, 6, 5, 1, 2, 4, 3, 9] start:  0 end 6
[6, 3, 5, 1, 2, 4, 7, 9] start:  0 end 5
[5, 3, 4, 1, 2, 6, 7, 9] start:  0 end 4
[4, 3, 2, 1, 5, 6, 7, 9] start:  0 end 3
[3, 1, 2, 4, 5, 6, 7, 9] start:  0 end 2
[2, 1, 3, 4, 5, 6, 7, 9] start:  0 end 1
[1, 2, 3, 4, 5, 6, 7, 9] start:  0 end 0
[1, 2, 3, 4, 5, 6, 7, 9]
'''

参考