【排序算法】Leetcode刷题心得

0. 排序算法相关资料

十大经典排序算法
Python实现十大经典排序算法–python3实现（以及全部的排序算法分类）

1. 冒泡排序

# 基础算法
def bubblesort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] =  arr[j+1], arr[j]
            
    return arr

# 考虑后续数列已经有序不需要比较了
def bubblesort_v1(arr):
    for i in range(1, len(arr)):
        flag = 0 #有序标记，每一轮的初始是true
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] =  arr[j+1], arr[j]
                flag = 1 #有元素交换，所以不是有序，标记变为1

        #一趟下来是否发生位置交换，如果没有交换直接跳出大循环
        if flag == 0:
            break
            
    return arr

# 考虑每一趟比较的后面几个，已经有序不需要比较了
def bubblesort_v2(arr):
    last_Exchange_idx = 0
    #无序数列的边界，每次比较只需要比到这里为止
    sort_border = len(arr) - 1
    for i in range(1, len(arr)):
        flag = 0 #有序标记，每一轮的初始是true
        for j in range(0, sort_border):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] =  arr[j+1], arr[j]
                flag = 1 #有元素交换，所以不是有序，标记变为1
                last_Exchange_idx = j #记录每次交换的坐标
        
        sort_border = last_Exchange_idx
        #一趟下来是否发生位置交换，如果没有交换直接跳出大循环
        if flag == 0:
            break
            
    return arr

A = [1,3,6,9,4,6,0]
# bubblesort(A)
# bubblesort_v1(A)
bubblesort_v2(A)
print(A)
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

• 基础算法时间复杂度：

4 个石子的时候排完序需要 3 趟，第一趟需要比较3次，第二趟需要比较2次，第三趟需要比较1次，那一共比较了 3 + 2 + 1 次；

那如果有 n 个石子呢？

那就需要 (n-1) + (n-2) +…+2+1 次，很显然：

根据复杂度的规则，去掉低阶项（也就是 n/2）,并去掉常数系数，那复杂度就是 **O(n^2)**了；
冒泡排序也是一种稳定排序，因为在两个数交换的时候，如果两个数相同，那么它们并不会因为算法中哪条语句相互交换位置

2. 选择排序

def select_sort(arr):
    for i in range(0,len(arr)-1):#比较n-1次
        # 记录最小数的索引 
        minIndex = i
        for j in range(i+1,len(arr)):#比较第i个和i之后数的大小
            #若此时minIndex记录的不是最小数，更行minIndex
            if arr[minIndex] > arr[j]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if minIndex != i:
            arr[minIndex], arr[i] = arr[i], arr[minIndex]

    return arr
1
2
3
4
5
6
7
8
9
10
11
12
13

• 时间复杂度：

无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

3. 插入排序

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

• 复杂度分析:

平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1);
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

4. 希尔排序

def shell_sort(arr):
    gap = len(arr) // 2
    while(gap>=1):
        for i in range(gap, len(arr)):
            tmp = arr[i]
            j = i - gap
            while(j>=0 and arr[j]>tmp):
                arr[j+gap] = arr[j]
                j = j - gap
            arr[j+gap] = tmp 
        gap //= 2
    return 0
1
2
3
4
5
6
7
8
9
10
11
12

5. 归并排序

import math
def merge_sort(arr):
    if len(arr) < 2:
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[:middle], arr[middle:]
    return merge(merge_sort(left), merge_sort(right))

def merge(left, right):
    ans = []
    while left and right:
        if left[0]>= right[0]:
            ans.append(right.pop(0))
        else:
            ans.append(left.pop(0))
    while left:
        ans.append(left.pop(0))
    while right:
        ans.append(right.pop(0))
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 算法步骤：

（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
（4）重复步骤 3 直到某一指针达到序列尾；
（5）将另一序列剩下的所有元素直接复制到合并序列尾。

• 复杂度分析：

算法复杂度：O（nlogn）

• 核心思想：

分而治之

6. 快速排序

def quickSort(arr,left=None, right=None):
    left = 0 if not isinstance(left, (int,float)) else left
    right = len(arr)-1 if not isinstance(right, (int,float)) else right
    if left < right:
        index = partition(arr, left, right) # arr中index左边的值小于arr[index]，右边的值大于arr[index]
        # 分别对arr左边的值再次递归调用quicksort
        quickSort(arr, left, index-1) 
        quickSort(arr, index+1, right)
    return arr

def partition(arr, left, right):
    pivot = left # 选用最左边的数作为pivot
    index = pivot+1 # index记录比pivot小的数的位置
    i = index # 从pivot位置后的一个数开始遍历
    while(i<=right): # 遍历到最后一个数
        if arr[i] < arr[pivot]: #如果此时遍历的数小于pivot
            swap(arr, i, index) #交换正在遍历的数与比pivot小的数的位置
            index += 1 # 因为此时index已经被用了，+1，记录下一个小于pivot数待交换的位置
        i += 1
    swap(arr, pivot, index-1) #最后将pivot的代表数与下一个小于pivot的数的最后一个数交换
    # index-1因为记录的是下一个小于pivot数待交换的位置
    return index-1 # 返回分界索引，此时arr[index-1]左边都小于pivot，右边都大于pivot

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
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

7. 堆排序

堆排序详解

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1): #从最后一个非叶子节点开始
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1 #对于结点i，左结点为2*i+1
    right = 2*i+2 # 对于结点i，右结点为2*i+2
    largest = i #此时最大结点为i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left #若左节点比i大，替换
    if ri
|
|  |  |
|--|--|
|  |  |
|  |
|--|--|
|  |  |
ght < arrLen and arr[right] > arr[largest]:
        largest = right #若右节点比i大，替换

    if largest != i: #若最大结点不是根节点
        swap(arr, i, largest) #交换最大结点值至根节点
        heapify(arr, largest) #递归调用，将此时最大结点作为根节点，调整为大根堆的数据结构

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen 
    arrLen = len(arr)
    buildMaxHeap(arr) #先构建一个大根堆
    for i in range(len(arr)-1,0,-1): #从最后一个数开始
        swap(arr,0,i) #交换最大的数（第一个数）和最后一个数
        arrLen -=1 #堆的大小减一，用global变量控制
        heapify(arr, 0) #将交换且大小减一的arr重新变为大根堆
    return arr
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

• 复杂度分析：

堆排序无关乎初始序列是否已经排序的状态，始终有两部分过程，构建初始的大顶堆的过程时间复杂度为O(n)，交换及重建大顶堆的过程中，需要交换n-1次，重建大顶堆的过程根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以它最好和最坏的情况时间复杂度都是O(nlogn)，空间复杂度O(1)。

8.计数排序

9. 桶排序

10.基数排序