Sorting学习笔记

Start

相比Array， Sorted Array在寻找数组元素上有优势，时间复杂度来到了O(logn)O(log n) (find_max, find_min达到了O(1)O(1) ), 接下来介绍几种sort的方法

Permutation Sort

暴力枚举法，通过检查数组每一个排列方式是否已经是sorted来得到sorted Array，
时间复杂度达到了O(n!⋅n)O(n! \cdot n) ，对于 n!n! 是排列的种类，这里不再过多赘述

Selection Sort

基本思路

  1. 找到最大：在当前子数组 A[0:i+1] 中找到最大元素的索引
  2. 交换位置：将最大元素交换到当前子数组的末尾 A[i]
  3. 递归排序：对剩余的子数组 A[0:i] 递归进行排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def selection_sort(A, i = None):    # T(i)
    '''Sort A[:i + 1]'''  
    if i is None: 
        i = len(A) - 1              # Θ(1)
    if i > 0:                       # Θ(1)
    '''先找到在i之前最大的数'''
        j = prefix_max(A, i)        # S(i)
        A[i], A[j] = A[j], A[i]     # Θ(1)
        selection_sort(A, i - 1)    # T(i - 1)
        
def prefix_max(A, i):               # S(i)
    '''Return index of maximum in A[:i + 1]'''  
    if i > 0:                       # Θ(1)
        j = prefix_max(A, i - 1)    # S(i - 1)git 
        if A[i] < A[j]:             # Θ(1)
            return j                # Θ(1)
    return i                        # Θ(1)

时间复杂度

  • prefix_max ： $$\Theta(n)$$
  • Selection_sort ： Θ(n2)\Theta(n ^ 2)

Insertion Sort

基本思路

  1. 递归排序前缀：先递归地对子数组 A[0:i] 进行排序
  2. 插入最后一个元素：将最后一个元素 A[i] 插入到已排序的前缀 A[0:i] 中的正确位置
  3. 重复交换：通过相邻元素的重复交换将新元素插入到正确位置

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def insertion_sort(A, i = None):                  # T(i)
    '''Sort A[:i + 1]'''
    if i is None:
        i = len(A) - 1                            # O(1)
    if i > 0:                                     # O(1)
        '''先递归排序前缀'''
        insertion_sort(A, i - 1)                  # T(i - 1)
        '''将最后一个元素插入到已排序的前缀中'''
        insert_last(A, i)                         # S(i)

def insert_last(A, i):                            # S(i)
    '''Sort A[:i + 1] assuming sorted A[:i]'''
    if i > 0 and A[i] < A[i - 1]:                 # O(1)
        '''如果当前元素比前一个元素小，则交换位置'''
        A[i], A[i - 1] = A[i - 1], A[i]           # O(1)
        '''继续向前插入'''
        insert_last(A, i - 1)                     # S(i - 1)

时间复杂度

  • insert_last：Θ(n)\Theta(n)
  • insertion_sort ： Θ(n2)\Theta(n ^2 )

Merge Sort

基本思路

  1. 递归排序前半部分和后半部分：将数组分成两个大致相等的子数组进行递归排序
  2. 合并排序后的子数组：使用双指针算法将两个已排序的子数组合并成一个有序数组
  3. 分治策略：通过不断分割和合并来实现整体排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def merge_sort(A, a = 0, b = None):              # T(b - a = n)
    '''Sort A[a:b]'''
    if b is None: 
        b = len(A)                               # O(1)
    if 1 < b - a:                                # O(1)
        c = (a + b + 1) // 2                     # O(1)
        merge_sort(A, a, c)                      # T(n / 2)
        merge_sort(A, c, b)                      # T(n / 2)
        L, R = A[a:c], A[c:b]                    # O(n)
        merge(L, R, A, len(L), len(R), a, b)     # S(n)

def merge(L, R, A, i, j, a, b):                 # S(b - a = n)
    '''Merge sorted L[:i] and R[:j] into A[a:b]'''
    if a < b:                                   # O(1)
        if (j <= 0) or (i > 0 and L[i - 1] > R[j - 1]):  # O(1)
            A[b - 1] = L[i - 1]                 # O(1)
            i = i - 1                           # O(1)
        else:                                   # O(1)
            A[b - 1] = R[j - 1]                 # O(1)
            j = j - 1                           # O(1)
        merge(L, R, A, i, j, a, b - 1)         # S(n - 1)

这边要注意，进行merge之前会分别对左右两边的分割子数组进行sort，当分割到子数组只剩一个，会进入merge，此时用双指针法必然能在merge中形成一个有序数组，然后不断的返回已排序的数组作为上一级merge中的左右分割子数组

  • 这边给出份示例的图解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[38, 27, 43, 3, 9, 82, 10]
           |
           | DIVIDE
           |
m([38, 27, 43, 3])       m([9, 82, 10])
            |                         |
m([38, 27])    m([43, 3])       m([9])   m([82, 10])
     |                 |               |
m([38]) m([27])  m([43]) m([3])   m([82]) m([10]) <-- 所有子数组均为单元素，已排序
      |                 |                |        
merge->[27,38]  merge->[3,43]     merge->[10,82] <-- 开始合并（Conquer & Combine）
              |                           |
       merge->[3, 27, 38, 43]    merge->[9, 10, 82]
           |                          |
           |       COMBINE            |
           |__________________________|
                       |
                 merge->[3, 9, 10, 27, 38, 43, 82] <-- 最终结果

时间复杂度

  • merge函数分析 ：S(0)=Θ(1)S(0) = \Theta(1), S(n)=S(n−1)+Θ(1)S(n) = S(n-1) + \Theta(1)
  • merge_sort函数分析：T(1)=Θ(1)T(1) = \Theta(1), T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n)

这边示例用递归树法分析

1
2
3
4
5
6
7
递归树深度：log₂n
第0层：1个节点，工作量Θ(n)
第1层：2个节点，每个工作量Θ(n/2)，总工作量Θ(n)
第2层：4个节点，每个工作量Θ(n/4)，总工作量Θ(n)
...
每层总工作量都是Θ(n)，共有log₂n层
总时间：T(n) = Θ(n) × log₂n = Θ(n log n)

综上分析，因此有Merge Sort时间复杂度为 Θ(nlogn)\Theta(n logn)