十大排序算法

排序

笔记

发布日期: 2024-05-22

更新日期: 2024-07-30

文章字数: 4.5k

阅读时长: 16 分

阅读次数:

一、冒泡排序（Bubble Sort）

基本思想：

从数组的一段开始，两两比较大小，较小的数上冒，较大的数下沉。每轮比较都会一个数回归到应该所在的位置上

算法流程

分析

时间复杂度：

最坏情况（逆序排列）：
在最坏情况下，每一对元素都需要比较和交换，总共需要进行 (\frac{n(n-1)}{2}) 次比较和交换，因此时间复杂度为 (O(n^2))。
最佳情况（已排序）：
在最佳情况下，数组已经是有序的，第一次遍历时不会发生任何交换操作。由于使用了标志位 flag 来检测是否发生交换，排序可以在第一次遍历后提前终止，因此时间复杂度为 (O(n))。
平均情况：
在平均情况下，时间复杂度也是 (O(n^2))，因为大多数情况下都需要对每对元素进行比较和交换。

空间复杂度：

冒泡排序是原地排序算法（in-place sorting），只需要常数级别的额外空间来存储临时变量。因此，空间复杂度为 (O(1))。

稳定性

冒泡排序是稳定的排序算法。在冒泡排序中，只有当两个元素满足 `A[j-1] > A[j]` 时才会交换它们的位置，这意味着如果两个相等的元素，排序后它们的相对位置不会改变，因此冒泡排序保持了稳定性。

适用性

顺序表（数组）：
冒泡排序适用于顺序表（数组），因为在数组中，元素的随机访问效率很高，可以直接通过索引访问和修改元素值。
链表：
冒泡排序不适用于链表。虽然链表也可以通过两两比较相邻元素进行交换，但由于链表中的元素交换操作涉及指针的调整，效率较低。而且链表不支持直接访问，需要从头遍历到特定位置，增加了额外的时间开销。

总结

冒泡排序

时间复杂度：
- 最坏情况：(O(n^2))
- 最佳情况：(O(n))
- 平均情况：(O(n^2))
空间复杂度：
- (O(1))
稳定性：
- 稳定
适用性：
- 适用于顺序表（数组）
- 不适用于链表

冒泡排序在数组上的表现可以接受，尤其是在小规模或者近乎有序的数组上效率较高，但在链表上由于其结构特点并不适用。如果需要在链表上进行排序，通常选择适合链表的排序算法，如归并排序。

代码实现

#include <iostream>

// 交换函数
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// 冒泡排序算法
void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false; // 表示本趟冒泡是否发生交换的标志
        for (int j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) { // 若为逆序，交换
                swap(A[j - 1], A[j]);
                flag = true; // 发生了交换
            }
        }
        if (!flag) { // 本趟遍历后没有发生交换，说明表已经有序
            break;
        }
    }
}

// 主函数用于测试
int main() {
    int A[] = {27, 49, 38, 65, 97, 76, 49};
    int n = sizeof(A) / sizeof(A[0]);

    BubbleSort(A, n);

    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }

    return 0;
}

标志位：flag 用于标记是否在当前轮次中发生了交换。如果在某一轮次中没有发生任何交换 (if (!flag))，说明数组已经有序，提前退出排序，避免了不必要的遍历，提高了效率

二、快速排序（Quick Sort）☆

它的核心思想是分治法，通过选择一个“基准”元素，将数组分成比基准小的部分和比基准大的部分，然后递归地对这两部分进行排序。

算法流程

选择基准元素：从数组中选择一个基准元素，通常是数组中的第一个元素。
分区（Partition）：按基准元素的大小把数组分为两部分。小于基准元素的数放在左边，大于或等于的数放在右边，基准元素此时在其最终的位置。
递归排序：递归地对基准元素两侧的子序列进行排序。
合并：不需要合并步骤，因为在分区步骤中已经确定了基准元素的最终位置。
快排思想广泛适用于408专业课，只要是涉及线性表，80%以上的问题可用快排快速结束战斗。

分析

快排分析

时间复杂度

最坏情况：
- 最坏情况发生在每次选择的基准元素都是当前子数组的最小或最大元素，使得划分不均匀。例如，数组已经有序（正序或逆序）时，每次划分后只有一个子数组有效，这样递归的深度为 O(n)。在这种情况下，每次划分需要 O(n)的时间，总的时间复杂度为 O(n^2^)
平均情况：
- 平均情况下，每次选择的基准元素能够将数组大致均分为两部分。递归的深度大约为nlogn，每次划分操作需要 O(n) 的时间。因此，平均时间复杂度为 (nlogn)。
最佳情况：
- 最佳情况与平均情况类似，每次选择的基准元素能够将数组完全均分。时间复杂度同样为 O(nlogn)

空间复杂度

原地排序（In-place Sorting）：
- 快排是一种原地排序算法，主要在输入数组上进行操作，不需要额外的存储空间。
- 但是，由于递归调用栈的存在，空间复杂度取决于递归的深度。
最坏情况：
- 最坏情况与时间复杂度相同，递归深度为 O(n)，此时空间复杂度为 O(n)
平均情况：
- 平均情况下，递归深度为O(log n)，因此空间复杂度为 O(log n)

稳定性：

快速排序（QuickSort）是一种不稳定的排序算法。稳定性指的是在排序过程中，两个相等的元素在排序前后的相对位置保持不变。

为什么快速排序不稳定？

在快速排序中，选择一个基准元素后，将数组分成两部分：比基准元素小的和比基准元素大的。在这个过程中，如果存在与基准元素相等的元素，它们可能会被交换到不同的位置，从而改变它们的相对顺序。

考虑一个简单的例子：初始数组：[2，2，1]

基准元素选择第一个元素 ‘2’，进行第一次划分时：1<2，将 ‘1’ 放在左边，而第二个 ‘2’ 等于基准元素’2’，不移动，最后基准元素（也是第一个’2’）被放在最后的位置。可以看到两个2的位置没有保持原来的相对位置，所以不稳定。

如何实现稳定？

虽然原始的快速排序是不稳定的，但可以通过一些改进使其稳定：

三向切分：
- 采用三向切分的方法，将数组分为三部分：小于基准元素的部分、等于基准元素的部分、大于基准元素的部分。这样可以确保所有与基准元素相等的元素保持相对顺序不变。
记录元素原始位置：
- 在排序时，使用元组记录每个元素及其原始位置，然后按元组进行排序。最终结果可以通过元组中的位置信息恢复原始相对顺序。

代码实现

int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 第一个元素作为枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) {
            --high;
        }
        A[low] = A[high]; // 比枢轴小的元素移动到左端
        while (low < high && A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low]; // 比枢轴大的元素移动到右端
    }
    A[low] = pivot; // 枢轴元素存放到最终位置
    return low; // 返回存放枢轴的最终位置
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotIndex = Partition(A, low, high);
        QuickSort(A, low, pivotIndex - 1); // 递归排序左子序列
        QuickSort(A, pivotIndex + 1, high); // 递归排序右子序列
    }
}

int main() {
    int A[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(A) / sizeof(A[0]);
    QuickSort(A, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        std::cout << A[i] << " ";
    }
    return 0;
}

有人可能会认为：循环内部的两个循环中的判断条件low < high多余了，实则不然。

它是必要的，以确保在执行数组访问操作时不会出现索引越界的问题。

为了进一步解释这一点，让我们看看 Partition 函数在没有 low < high 判断时会发生什么：

假设我们在内部循环中删除 low < high 判断：
int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 第一个元素作为枢轴
    while (low < high) {
        while (A[high] >= pivot) {
            --high;
        }
        A[low] = A[high]; // 比枢轴小的元素移动到左端
        while (A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low]; // 比枢轴大的元素移动到右端
    }
    A[low] = pivot; // 枢轴元素存放到最终位置
    return low; // 返回存放枢轴的最终位置
}
在上述代码中，如果数组中的所有元素都等于 pivot（例如，数组为 [1, 1, 1, 1, 1]，且 pivot 也是 1），内层循环将永远不会终止，因为没有 low < high 条件来打破循环。这将导致程序进入死循环。

因此，内部循环中的 low < high 判断是必要的，以确保在适当的时候跳出循环，避免索引越界和无限循环。

优化

化思路：尽量选择可以把数据中分的枢轴元素eg：

①选头、中、尾三个位置的元素，取中间值作为枢轴元素；

②随机选一个元素作为枢轴元素

三、选择排序（Selection Sort）

基本思想：每次从未排序部分中选择最小（或最大）的元素，放到已排序部分的后面。

算法流程

一般步骤：
找到最小元素：从未排序部分选择最小的元素。
交换位置：将选中的最小元素与未排序部分的第一个元素交换位置。
更新已排序部分和未排序部分：已排序部分增加一个元素，未排序部分减少一个元素。
重复步骤2-4：重复执行以上步骤，直到整个数组有序。

分析

选择排序

时间复杂度：

不管数组的初始顺序如何，选择排序的比较次数都是固定的。第一次进行n-1趟比较，找到最小元素；第二次需要n-2趟，依此类推。总的比较次数为 (n-1) + (n-2) + … + 1 = $\frac{n(n-1)}{2}\approx O(n^2)$

空间复杂度分析：

选择排序是一种原地排序算法，它只需要常数级别的额外空间来存储临时变量（用于交换元素）。因此，选择排序的空间复杂度为 O(1)。

稳定性

选择排序是一种不稳定的排序算法：例如，数组 [2, 2, 1]，最终的排序结果为：[1, 2, 2]，第一个 2 和第二个 2 会交换位置，从而改变它们的相对顺序。

代码实现

void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 遍历未排序部分的每个元素
    for (i = 0; i < n-1; i++) {
        // 找到未排序部分的最小元素的索引
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // 将找到的最小元素与当前未排序部分的第一个元素交换
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

四、堆排序（Heap Sort）

于选择排序相同，堆排序也是选择排序。每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

适用于数组存储，使用链式存储会降低效率，对每一个节点而言，保证其左右子树均比其大或者小，排序过程中时刻保持堆的特性。排序的过程是每次拿走堆顶元素放入有序序列，然后把最后一行的最后一个元素堆到堆顶，此时堆的特性遭到破坏，下沉堆顶元素，直至恢复堆的特性，依次重复，直到堆内没有元素。
堆数据结构遇到新插入的元素放在整棵树最后一层的最后一个节点，然后依次往上浮（不用考虑从上面换下来的元素，因为原来堆结构稳定，换下来的元素依旧比下面的元素大）

大根堆>左、右

算法流程

堆排序

构建堆（Heapify）：将待排序的序列视为一个完全二叉树，并将其转换为一个堆。对于最大堆，可以通过从最后一个非叶子节点开始向前遍历，对每个节点进行堆调整操作，保证每个节点都满足堆的性质。
堆排序：通过反复从堆中取出最大（或最小）元素，并将其放到数组的末尾。每次取出元素后，需要对剩余元素进行堆调整，以保持堆的性质。

分析

时间复杂度

空间复杂度

稳定性

适用性

代码实现

五、插入排序（Insertion Sort）

在要排序的一组数中，假定前n-1个数已经排好序，将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

算法流程

初始状态：将第一个元素视为已排序序列，其余元素为未排序序列。
遍历未排序序列：从第二个元素开始，逐个将未排序序列的元素插入到已排序序列的适当位置，以保持已排序序列的有序性。
插入操作：对于每个要插入的元素，与已排序序列的元素比较，找到插入位置，并将元素插入到该位置。插入过程中，已排序序列的元素可能需要后移，为新元素腾出空间。
重复步骤2-3：重复进行插入操作，直到未排序序列为空。

分析

时间复杂度

空间复杂度

是否稳定

代码实现

优化

使用哨兵

折半插入排序

六、希尔排序（Shell Sort）

基本思想

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。增量大小会影响到排序的效率。

算法流程

选择间隔序列：选择一个递减的间隔序列，通常以 n/2、n/4、n/8… 等为步长，直到步长为 1。
对每个间隔进行插入排序：对数组中每个间隔所形成的子序列进行插入排序。
缩小间隔：不断缩小间隔，重复步骤2，直到最终间隔为 1。

分析

时间复杂度

空间复杂度

稳定性

适用性

代码实现

七、归并排序（Merge Sort）

基本思想

算法流程

图+说明

分析

时间复杂度

空间复杂度

是否稳定

代码实现

八、基数排序（Radix Sort）

基本思想

算法流程

图+说明

分析

时间复杂度

空间复杂度

是否稳定

代码实现

九、计数排序（Counting sort）

基本思想

算法流程

图+说明

分析

时间复杂度

空间复杂度

稳定性

适用性

代码实现

十、桶排序（Bucket sorting）

基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每
个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

算法流程

图+说明

分析

时间复杂度

空间复杂度

稳定性

适用性

代码实现

十一、外部排序小专题

1.外部排序原理
2.外部排序开销及应用场景
2.多路归并（提高外排效率）
3.多路平衡归并与多路归并区别
4.败者树（优化关键字对比次数）
5.置换-选择排序（优化初始构造归并段的数量）
6.最佳归并树（本质：多元哈弗曼树）

十二、根据算法的特性划分

1.根据算法是否稳定划分
2.根据内/外部排序划分
3.初始序列对算法有影响
4.是否是比较型

总结

附录

排序算法学习工具：usf算法动画演示

参考链接：

十大排序算法及其特性最全总结，以408考察特性为基准_排序算法特点-CSDN博客

【数据结构入门精讲 | 第十篇】考研408排序算法专项练习（二）-阿里云开发者社区 (aliyun.com)

loyeh

http://Lo-Y-eH.github.io/posts/564c/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 loyeh !

排序

阅读全文

鼠标还能这么用？

2024-06-11 今日学习

鼠标

阅读全文

跨域问题及解决方案

2024-05-21 web

CORS

一、冒泡排序（Bubble Sort）

算法流程

分析

总结

代码实现

二、快速排序（Quick Sort）☆

算法流程

分析

代码实现

优化

三、选择排序（Selection Sort）

算法流程

分析

代码实现

四、堆排序（Heap Sort）

算法流程

分析

代码实现

五、插入排序（Insertion Sort）

算法流程

分析

代码实现

优化

使用哨兵

折半插入排序

六、希尔排序（Shell Sort）

算法流程

分析

代码实现

七、归并排序（Merge Sort）

算法流程

分析

代码实现

八、基数排序（Radix Sort）

算法流程

分析

代码实现

九、计数排序（Counting sort）

算法流程

分析

代码实现

十、桶排序（Bucket sorting）

算法流程

分析

代码实现

十一、外部排序小专题

十二、根据算法的特性划分

总结

附录

您的肯定是我前进的动力