算法

发表于 |

算法是每一个程序员都必须要认真学习的一门课程，虽然在工作中很少能够用到，但是它能够让我们理解程序的世界。由于前段时间学习了Python，Python语法简洁，便于理解。如果看不明白，可以借助这个网站来帮助理解。

冒泡排序

冒泡排序很简单，重复的遍历数列，依次比较两个元素，满足条件时，将两个元素进行互换。

思路：

  1. 比较相邻的两个元素，如果第一个元素比第二个元素大，就交换两个元素（里层条件判断）。
  2. 对第0个元素到第n-i个元素做同样的工作，这时候最大的数就会在数组中最后的位置（外层循环）。
  3. 对所有的元素重复上面两个步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array


if __name__ == '__main__':
    s = bubble_sort([3, 2, 4, 5, 1])
    print (s)

快速排序

快排通常比其他的算法快，因此常常被采用。快排算法体现了分治法的思想。

思路：

  1. 从数列当中取出一个元素作为基准数。
  2. 将比基准数大的放到右边，小于或等于它的数都放在左边
  3. 再对左右区间递归执行步骤2，直到各区间只有一个数
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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def quick_sort(ary):
    return qsort(ary, 0, len(ary) - 1)


def qsort(ary, left, right):
    # ary为待排序数组，left为待排序的左边界，right为右边界
    if left >= right: return ary
    key = ary[left]  # 基准数
    left_ptr, right_ptr = left, right
    while left_ptr < right_ptr:
        while ary[right_ptr] >= key and left_ptr < right_ptr:
            right_ptr -= 1
        while ary[left_ptr] <= key and left_ptr < right_ptr:
            left_ptr += 1
        # 交换两个指针对应的值
        ary[left_ptr], ary[right_ptr] = ary[right_ptr], ary[left_ptr]
    ary[left], ary[left_ptr] = ary[left_ptr], ary[left]
    qsort(ary, left, left_ptr - 1)
    qsort(ary, right_ptr + 1, right)
    return ary


if __name__ == '__main__':
    s = quick_sort([3, 2, 4, 5, 1])
    print (s)

插入排序

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

思路：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def insert_sort(array):
    n = len(array)
    for i in range(1, n):
        if array[i] < array[i - 1]:
            temp = array[i]  # 取出待插入的元素
            index = i  # 取出待插入元素的下标
            # 从后往前扫描，从 i-1 循环到 0 (包括0)
            for j in range(i - 1, -1, -1):
                if array[j] > temp:
                    array[j + 1] = array[j]  # 将该扫描的元素向后移动一位
                    index = j  # 记录待插入的下标
                else:
                    break
            array[index] = temp
            print(array)
    return array


if __name__ == '__main__':
    s = insert_sort([3, 2, 4, 5, 1])
    print (s)

选择排序

对于一个列表l = {k1, k2, … kn}，将其从小到大排序。

思路：

  1. 先从列表l，并选择最小的值minNum，将minNum与k1对换。
  2. 然后遍历剩下的元素（即k2, … kn）选取最小值minNum，与k2交换
  3. 以此类推，知道所有元素均排序完毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def select_sort(ary):
    n = len(ary)
    for i in range(n):
        # 记录最小元素下标
        minNum = i
        for j in range(i + 1, n):
            if ary[j] < ary[minNum]:
                # 最小的下标
                minNum = j
        ary[minNum], ary[i] = ary[i], ary[minNum]
    return ary


if __name__ == '__main__':
    s = select_sort([3, 1, 2, 4, 6])
    print(s)

归并排序

归并排布是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，然后再合并数组。

例如：有数列[5, 10, 2, 4, 6]，第一次递归后，

思路：

先考虑合并两个有序数组：思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解：思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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):
    print ('left = ', left)
    print ('right = ', right)
    '''
    将两个有序数组left[]和right[]合并成一个大的有序数组
    '''
    # left和right数组的下标指针
    l,r = 0,0
    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:]

    return result

if __name__ == '__main__':
    s = merge_sort([5, 4, 3, 2, 1])
    print ('sort result = ', s)

希尔排序

希尔排序的基本思想是：将数组中的数据列在一个按照一定的增量列在一个表当中，然后分别进行插入排序。一直重复这个过程，每次都改变这个增量的长度。最后这个表只有一列。

思路：有以下的数组[3, 2, 4, 5, 1, 6, 8, 7]，将增量列为数组长度的一半，那么得到的表为：

1
2
3  2  4  5
1  6  8  7

然后对每列进行排序，如下表：

1
2
1  2  4  5
3  6  8  7

再次将增量依次折半，并按照下表进行排序，如下表：

1
2
3
4
1  2
3  5
4  6
8  7

当增量为1的时候，就是插入排序了，重复多次后，当增量为小于0的时候，排序完成，就得到排序后的数组列表。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def shell_sort(ary):
    n = len(ary)
    # 初始增量，round四舍五入取整
    gap = int(round(n / 2))
    while gap > 0:
        for i in range(gap, n):
            temp = ary[i]
            j = i
            while (j >= gap and ary[j - gap] > temp):
                # 插入排序
                ary[j] = ary[j - gap]
                j = j - gap
            ary[j] = temp
        gap = int(round(gap / 2))
    return ary


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

堆排序

堆排序是采用二叉堆来的数据结构实现的，实质上还是一维数组。二叉堆是一个近似完全二叉树。

二叉堆有以下性质：

  1. 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值
  2. 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）

思路：

  1. 构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
  2. 堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
  3. 最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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


if __name__ == '__main__':
    s = heap_sort([3, 2, 4, 5, 1])
    print (s)

时间复杂度与空间复杂度

算法的时间复杂度和空间复杂度可参考这里

排序算法的时间复杂度和空间复杂度对比表：

参考

堆与堆排序