曹耘豪的博客

算法之排序

  1. 冒泡排序（Bubble Sort）
  2. 选择排序（Selection Sort）
  3. 插入排序（Insertion Sort）
  4. 希尔排序（Shell Sort）
  5. 堆排序（Heap Sort）
  6. 归并排序（Merge Sort）
  7. 快速排序（Quick Sort）
  8. 计数排序（Counting Sort）
  9. 基数排序（Radix Sort）

可视化排序 https://visualgo.net/en/sorting

冒泡排序（Bubble Sort）

依次两两比较，发现顺序不对则交换，重复这一过程

由于是从前向后遍历，所以第一次遍历会将最大的交换至最后一个位置，依次类推

我们记录每次遍历时最后一次交换的位置，避免后续多余的判断

1
2
3
4
5
6
7
8
9
def bubble_sort(arr):
    last_sort, swap_count = len(arr), 0
    while last_sort > 1:
        last_sort, end = 1, last_sort
        for i in range(1, end):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                last_sort = i
                swap_count += 1

选择排序（Selection Sort）

每次选择最小值放到前面

1
2
3
4
5
6
7
8
9
10
def selection_sort(arr):
    swap_count = 0
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            swap_count += 1
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

插入排序（Insertion Sort）

依次选择元素，插入到前面已排序的位置

1
2
3
4
5
6
7
8
9
def insertion_sort(arr):
    swap_count = 0
    for i in range(1, len(arr)):
        j = i
        while j >= 1 and arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
            swap_count += 1
            j -= 1
    return swap_count

希尔排序（Shell Sort）

插入排序的优化，也称“递减增量排序算法”，先分组，分组内使用普通插入排序，逐渐增加每个分组内的元素数，最终一个分组内包含全部元素（step=1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def shell_sort(arr):
    swap_count = 0
    step = len(arr) // 2
    while step:
        for i in range(step, len(arr)):
            # 以下是普通插入排序
            j = i # j=step时，j是第一个分组的第二个元素
            while j - step >= 0 and arr[j - step] > arr[j]:
                arr[j - step], arr[j] = arr[j], arr[j - step]
                swap_count += 1
                j -= step
        step //= 2

    return swap_count

堆排序（Heap Sort）

先将输入数组转化为最大堆，然后每次将堆顶元素和堆的最后一个未排序的元素交换，然后将前面的元素继续堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def heapify_max(arr, n, i):
    left, right, target = i * 2 + 1, i * 2 + 2, i
    if left < n and arr[left] > arr[target]:
        target = left
    if right < n and arr[right] > arr[target]:
        target = right
    if target != i:
        arr[target], arr[i] = arr[i], arr[target]
        heapify_max(arr, n, target)


def heap_sort(arr):
    # 构建最大堆
    last_parent = (len(arr) - 2 ) // 2
    for parent in range(last_parent, -1, -1):
        heapify_max(arr, parent, len(arr))
    # 交换后，将前面的元素再次堆化
    for i in range(len(arr) - 1, -1, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_max(arr, i, 0)

归并排序（Merge Sort）

先2个一组，组内排序，然后4个一组，组内排序（相当于合并两个有序列表），然后8个一组，组内排序，依次类推

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
def merge_sort(arr):
    def merge(ll, rr):
        l, r, r_end = ll, rr, min(rr + (rr - ll), len(arr))
        merged = []
        while l < rr and r < r_end:
            if arr[l] < arr[r]:
                merged.append(arr[l])
                l += 1
            else:
                merged.append(arr[r])
                r += 1
        for i in range(l, rr):
            merged.append(arr[i])
        for i in range(r, r_end):
            merged.append(arr[i])
        for i in range(len(merged)):
            arr[ll + i] = merged[i]

    i = 1
    while True:
        for j in range(0, len(arr), i << 1):
            merge(j, j + i)
        i <<= 1
        if i >= len(arr):
            break

快速排序（Quick Sort）

每次取第一个未排序的值，将小于它的放到左边，大于它的放到右边，把该值放到中间，该值便确定。重复该过程直到全部排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(arr):
    sorted_indices = [False] * len(arr)
    first_unsorted_idx = 0

    while first_unsorted_idx < len(arr):
        pivot_idx = first_unsorted_idx

        low_store_idx = pivot_idx + 1
        for i in range(pivot_idx + 1, len(arr)):
            if sorted_indices[i]:
                # 如果排序过则停止
                break
            if arr[pivot_idx] > arr[i]:
                arr[i], arr[low_store_idx] = arr[low_store_idx], arr[i]
                low_store_idx += 1

        arr[pivot_idx], arr[low_store_idx - 1] = arr[low_store_idx - 1], arr[pivot_idx]
        sorted_indices[low_store_idx - 1] = True

        # 计算第一个未排序的位置
        while first_unsorted_idx < len(arr) and sorted_indices[first_unsorted_idx]:
            first_unsorted_idx += 1

计数排序（Counting Sort）

对一个小范围的整数排序

1
2
3
4
5
6
7
8
9
10
11
12
def counting_sort(arr):
    base = min(arr)
    sort_arr = [0] * (max(arr) - base + 1)

    for i in range(len(arr)):
        sort_arr[arr[i] - base] += 1

    idx = 0
    for i in range(len(sort_arr)):
        for _ in range(sort_arr[i]):
            arr[idx] = base + i
            idx += 1

基数排序（Radix Sort）

对每一位分别排序

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
def radix_sort(arr):

    # 获取最大位数
    max_ = max(arr)
    digit_count = 0
    while max_:
        max_ //= 10
        digit_count += 1

    def get(num, digit):
        '''
        获取一个整数的倒数第digit位数
        @param digit: 0代表倒数第一位，1代表倒数第二位
        '''
        while digit:
            num //= 10
            digit -= 1
        return num % 10

    for i in range(digit_count):
        # 初始化10个桶
        buckets = [[] for _ in range(10)]
        for n in arr:
            digit = get(n, i)
            buckets[digit].append(n)

        idx = 0
        for bucket in buckets:
            for n in bucket:
                arr[idx] = n
                idx += 1

  算法