排序

排序算法是一种将一组元素按照特定规则进行排列的算法。tips：

  • 稳定指如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 二维数组.sort(key=lambda x: x[0]) 根据指定二维数组的第一个元素升序排序
  • 二维数组.sort(key=lambda x: (x[0], -x[1]))根据指定二维数组的第一个元素升序排序，若第一个元素相等，按第二个元素降序排序
  • sort()排序的时间复杂度为O(NlogN)，使用的是归并排序。
  • 自定义排序函数array.sort(key=functools.cmp_to_key=sort_function)

稳定性是指待排序元素中相等的元素在排序后相对位置不变。想象下两个相等元素在快排的树中，位置靠前的那个被拿到P位置，那么这两个元素的相对位置就变了，最终排序结果就是不稳定的。但如果是在归并排序树中，每次都将元素们对半分开再按大小合并，即使相等元素被放入左右两个子树，只要最后按原来元素位置顺序遍历合并，就能保证相等元素的相对位置跟原来一样，所以归并排序可以是稳定的

排序算法
算法 思想 复杂度 稳定性
冒泡排序（Bubble Sort） 重复比较相邻的两个元素，如果顺序不正确则交换，直到整个序列排序完成 O(n^2) 稳定
插入排序（Insertion Sort） 将待排序的元素逐个插入已排序的序列中的适当位置，直到整个序列排序完成 O(n^2) 稳定
选择排序（Selection Sort） 在未排序的序列中选择最小（或最大）的元素，将其放置在已排序序列的末尾，重复这个过程直到整个序列排序完成 O(n^2) 不稳定
快速排序（Quick Sort） 选择一个基准元素，将序列分为两个子序列，左边的子序列都小于基准元素，右边的子序列都大于基准元素，然后对两个子序列进行递归排序 O(nlogn) 不稳定
归并排序（Merge Sort） 将序列递归分为两个子序列，对每个子序列进行排序，然后合并两个有序子序列以得到排序后的序列 O(nlogn) 稳定
堆排序（Heap Sort） 将待排序序列构建为一个最大（或最小）堆，然后逐个从堆中取出最大（或最小）元素，重建堆，直到整个序列排序完成 O(nlogn) 稳定
希尔排序（Shell Sort） 将待排序序列按照一定的增量进行分组，对每个分组使用插入排序，然后逐步缩小增量直至为1，最后进行一次完整的插入排序 O(nlogn) 稳定

算法框架

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
# 冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 插入排序
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 选择排序
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]   # 随机索引random.randint(0,len(arr)-1) 或 随机打乱 random.shuffle(arr)
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 带有重复元素的数组快排
def quick_sort(arr, l, r):
    if l >= r:
        return
    less, p = partition(arr, l, r)
    quick_sort(arr, l, less - 1)
    quick_sort(arr, p, r)

def partition(arr, l, r):
    # 优化：随机选取piovt
    random_idx = random.randint(l, r)
    arr[l], arr[random_idx] = arr[random_idx], arr[l]
    piovt = arr[l]
    i, j = l + 1, r + 1
    less = l
    while i < j:
        if arr[i] < piovt:
            less += 1
            arr[i], arr[less] = arr[less], arr[i]
            i += 1
        elif arr[i] == piovt:
            i += 1   # i最后指定的是>piovt的元素
        elif arr[i] > piovt:
            j -= 1   # j最后指定的是第一个>piovt的元素
            arr[i], arr[j] = arr[j], arr[i]  
    arr[l], arr[less] = arr[less], arr[l]   # less最后指定的是<piovt的元素，交换后less-1<piovt
    return less, j

# 数组中无重复元素
def quick_sort(arr, l, r):
    if l >= r:
        return
    p = partition(arr, l, r)
    quick_sort(arr, l, p - 1)
    quick_sort(arr, p + 1, r)

def partition(arr, l, r):
    # 优化：随机选取piovt
    random_idx = random.randint(l, r)
    arr[l], arr[random_idx] = arr[random_idx], arr[l]
    piovt = arr[l]
    i, j = l + 1, r
    while i <= j:
        while i < r and arr[i] <= pivot:
            i += 1  # while结束时恰好 nums[i] > pivot
        while j > l and arr[j] > pivot:
            j -= 1  # while结束时恰好 nums[j] <= pivot
        # 此时 [l, i) <= pivot and (j, r] > pivot
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    arr[l], arr[j] = arr[j], arr[l]   # 交换后j为piovt
    return j
            
# random.shuffle(nums)    # 优化：随机选取piovt
quick_sort(nums, 0, len(nums) - 1)
return nums



# 归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1
    return merged


# 堆排序
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 建堆：升序排序用大顶堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 排序
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr


# 希尔排序
def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

    return arr

十大经典排序算法（动图演示）

力扣指南

排序算法
题目 技巧 难度
✅912. 排序数组 API、归并排序、快排（随机piovt+三路优化）、堆排序 🌟🌟
✅315. 计算右侧小于当前元素的个数 归并排序 🌟🌟🌟
✅剑指 Offer 51. 数组中的逆序对 同上，归并排序 🌟🌟🌟
✅493. 翻转对 借助归并排序 🌟🌟🌟
✅327. 区间和的个数 前缀和+归并排序 🌟🌟🌟
✅215. 数组中的第K个最大元素 优先队列；基于快速选择的快排 🌟🌟