张芷铭的个人博客

总结

排序算法的重要性不言而喻，记录常见的十种排序算法，介绍排序思路并且给出代码。同时最后介绍常见语言的内置排序函数，例如python的sort() 1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)

总结

排序算法平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性
冒泡排序O(n²)O(n)O(n²)O(1)In-place稳定
选择排序O(n²)O(n²)O(n²)O(1)In-place不稳定
插入排序O(n²)O(n)O(n²)O(1)In-place稳定
希尔排序O(n log n)O(n log n)O(n²) *O(1)In-place不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)Out-place稳定
快速排序O(n log n)O(n log n)O(n²)O(log n)In-place不稳定
堆排序O(n log n)O(n log n)O(n log n)O(1)In-place不稳定
计数排序O(n +k)O(n+k)O(n+k)O(k)Out-place稳定
桶排序O(n +k)O(n+k)O(n²)O(n+k)Out-place稳定
基数排序O(n×k)O(n×k)O(n×k)O(n+k)Out-place稳定
  • 希尔排序的最差情况与选择的增量序列有关

![[Pasted image 20240409184811.png]]

冒泡排序

算法步骤

一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

什么时候最快

当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

什么时候最慢

当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

Python版本

1
2
3
4
5
6

def bubbleSort(arr):
    for i in range(1, len(arr)): # 所以，冒泡需要执行len(arr)-1轮
        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

优化策略

  1. 停止已排序检测（标志位优化） 最简单的优化是增加一个标志位来检测在一次遍历中是否有元素被交换。如果在一次遍历过程中没有任何两个元素发生交换，这意味着列表已经排序好了，因此算法可以提前停止。这个优化可以减少不必要的遍历，特别是在输入数组已经部分排序的情况下非常有效。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果在这一轮遍历中没有发生交换，说明已经排序完成，退出循环
        if not swapped:
            break
  1. 记录最后一次交换位置 在冒泡排序的每次遍历中，可以记录下最后一次元素交换的位置，该位置之后的元素显然已经处于排序好的状态，下一轮排序时只需要遍历到这个位置即可。这个优化减少了每轮遍历的长度，特别是当数组的一部分已经排序时非常有效。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def sortArray(self, arr: List[int]) -> List[int]:
        n = len(arr)
        swapped = True
        newn = 0
        while swapped:
            swapped = False
            for i in range(1, n):
                if arr[i - 1] > arr[i]:
                    arr[i], arr[i - 1] = arr[i - 1], arr[i]
                    newn = i
                    swapped = True  # 如果在这一轮遍历中没有发生交换，说明已经排序完成，退出循环
            n = newn
        return arr

选择排序

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

算法步骤

不断在剩余的数组中找到最小的放到排好的结果里

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

Python版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

插入排序

算法步骤

就像打扑克牌最开始理牌一样

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

Python版本

1
2
3
4
5
6
7
8
9

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

希尔排序

实质就是分组插入排序，该方法又称递减增量排序算法，因DL．Shell于1959年提出而得名。希尔排序是非稳定的排序算法。

通过引入“间隔”概念来提高插入排序的效率。其基本思想是将相距一定间隔的元素组成一个子序列，分别对这些子序列进行插入排序，随着间隔的逐渐减小，整个数据序列越来越接近于有序，最后当间隔为1时，进行一次插入排序后，数组即被排序。

开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

算法步骤

  1. 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
  2. 所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。
  3. 取第二个增量d2小于d1重复上述的分组和排序，直至所取的增量dt=1(dt小于dt-l小于…小于d2小于d1)，即所有记录放在同一组中进行直接插入排序为止。

最差时间复杂度

希尔排序的最差时间复杂度依赖于选用的间隔序列。对于不同的间隔序列，最差情况下的时间复杂度有很大的差异。一些常见间隔序列和它们的时间复杂度如下：

  • 使用原始的Shell序列（间隔为n/2, n/4, ..., 1）的时间复杂度约为O(n^2)。
  • Hibbard提出的间隔序列（1, 3, 7, ..., 2^k - 1）有O(n^(3/2))的最差时间复杂度。
  • Sedgewick提出的几种序列，其中一种的最差时间复杂度为O(n^(4/3))。
  • 最优的已知间隔序列，如Ciura序列（固定序列），对于中等大小的数组表现最好，但它的最差时间复杂度并不清楚，且随着序列的选择和数组的大小而变化。
    • Ciura序列: 1, 4, 10, 23, 57, 132, 301, 701, 1750 Ciura在其2001年的论文中提出了这个序列，并指出这个序列是基于经验数据调整得到的。值得注意的是，虽然原始论文只列出到1750，但是这个序列可以通过一个近似公式继续扩展：选择下一个间隔大约是前一个间隔的2.3倍。

Python版本

 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

def shell_sort(arr):
    # 开始带有间隔的插入排序
    gap = len(arr) // 2  # 初始间隔设置为数组长度的一半

    while gap > 0:
        for i in range(gap, len(arr)):
            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

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

优化策略

归并排序

分治法（Divide and Conquer）的典型应用。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  4. 重复步骤 3 直到某一指针达到序列尾；

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

Python版本

 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

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中间的位置，进行分割
        left_half = arr[:mid]  # 分割为左半部分
        right_half = arr[mid:]  # 分割为右半部分

        merge_sort(left_half)  # 递归排序左半部分
        merge_sort(right_half)  # 递归排序右半部分

        # 合并排序好的两半
        i = 0  # 左半部分的索引
        j = 0  # 右半部分的索引
        k = 0  # 合并后数组的索引

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 检查两部分中是否还有剩余的元素，如果有，直接追加到后面
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

优化策略

快速排序

找到一个pivot

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

Python版本

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

def quick_sort(arr):
    # 基线条件：如果数组只有0个或1个元素，就不需要排序
    if len(arr) <= 1:
        return arr
    else:
        # 选择基准值，这里我们选择列表的第一个元素
        pivot = arr[0]
        # 使用列表推导式将小于基准值的元素放到一个子数组
        less_than_pivot = [x for x in arr[1:] if x <= pivot]
        # 使用列表推导式将大于基准值的元素放到另一个子数组
        greater_than_pivot = [x for x in arr[1:] if x > pivot]
        # 对这两个子数组递归地进行快速排序，然后与基准值合并
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

优化策略

堆排序

堆（Heap）：[[堆]]（Heap）是一种特殊的完全二叉树，它满足两个主要特性：结构性和堆序性。根据堆序性的不同，堆可以分为最大堆和最小堆

算法步骤

  1. 创建一个堆 H[0……n-1]；

  2. 把堆首（最大值）和堆尾互换；

  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  4. 重复步骤 2，直到堆的尺寸为 1。

Python版本

 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

def heapify(arr, n, i):
    """将以第i个元素为根的子树调整为最大堆"""
    largest = i  # 初始化最大值为根
    left = 2 * i + 1     # 左 = 2*i + 1
    right = 2 * i + 2    # 右 = 2*i + 2

    # 如果左子节点存在，且大于根节点，则更新最大值
    if left < n and arr[largest] < arr[left]:
        largest = left

    # 同上，如果右子节点存在，且大于当前最大值，则更新最大值
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大值不是根节点，交换它们
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换

        # 递归地调整被影响的子树
        heapify(arr, n, largest)

def heapSort(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)

# 测试代码
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    print("Original array is:", arr)
    heapSort(arr)
    n = len(arr)
    print("Sorted array is:", arr)

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

  1. x

Python版本

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

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

优化策略

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

算法步骤

  1. 元素分布在桶中：

  1. 然后，元素在每个桶中排序：

Python版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def bucket_sort(arr):
    # 找出最大值和最小值，确定桶的数量
    max_val, min_val = max(arr), min(arr)
    bucket_size = (max_val - min_val) // len(arr) + 1
    buckets = [[] for _ in range(bucket_size)]

    # 将数组中的值分配到各个桶里
    for i in arr:
        idx = (i - min_val) // len(arr)
        buckets[idx].append(i)

    # 对每个桶进行排序，然后合并结果
    arr.clear()
    for bucket in buckets:
        arr.extend(sorted(bucket))

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
bucket_sort(arr)
print("Sorted array is:", arr)

优化策略

基数排序

基数排序适用于整数或者可以分解为整数的元素排序。它通过按位数切割整数或字符串，然后按每个位数分别排序。

算法步骤

  1. x

Python版本

 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

# 基数排序辅助函数：根据给定的数位进行排序
def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 计数
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # 更改count，现在包含位置信息
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 构建输出数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # 复制回arr
    for i in range(n):
        arr[i] = output[i]

# 主函数
def radix_sort(arr):
    # 找到最大值，确定最大位数
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort

优化策略

💬 评论