算法：排序

敖炜 Lv5
  2023-12-04 15:53:29 2023-12-04 15:53:29 创建   2024-04-19 09:30:31 2024-04-19 09:30:31 更新      8.4k 字  37 分钟  

这一篇要讲的是常见的排序算法

排序算法

排序算法依照特定的排序规则对一组数据按照特定顺序进行排序，得到有序数据

评价维度

  1. 运行效率：排序算法时间复杂度越低越好，总体操作数越少越好

  2. 就地性：原地排序是在原数组上直接操作实现排序，无须借助额外的辅助数组，节省内存。原地排序的数据搬运操作较少，运行速度快

  3. 稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变

  4. 自适应性：自适应排序的时间复杂度受输入数据的影响，最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等

    • 若最差时间复杂度差于平均时间复杂度，说明算法性能可能劣化，是负面属性
    • 若最佳时间复杂度优于平均时间复杂度，是正面属性

  5. 是否基于比较

    • 基于比较的排序依赖比较运算符来判断相对顺序，理论最优时间复杂度为
    • 非比较排序不使用比较运算符，时间复杂度可达，但通用性相对较差

理想排序算法

最理想的排序算法是运行快、原地、稳定、正向自适应、通用性好。但是这样的排序算法还没被发现，具体选择排序算法时需要进行权衡

选择排序

工作原理

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组长度为n，算法流程如下

  1. 初始状态下，所有元素未排序，未排序区间为[0, n-1]
  2. 选取区间[0, n-1]中的最小元素，将其与索引0处元素交换。数组前一个元素完成排序
  3. 选取区间[1, n-1]中的最小元素，将其与索引1处元素交换。数组前两个元素完成排序
  4. 以此类推。经过n-1轮选择与交换，数组前n-1个元素已排序
  5. 剩下一个元素必定是最大元素，无须排序，数组排序完成
1
2
3
4
5
6
7
8
def selection_sort(nums):
    n = len(nums)
    for i in range(n-1):
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j # 记录最小元素的索引
        nums[i], nums[k] = nums[k], nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
void selectionSort(vector<int> &nums){
    int n = nums.size();
    for(int i = 0; i < n - 1; i++){
        int k = i;
        for(int j = i + 1; j < n; j++){
            if(nums[j] < nums[k]){
                k = j;
            }
        }
        swap(nums[i], nums[k]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort(int nums[], int n){
    for(int i = 0; i < n - 1; i++){
        int k = i;
        for (int j = i + 1; j < n; j++){
            if(nums[j] < nums[k]){
                k = j
            }
        }
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

算法特性

  • 时间复杂度

  • 非自适应排序

  • 空间复杂度

  • 原地排序

  • 非稳定排序：如下图所示，元素的相对顺序可能发生改变

选择排序非稳定示例

冒泡排序

工作原理

通过连续地比较与交换相邻元素实现排序，每轮循环完成一个元素的排序。过程就像气泡从底部升到顶部一样。

从数组最左端开始向右遍历，依次比较相邻元素大小，若左元素 > 右元素就交换二者。每完成一次该过程，就会有一个未排序区间中的最大元素被移动到数组右端

设数组长度为n，算法流程如下

  1. 首先，对n个元素进行冒泡操作，将数组的最大元素交换至正确位置
  2. 接下来，对剩余n - 1个元素进行冒泡操作，第二大元素交换至正确位置
  3. 以此类推，经过n - 1轮冒泡，前n - 1大的元素被交换至正确位置
  4. 仅剩一个元素必定是最小元素，无须排序，数组排序完成
1
2
3
4
5
6
7
8
def bubble_sort(nums):
    n = len(nums)
    # 外循环：未排序区间为[0, i]
    for i in range(n-1, 0, -1):
        # 内循环：将未排序区间[0, i]中的最大元素交换至该区间的最右端
        for j in range(i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int> &nums){
    for(int i = nums.size() - 1; i > 0; i--){
        for(int j = 0; j < i; j++){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(int nums[], int size){
    for(int i = size - 1; i > 0; i--){
        for(int j = 0; j < i; j++){
            if(nums[j] > nums[j+1]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

效率优化

如果某一轮冒泡操作中没有执行任何交换操作，说明数组已经完成排序，可以直接返回。可增加一个标志位flag来监测这种情况，一旦出现立即返回

优化过后，冒泡排序最差时间复杂度和平均时间复杂度仍为；当输入数组完全有序时，最佳时间复杂度为

1
2
3
4
5
6
7
8
9
10
def bubble_sort_with_flag(nums):
    n = len(nums)
    for i in range(n - 1, 0, -1):
        flag = False
        for j in range(i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = True
        if not flag:
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSortWithFlag(vector<int>& nums){
    for(int i = nums.size() - 1; i > 0; i--){
        bool flag = false;
        for(int j = 0; j < i; j++){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubbleSortWithFlag(int nums[], int size){
    for(int i = size() - 1; i > 0; i--){
        bool flag = false;
        for(int j = 0; j < i; j++){
            if(nums[j] > nums[j+1]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
}

算法特性

  • 时间复杂度
  • 自适应排序
  • 空间复杂度
  • 原地排序
  • 稳定排序：冒泡中遇到相等元素不交换

插入排序

工作原理

与手动整理一副牌的过程非常相似，在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将元素插入到正确的位置。单次插入操作如下图

单词插入操作

算法流程如下

  1. 初始状态下，数组的第1个元素已完成排序
  2. 选取数组的第2个元素作为base，将其插入到正确的位置后，数组的前2个元素已排序
  3. 选取第3个元素作为base，将其插入到正确的位置后，**数组的前3个元素已排序
  4. 以此类推，在最后一轮中，选取最后一个元素作为base，将其插入到正确位置后，所有元素均已排序

插入排序流程

1
2
3
4
5
6
7
8
def insertion_sort(nums):
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > base:
            nums[j+1] = nums[j]
            j -= 1
        nums[j + 1] = base
1
2
3
4
5
6
7
8
9
10
11
void insertionSort(vector<int> &nums){
    for(int i = 1; i < nums.size(); i++){
        int base = nums[i];
        j = i - 1;
        while (j >= 0 && nums[j] > base){
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1] = base;
    }
}
1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int nums[], int size){
    for(int i = 1; i < size; i++){
        int base = nums[i];
        j = i - 1;
        while (j >= 0 && nums[j] > base){
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1] = base;
    }
}

算法特性

  • 时间复杂度，当输入数据完全有序时，插入排序达到最佳时间复杂度
  • 自适应排序
  • 空间复杂度
  • 原地排序
  • 稳定排序

插入排序优势

插入排序时间复杂度为，快速排序时间复杂度为。但在数据量较小的情况下，插入排序通常更快

该结论与线性查找和二分查找的适用情况的结论类似。快速排序此类的算法属于分治策略的排序算法，往往包含更多单元计算操作。数据量较小时，和数值接近，复杂度不占主导地位；每轮中的单元操作数量起到决定性作用

冒泡、选择、插入排序的时间复杂度都是，但实际情况中插入排序使用频率更高，原因如下

  • 冒泡排序基于元素交换实现，需要借助一个临时遍历。涉及三个单元操作；插入排序基于元素赋值实现，仅需一个单元操作。冒泡排序的计算开销通常比插入排序更高

  • 选择排序不具有正向自适应性，且不稳定；插入排序具有正向自适应性，且稳定，可应用于多级排序

选择、冒泡、插入排序思路总结

选择、冒泡、插入的基本思想都是：每一轮完成一个元素的排序，并将这个过程循环 n-1 轮。

三者在“每一轮完成一个元素的排序”的做法是不一样的。冒泡排序是基于相邻元素交换、插入排序是基于数组插入操作。

快速排序

工作原理

快速排序是一种基于分治策略的排序算法。核心操作是“哨兵划分”，其目标是：选组数组中某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，所有大于基准数的元素移到其右侧

哨兵划分流程如下：

  1. 选取数组最左端元素作为基准数，初始化两个指针i和j分别指向数组的两端
  2. 设置一个循环，在每轮中使用i(j)分别寻找第一个比大(小)的元素，然后交换这两个元素
  3. 循环执行步骤2，直到i和j相遇时停止，最后将基准数交换至两个子数组的分界线

哨兵划分完成后，原数组被划分为：左子数组、基准数、右子数组，且满足左子数组任意元素 基准数 右子数组任意元素。接下来只需对两个子数组进行排序

哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def partition(self, nums, left, right):
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1 # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1 # 从左向右找首个大于基准数的元素
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[left] = nums[left], nums[i]
    return i

"""基准数最终所在索引有两种情况得到：
    1. 由j靠近i得到，此时i指向的值小于基准值，j不断向左，使得i=j循环终止
    2. 由i靠近j得到，最后一轮循环中，j指向的值小于基准值，i不断向右，使得i=j循环终止
综上所述，最终i=j时得到的索引处值小于基准值，与基准值交换得到有序结果
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(vector<int>& nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

int partition(vector<int>& nums, int left, int right){
    int i = left, j = right;
    while(i < j){
        while(i < j && nums[j] >= nums[left]){
            j--;
        }
        while(i < j && nums[i] <= nums[left]){
            i++;
        }
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

int partition(int nums[], int left, int right) {
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--;
        }
        while (i < j && nums[i] <= nums[left]) {
            i++;
        }
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}

快速排序整体流程如下：

  1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组
  2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”
  3. 持续递归，直到子数组长度为1时终止，从而完成整个数组的排序

快速排序流程

1
2
3
4
5
6
def quick_sort(self, nums, left, right):
    if left >= right:
        return
    pivot = self.partition(nums, left, right)
    self.quick_sort(nums, left, pivot-1)
    self.quick_sort(nums, pivot+1, right)
1
2
3
4
5
6
7
8
void quickSort(vector<int>& nums, int left, int right){
    if(left >= right){
        return;
    }
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot-1);
    quickSort(nums, pivot+1, right);
}
1
2
3
4
5
6
7
8
void quickSort(int nums[], int left, int right){
    if(left >= right){
        return;
    }
    int pivot = partition(nums, left, right);
    quickSort(nums, left, pivot-1);
    quickSort(nums, pivot+1, right);
}

算法特性

  • 时间复杂度：平均情况下，哨兵划分的递归层数为，每层中的总循环次数为，总体使用时间
  • 自适应排序：最差情况下，每轮哨兵划分都将长度为的数组划分为长度为0和n-1的两个子数组，递归层数为，每层中的循环数为，总体使用时间
  • 空间复杂度：输入数组完全倒序的情况下，达到最差递归深度，使用栈帧空间
  • 原地排序
  • 非稳定排序：哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧

快速排序为什么快

虽然快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要原因如下

  • 出现最差情况的概率很低
  • 缓存使用效率高：执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。
  • 复杂度的常数系数小：这三种排序算法中，快速排序的比较、赋值、交换等操作的总数量最少

基准数优化

快速排序在某些输入下可能降低，如完全倒序的数组，快速排序会退化为冒泡排序，可通过优化哨兵划分中的基准数的选取策略来避免这种情况。

我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。采用这种方法后，时间复杂度劣化至的概率大大降低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def median_three(self, nums, left, mid, right):
    """选取三个元素中的中位数"""
    if (nums[left] < nums[mid]) ^ (nums[left] < nums[right]):
        return left
    elif (nums[mid] < nums[left]) ^ (nums[mid] < nums[right]):
        return mid
    return right

def partition(self, nums, left, right):
    med = self.median_three(nums, left, (left + right) // 2, right)
    nums[left], nums[med] = nums[med], nums[left]
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1
        while i < j and nums[i] <= nums[left]:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[left] = nums[left], nums[i]
    return i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int medianThree(vector<int> &nums, int left, int mid, int right) {
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}

int partition(vector<int> &nums, int left, int right) {
    int med = medianThree(nums, left, (left + right) / 2, right);
    swap(nums, left, med);
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;
        while (i < j && nums[i] <= nums[left])
            i++;
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int medianThree(int nums[], int left, int mid, int right) {
    if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
        return left;
    else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
        return mid;
    else
        return right;
}

int partition(int nums[], int left, int right) {
    int med = medianThree(nums, left, (left + right) / 2, right);
    swap(nums, left, med);
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;
        while (i < j && nums[i] <= nums[left])
            i++;
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}

尾递归优化

某些输入下(如完全倒序输入数组)，快速排序可能占用空间较多，递归树的高度最高可达。

为防止栈帧空间的积累，在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过，因此每次尾递归优化都会将处理的数组长度减少至少一半，**确保递归深度不超过，从而将最差空间复杂度优化至

1
2
3
4
5
6
7
8
9
10
def quick_sort(self, nums, left, right):
    while left < right:
        pivot = self.partition(nums, left, right)
        if pivot - left < right - pivot:
            self.quick_sort(nums, left, pivot - 1) # 递归排序左子数组
            left = pivot + 1 # 剩余未排序区间为[pivot+1, right]
        else:
            self.quick_sort(nums, pivot + 1, right)
            right = pivot - 1 # 剩余未排序区间为[left, pivot-1]

1
2
3
4
5
6
7
8
9
10
11
12
void quickSort(vector<int>& nums, int left, int right){
    while(left < right){
        int pivot = partition(nums, left, right);
        if(pivot - left < right - pivot){
            quickSort(nums, left, pivot - 1);
            left = pivot + 1;
        }else{
            quickSort(nums, pivot + 1, right);
            right = pivot - 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
void quickSort(int nums[], int left, int right){
    while(left < right){
        int pivot = partition(nums, left, right);
        if(pivot - left < right - pivot){
            quickSort(nums, left, pivot - 1);
            left = pivot + 1;
        }else{
            quickSort(nums, pivot + 1, right);
            right = pivot - 1;
        }
    }
}

归并排序

工作原理

归并排序是一种基于分治策略的排序算法，包含划分和合并两个阶段

  1. 划分阶段：通过不断递归将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题

  2. 合并阶段：当数组长度为1时终止划分，开始合并，持续地将左右两个较短地有序数组合并为一个较长地有序数组，直至结束

归并排序地划分与合并阶段

算法流程如下：

  • 划分阶段：从顶至底递归地将数组从中点切分为两个子数组

    1. 计算数组中点mid，递归划分左子数组(区间[left, mid])和右子数组(区间[mid+1, right])
    2. 递归执行步骤1，直至子数组区间长度为1时终止

  • 合并阶段：从底至顶将左子数组和右子数组合并为一个有序数组，从长度为1的子数组开始合并，合并阶段每个子数组都是有序的

归并排序与二叉树后序遍历的递归顺序是一致的

  • 后序遍历：先递归左子树，再递归右子树，最后处理根节点
  • 归并排序：先递归左子数组，再递归右子数组，最后处理合并
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 merge(nums, left, mid, right):
    """合并左子数组和右子数组"""
    # 创建一个临时数组tmp，用于存放合并后的结果
    tmp = [0] * (right - left + 1)
    # 初始化左子数组和右子数组的起始索引
    i, j, k = left, mid + 1, 0
    while i <= mid and j <= right:
        if nums[i] < nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1
        k += 1
    while i <= mid:
        tmp[k] = nums[i]
        i += 1
        k += 1
    while j <= right:
        tmp[k] = nums[j]
        j += 1
        k += 1
    for k in range(0, len(tmp)):
        nums[left + k] = tmp[k]

def merge_sort(nums, left, right):
    if left >= right:
        return # 当子数组长度为1时终止递归
    mid = (left + right) // 2
    merge_sort(nums, left, mid)
    merge_sort(nums, mid + 1, right)
    merge(nums, left, mid, right)
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
void merge(vector<int>& nums, int left, int mid, int right){
    vector<int> tmp(right - left - 1);
    int i = left, j = mid + 1, k = 0;
    while(i <= mid && j <= right){
        if (nums[i] <= nums[j]){
            tmp[k++] = nums[i++];
        }else{
            tmp[k++] = nums[j++];
        }
    }

    while(i <= mid){
        tmp[k++] = nums[i++];
    }

    while(j <= right){
        tmp[k++] = nums[j++];
    }

    for(k = 0; k < tmp.size(); k++){
        nums[left + k] = tmp[k];
    }
}

void mergeSort(vector<int>& nums, int left, int right){
    if (left >= right){
        return;
    } 
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}
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
void merge(int nums[], int left, int mid, int right){
    int tmp[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while(i <= mid && j <= right){
        if (nums[i] <= nums[j]){
            tmp[k++] = nums[i++];
        }else{
            tmp[k++] = nums[j++];
        }
    }
    while(i <= mid){
        tmp[k++] = nums[i++];
    }
    while(j <= right){
        tmp[k++] = nums[j++];
    }

    for(k = 0; k < (right-left+1); k++){
        nums[left + k] = tmp[k]; 
    }
}

void mergeSort(int nums[], int left, int right){
    if (left >= right){
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid+1, right);
    merge(nums, left, mid, right);
}

算法特性

  • 时间复杂度：划分产出高度为的递归树，每层合并的总操作数为n
  • 非自适应排序
  • 空间复杂度：递归深度为，栈帧空间大小为，合并操作需要辅助数组实现，使用大小的额外空间
  • 非原地排序
  • 稳定排序

链表排序

对于链表使用归并排序，可以将链表排序任务的空间复杂度优化至

  • 划分阶段用迭代代替递归
  • 合并阶段仅需改变指针即可，无须额外数据结构

堆排序

工作原理

基于堆数据结构实现的高效排序算法，利用建堆操作和元素出堆操作实现堆排序

  1. 输入数组并建立小顶堆，此时最小元素位于堆顶
  2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列

以上实现方法需借助一个额外数组来保存弹出的元素，较浪费空间，下面有一种更优雅的实现

  1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶
  2. 将堆顶元素（数组中第一个元素）与堆底元素（数组中最后一个元素）交换。完成交换后，堆的长度减一，已排序元素数量加一
  3. 从堆顶元素开始，从顶到底执行堆化操作(Sift Down)。完成堆化后，堆的性质得到修复
  4. 循环执行第2步和第3步。循环n-1轮，完成排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sift_down(nums, n, i):
    """堆的长度为n，从节点i开始，从顶至底堆化"""
    while True:
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        if ma == i:
            break
        nums[i], nums[ma] = nums[ma], nums[i]
        i = ma

def heap_sort(nums):
    # 建堆操作
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    for i in range(len(nums) - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        sift_down(nums, i, 0)

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
void siftDown(vector<int>& nums, int n, int i){
    while(true){
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i
        if (l < n && nums[l] > nums[ma]){
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]){
            ma = r;
        } 
        if (ma == i){
            break;
        }
        swap(nums[i], nums[ma]);
        i = ma;
    }
}

void heapSort(vector<int>& nums){
    for (int i = nums.size() / 2 - 1; i >= 0; --i){
        siftDown(nums, nums.size(), i);
    }
    for (int i = nums.size() - 1; i > 0; --i){
        swap(nums[0], nums[i]);
        siftDown(nums, i, 0);
    }
}
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
void siftDown(int nums[], int n, int i){
    while(1){
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma]){
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]){
            ma = r;
        }
        if (ma == i){
            break;
        }
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        i = ma;
    }
}

void heapSOrt(int nums[], int size){
    for(int i = n / 2 - 1; i >= 0; --i){
        siftDown(nums, n, i);
    }
    for(int i = size - 1; i > 0; --i){
        int temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        siftDown(nums, i, 0);
    }
}

算法特性

  • 时间复杂度：建堆操作使用时间。从堆中提取最大元素的时间复杂度为，共循环n-1轮
  • 非自适应排序
  • 空间复杂度
  • 原地排序
  • 非稳定排序：交换堆顶和堆底元素时，相等元素的相对位置可能发生变化

基于比较的排序算法 VS 非比较排序算法

前述几种排序算法都属于基于比较的排序算法，通过比较元素间的大小来实现排序，这一类排序算法的时间复杂度无法超越

而接下来几种非比较排序算法，时间复杂度可以达到线性阶

桶排序

工作原理

桶排序是分治策略的典型应用。通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并

设数组长度为n，元素是范围[0, 1)内的浮点数，桶排序流程如下

  1. 初始化k个桶，将n个元素分配到k个桶中
  2. 对每个桶分别执行排序
  3. 按照桶从小到大的顺序合并结果

桶排序算法流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bucket_sort(nums):
    k = len(nums) // 2
    buckets = [[] for _ in range(k)]
    # 1. 将数组元素分配到各个桶中
    for num in nums:
        # 输入数据范围为[0, 1)，使用num * k 映射到范围[0, k-1]
        i = int(num * k)
        buckets[i].append(num)
    # 2. 对各个桶执行排序
    for bucket in buckets:
        buckets.sort()
    # 3. 遍历桶合并结果
    i = 0
    for bucket in buckets:
        for num in bucket:
            nums[i] = num
            i += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bucketSort(vector<float>& nums){
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    for (float num : nums){
        int i = num * k;
        buckets[i].push_back(num);
    }
    for(vector<float>& bucket : buckets){
        sort(bucket.begin(), bucket.end());
    }

    int i = 0;
    for (vector<float>& bucket : buckets){
        for (float num : bucket){
            nums[i++] = num;
        }
    }
}
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
void bucketSort(float nums[], int size){
    int k = size / 2;
    float **buckets = calloc(k, sizeof(float*));
    for (int i = 0; i < k; i++){
        buckets[i] = calloc(ARRAY_SIZE, sizeof(float));
    }

    for (int i = 0; i < size; i++){
        int bucket_idx = nums[i] * k;
        int j = 0;
        while(buckets[bucket_idx][j] > 0 && buckets[bucket_idx][j] < nums[i]){
            j++;
        }
        float temp = nums[i];
        while(j < ARRAY_SIZE && buckets[bucket_idx][j] > 0){
            swap(&temp, &buckets[bucket_idx][j]);
        }
        buckets[bucket_idx][j] = temp;
    }

    for (int i = 0; i < k; i++){
        qsort(buckets[i], ARRAY_SIZE);
    }

    for(int i = 0, j = 0; j < k; j++){
        for(int l = 0; i < ARRAY_SIZE; l++){
            if(buckets[j][l] > 0){
                nums[i++] = buckets[j][l];
            }
        }
    }

    for (int i = 0; i < k; i++){
        free(buckets[i]);
    }
    free(buckets);
}

算法特性

  • 适用于处理体量很大的数据，当系统内存无法一次性加载所有数据时，可将数据进行分桶

  • 时间复杂度：假设元素在各个桶平均分配，那么每个桶内的元素数量为，排序单个桶使用时间，排序所有桶使用时间。当桶数量k比较大时(k=n/2)，时间复杂度则趋向于。合并结果时需要遍历所有桶和元素，花费时间

  • 自适应排序：最差情况下，所有数据分配到一个桶中，且排序该桶使用时间

  • 空间复杂度：借助k个桶和总共n个元素的额外位置

  • 非原地排序

  • 是否稳定取决于桶内排序算法是否稳定

如何实现平均分配

桶排序时间复杂度达到的关键在于将元素均匀分配到各个桶中，但实际数据往往不是均匀分布的。

为实现平均分配，可以先设定一条大致的分界线，将数据粗略分到x个桶中。分配完毕后，再将商品较多的桶继续划分为x个桶，直至所有桶中的元素数量大致相同

递归划分桶

如果提前知道数据的概率分布，则可以根据数据概率分布设置每个桶的分界线

计数排序

工作原理

通过统计元素数量来实现排序，通常应用于整数数组

给定一个长度为n的数组nums，其中元素都是“非负整数”，计数排序整体流程如下

  1. 遍历数组，找出其中的最大数字，记为m，创建一个长度为m+1的辅助数组counter
  2. 用counter统计nums中各数字出现次数，counter[num]对应数字num的出现次数
  3. counter的各个索引天然有序，因此相当于所有数字已经排序好了。接下来遍历counter，根据各数字出现次数从小到大的顺序填入nums即可

计数排序流程

1
2
3
4
5
6
7
8
9
10
11
12
def counting_sort_naive(nums):
    m = 0
    for num in nums:
        m = max(m, num)
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void countingSortNaive(vecctor<int>& nums){
    int m = 0;
    for (int num : nums){
        m = max(m, num);
    }
    vector<int> counter(m + 1, 0);
    for (int num : nums){
        counter[num]++;
    }
    int i = 0;
    for (int num = 0; num < m + 1; i++){
        for (int j = 0; j < counter[num]; j++){
            nums[i++] = num;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void countingSortNaive(int nums[], int size){
    int m = 0;
    for (int i = 0; i < size; i++){
        if(nums[i] > m){
            m = nums[i];
        }
    }

    int *counter = (int*)calloc(m + 1, sizeof(int))
    for (int i = 0; i < size; i++){
        counter[nums[i]]++;
    }

    int i = 0;
    for (int num = 0; num < (m + 1); num++){
        for(int j = 0; j < counter[num]; j++){
            nums[i++] = num;
        }
    }

    free(counter);
}

从桶排序的角度看，可将计数排序中counter的每个索引视为一个桶，将统计数量的过程看作各个元素分配到对应的桶中。计数排序是桶排序在整型数据下的一个特例

完整实现

如果输入数据是对象，前面的步骤3就失效了。

当输入数据是对象时，如何才能得到原数据的排序结果呢？首先计算counter的前缀和。索引i处的前缀和prefix[i]等于数组前i个元素之和

**前缀和具有明确意义，prefix[num] - 1代表元素num在结果数组res中最后一次出现的索引。接下来倒序遍历（保证稳定性）原数组nums的每个元素num，在每轮迭代中执行以下两步

  1. 将num填入数组res的索引prefix[num] - 1处
  2. 令前缀和prefix[num]减小1，从而得到下次放置num的索引

遍历完成后，数组res中就是排序好的结果，用res覆盖原数组nums即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def counting_sort(nums):
    m = max(nums)
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 计算前缀和
    for i in range(m):
        counter[i + 1] += counter[i]
    n = len(nums)
    res = [0] * n
    for i in range(n - 1, -1, -1):
        num = nums[i]
        res[counter[num] - 1] = num
        counter[num] -= 1
    # 覆盖原数组
    for i in range(n):
        nums[i] = res[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
void countingSort(vector<int>& nums){
    int m = 0;
    for (int num : nums){
        m = max(num, m);
    }

    vector<int> counter(m + 1, 0);
    for (int num : nums){
        counter[num]++;
    }

    for (int i = 0; i < m; i++){
        counter[i+1] += counter[i];
    }

    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; --i){
        int num = nums[i];
        res[counter[num] - 1] = num;
        counter[num]--;
    }
    nums = res;
}
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
void countingSort(int nums[], int size){
    int m = 0;
    for (int i = 0; i < size; i++){
        if(nums[i] > m){
            m = nums[i];
        }
    }

    int *counter = (int*)calloc(m+1, sizeof(int));
    for(int i = 0; i < size; i++){
        counter[nums[i]]++;
    }

    for (int i = 0; i < m; i++){
        counter[i+1] += counter[i];
    }

    int* res = (int*)malloc(sizeof(int) * size);
    for (int i = size - 1; i >= 0; i--){
        int num = nums[i];
        res[counter[num] - 1] = num;
        counter[num]--;
    }
    memcpy(nums, res, size * sizeof(int));
    free(counter);
}

算法特性

  • 时间复杂度：n为数据量，m为最大值，需遍历nums和counter，都使用线性时间，一般情况下，时间复杂度趋于
  • 空间复杂度：借助了长度分别为n和m的数组res和counter
  • 非原地排序
  • 稳定排序：倒序遍历nums可以避免改变相等元素之间的相对位置，实现稳定排序

局限性

  • 计数排序只适用于非负整数，若想用于其他类型的数据，要确保这些数据可以转换为非负整数并且转换过程中不能改变各个元素之间的相对大小关系

  • 计数排序适用于数据量大但数据范围较小的情况，若数据范围较大，则m过大，会占用过多空间，当时，计数排序使用时间，可能比排序算法还要慢

基数排序

工作原理

基数排序核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果

亦学号数据为例，假设数字最低位是第一位，最高位是第八位，基数排序流程如下

  1. 初始化位数k=1
  2. 对学号的第k位执行“计数排序”。完成后，数据会根据第k位从小到大排序
  3. 将k增加1，然后执行步骤2，直到所有位都排序完成后结束

基数排序算法流程

对于一个d进制的数字x，要获取其第k位，可以使用以下计算公式

mod 

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
def digit(num, exp):
    """获取元素num的第k位，其中exp=10^(k-1)"""
    # 传入exp而非k可以避免在此重复执行昂贵的次方计算
    return (num // exp) % 10

def counting_sort_digit(nums: list[int], exp):
    """计数排序（根据nums第k位排序）"""
    counter =  [0] * 10
    n = len(nums)
    for i in range(n):
        d = digit(nums[i], exp)
        counter[d] += 1
    for i in range(1, 10):
        counter[i] += counter[i - 1]
    res = [0] * n
    for i in range(n - 1, -1, -1):
        d = digit(nums[i], exp)
        j = counter[d] - 1
        res[j] = nums[i]
        counter[d] -= 1
    for i in range(n):
        nums[i] = res[i]

def radix_sort(nums):
    m = max(nums)
    exp = 1
    while exp <= m:
        counting_sort_digit(nums, exp)
        exp *= 10
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
int digit(int num, int exp){
    return (num / exp) % 10;
}

void countingSortDigit(vector<int>& nums, int exp){
    vector<int> counter(10, 0);
    int n = nums.size();
    for (int i = 0; i < size; i++){
        int d = digit(nums[i], exp);
        counter[d]++;
    }

    for (int i = 0; i < 9; i++){
        counter[i + 1] = counter[i];
    }

    vector<int> res(n, 0);
    for (int i = n - 1; i >= 0; i--){
        int d = digit(nums[i], exp);
        int j = counter[d];
        res[j] = nums[i];
        counter[d]--;
    }

    nums = res;
}

void radixCounting(vector<int>& nums){
    int m = *max_element(nums.begin(), nums.end());

    for(int exp = 1; exp <= m; exp *= 10){
        countingSortDigit(nums, exp);
    }
}
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
int digit(int num int exp){
    return (num / exp) % 10;
}

void countingSortDigit(int nums[], int size, int exp){
    int *counter = (int*)calloc(10, sizeof(10));
    for (int i = 0; i < size; i++){
        int d = digit(nums[i], exp);
        counter[d]++;
    }

    for (int i = 0; i < 9; i++){
        counter[i + 1] = counter[i];
    }

    int* res = (int*)calloc(size, 0);
    for (int i = size - 1; i >= 0; i--){
        int d = digit(nums[i], exp);
        int j = counter[d];
        res[j] = nums[i];
        counter[d]--;
    }

    memcpy(nums, res, size * sizeof(int));

    free(res);
}

void radixSort(int nums[], int size){
    int max = INT32_MIN;
    for (size_t i = 0; i < size; i++){
        if(nums[i] > max){
            max = nums[i];
        }
    }

    for(int exp = 1; exp <= max; exp *= 10){
        countingSortDigit(nums, size, exp);
    }
}

由于数字的高位优先级高于低位，因此应该先排序低位再排序高位

算法特性

与计数排序相比，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大(如浮点数)

  • 时间复杂度：n为数据量，d进制，最大位数为k，对 某一位执行计数排序使用时间，排序k位使用时间。d和k相对n较小，时间复杂度趋向
  • 空间复杂度：与计数排序相同
  • 非原地排序
  • 稳定排序：取决于计数排序是否稳定

小结（我居然写到了这里，你居然也看到了这里，我们真厉害）

主流排序算法对比

  • 标题: 算法：排序
  • 作者: 敖炜
  • 创建于 : 2023-12-04 15:53:29
  • 更新于 : 2024-04-19 09:30:31
  • 链接: https://ao-wei.github.io/2023/12/04/算法：排序/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
算法：排序
  1. 排序算法
    1. 评价维度
    2. 理想排序算法
  2. 选择排序
    1. 工作原理
    2. 算法特性
  3. 冒泡排序
    1. 工作原理
    2. 效率优化
    3. 算法特性
  4. 插入排序
    1. 工作原理
    2. 算法特性
    3. 插入排序优势
  5. 选择、冒泡、插入排序思路总结
  6. 快速排序
    1. 工作原理
    2. 算法特性
    3. 快速排序为什么快
    4. 基准数优化
    5. 尾递归优化
  7. 归并排序
    1. 工作原理
    2. 算法特性
    3. 链表排序
  8. 堆排序
    1. 工作原理
    2. 算法特性
  9. 基于比较的排序算法 VS 非比较排序算法
  10. 桶排序
    1. 工作原理
    2. 算法特性
    3. 如何实现平均分配
  11. 计数排序
    1. 工作原理
    2. 完整实现
    3. 算法特性
    4. 局限性
  12. 基数排序
    1. 工作原理
    2. 算法特性
  13. 小结（我居然写到了这里，你居然也看到了这里，我们真厉害）