十种经典排序算法深度解读

十种经典排序算法深入剖析

目录

一、冒泡排序:

二、插入排序:

三、选择排序:

四、希尔排序:

五、堆排序:

六、快速排序:

6.1 挖坑法:

6.2 左右指针法

6.3 前后指针法:

七、归并排序:

八、桶排序:

九、计数排序:

9.1 绝对映射:

9.2 相对映射:

十、基数排序:

一、冒泡排序:

1、核心思路:

通过对待排序的序列进行从前往后的遍历(从下标较小的元素起始),依次对相邻的两个元素的值进行两两比较,若发现前一个数大于后一个数则进行交换操作,使得值较大的元素逐步从前部向尾部移动,恰似水底的气泡缓缓向上升腾。

2、实例讲解与代码示例:

以数组[3, 9, -1, 10, 20]为例进行说明:

第一轮排序:
- 3与9比较,无需交换;
- 9与-1比较,因9大于-1,两者交换,序列变为[3, -1, 9, 10, 20];
- 9与10比较,无需交换;
- 10与20比较,无需交换。第一轮结束后,最大的元素20被固定在末尾位置。

第二轮排序:
由于20已处于正确位置,只需对前4个元素进行排序:
- -1与3比较,因3大于-1,两者交换,序列变为[-1, 3, 9, 10, 20];
- 3与9比较,无需交换;
- 9与10比较,无需交换。第二轮结束后,第二大的元素10被固定在倒数第二个位置。

第三轮排序:
此时10和20已各就其位,只需对前3个元素进行排序:
- -1与3比较,无需交换;
- 3与9比较,无需交换。第三轮结束后,第三大的元素9被固定在相应位置。

第四轮排序:
仅需对前两个元素进行排序:
- -1与3比较,无需交换。第四轮结束后,所有元素排序完成。

小结:

设待排序元素的总数为n,那么排序过程具有以下特点:
1. 总共需要进行(n-1)轮排序,即(n-1)次大循环;
2. 每一轮排序中比较的次数逐轮递减;
3. 若在某一趟排序中,未发生任何一次交换操作,则可提前终止冒泡排序;
4. 时间复杂度为O(N²),在序列有序时,由于有exchange变量进行优化,执行速度较快;但在序列无序时,效率较低。

#include<stdio.h>
void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void BubbleSort(int* a, int n) {
    int end = n - 1; // 避免越界
    while (end) {
        int exchange = 0; // 用于优化,若未发生交换则提前结束循环
        for (int i = 0; i < end; i++) {
            if (a[i] < a[i + 1]) {
                swap(&a[i], &a[i + 1]);
                exchange++;
            }
        }
        if (exchange == 0) break;
        end--;
    }
}

冒泡排序动态演示

二、插入排序:

1、思路阐述:

假定待排序的元素中,前n-1个元素已然有序,现在将第n个元素插入到前面已经排好序的序列之中,使得前n个元素也呈现有序状态。按照这样的方式对所有元素依次进行插入操作,直至整个序列完全有序。需要注意的是,我们初始并不能确定待排元素中哪一部分是有序的,所以一开始默认第一个元素是有序的,然后依次将其后的元素插入到这个有序序列当中,最终使整个序列有序。

2、示例说明:

如同插入扑克牌的过程,当摸到数字7时,会自然而然地与前面已有的牌面数字进行比较,如果遇到比7大的牌,就将其向后挪动(通过交换操作),然后在第一个比7小的牌的后面插入7。

void InsertSort(int* a, int n) {
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) { // 若当前元素小于前一个元素,则进入插入流程
            int tmp = a[i];
            int j;
            for (j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j + 1] = a[j]; // 将较大的元素后移
            }
            a[j + 1] = tmp; // 将当前元素插入到合适的位置
        }
    }
}

插入排序动态演示
插入排序动态效果

三、选择排序:

思路解析:

  1. 在内层循环中,找出当前未排序部分的最小值的下标,然后将其与未排序部分的第一个元素进行交换。重复进行寻找最小值和交换的操作。
  2. 实际上,我们可以在一趟排序中同时找出一个最大值和一个最小值,分别将它们放置在序列的开头和末尾位置,这样能使选择排序的效率提高一倍。不过,其时间复杂度依然为O(N²),效率相对不高。
void SelectSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) { // 当处理到最后一个元素时,无需再进行交换操作
        int min = i;
        for (int j = i; j < n; j++) {
            if (a[j] < a[min]) {
                min = j; // 记录最小值的下标
            }
        }
        swap(&a[i], &a[min]); // 交换当前元素与最小值元素
    }
}

选择排序动态演示

四、希尔排序:

思路解读:

  1. 希尔排序是插入排序的优化版本,存在一个预排序的阶段。通过该阶段,使得较大的数能够快速地移动到序列的后面,较小的数能够快速地移动到序列的前面。
  2. 其目的是让待排序的序列尽可能接近有序状态,之后再对这个接近有序的序列进行一次插入排序。
  3. 本质上,希尔排序相当于将直接插入排序中的步长1替换成了gap。
void ShellSort(int* a, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; // 动态调整步长
        for (int i = gap; i < n; i++) {
            if (a[i] < a[i - gap]) {
                int tmp = a[i];
                int j;
                for (j = i - gap; j >= 0 && a[j] > tmp; j -= gap) { // 按照步长进行移动
                    a[j + gap] = a[j];
                }
                a[j + gap] = tmp;
            }
        }
    }
}

希尔排序动态演示

五、堆排序:

堆的基本认知:

  1. 堆的定义:
  2. 大堆:父节点的值大于子节点的值;
  3. 小堆:父节点的值小于子节点的值(这里的父节点和子节点是基于二叉树结构而言的)。
  4. 堆的物理与逻辑结构:
  5. 物理结构:采用数组来存储;
  6. 逻辑结构:是一棵完全二叉树。

堆排序的步骤:

堆排序包含建堆(通过向下调整算法结合循环实现)和堆排序(通过交换操作结合向下调整算法实现)两个主要阶段。
1. 建堆:要构建大堆时,将堆顶元素与最后一个元素进行交换,然后减小堆的有效大小,这样可以保证堆的结构不被破坏。
2. 向下调整算法:比较当前父节点的两个子节点的大小,选出较大的子节点,若子节点的值大于父节点,则进行交换操作。然后将父节点指针指向子节点,子节点指针指向下一层子节点,如此循环,向下调整算法一共会进行h-1次调整(h为堆的高度)。

void AdjustDown(int* a, int n, int root) {
    int parent = root;
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child] < a[child + 1]) {
            child++; // 指向较大的子节点
        }
        if (a[child] > a[parent]) {
            swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}
void HeapSort(int* arr, int n) {
    // 构建大堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) { // 从最后一个非叶子节点开始调整
        AdjustDown(arr, n, i);
    }
    // 排序过程
    for (int i = n; i > 1; i--) {
        swap(&arr[0], &arr[i - 1]);
        AdjustDown(arr, i - 1, 0);
    }
}

堆排序动态演示

六、快速排序:

快速排序包含三种常见的实现方法:挖坑法、左右指针法和前后指针法。

6.1 挖坑法:

  1. 核心思想:选取第一个元素作为key值,通过调整key值的位置,使得key值左边的所有元素都小于key值,右边的所有元素都大于key值。
  2. 具体步骤:
  3. 选定第一个元素作为key值,并将其存储到key变量中,此时该元素的位置形成一个“坑”;
  4. 定义left和right两个指针,left从左向右移动(当遇到大于key值的元素时停下),right从右向左移动(当遇到小于key值的元素时停下)。若从最左边开始挖坑,则需要先移动right指针;若从最右边开始挖坑,则需要先移动left指针;
  5. 将right指针所指的较小元素填入坑中,然后将left指针所指的元素填入right指针所指的位置,形成新的坑;
  6. 重复上述操作,直到left和right指针相遇,此时将key值填入相遇位置,完成一趟排序;
  7. 采用分治思想,将序列分为left到pivot-1和pivot+1到right两个部分,分别对这两个子序列进行递归排序。
void QuickSort(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    int begin = left, end = right;
    int key = a[begin]; // 确定key值并挖坑
    int pivot = begin;
    while (begin < end) {
        // 先从右边找小于key的元素
        while (begin < end && a[end] >= key) {
            end--;
        }
        a[pivot] = a[end]; // 将较小元素填入坑
        pivot = end;
        // 再从左边找大于key的元素
        while (begin < end && a[begin] <= key) {
            begin++;
        }
        a[pivot] = a[begin]; // 将较大元素填入坑
        pivot = begin;
    }
    a[pivot] = key; // 将key值放入正确位置
    QuickSort(a, left, pivot - 1); // 递归处理左子序列
    QuickSort(a, pivot + 1, right); // 递归处理右子序列
}

挖坑法快速排序动态演示

6.2 左右指针法:

  1. 思路流程:
  2. 选取第一个元素作为key值;
  3. 定义begin和end两个指针,begin从左向右移动,end从右向左移动。若选取最左边的元素作为key值,则需要先移动end指针;若选取最右边的元素作为key值,则需要先移动begin指针(这是为了保证最后相遇位置能够正确与key值交换);
  4. 在移动过程中,当end指针遇到小于key值的元素时停下,begin指针遇到大于key值的元素时停下,然后交换begin和end指针所指的元素;
  5. 重复上述操作,直到begin和end指针相遇,此时交换相遇位置与key值的元素;
  6. 采用分治思想,对key值左右的子序列分别进行递归排序。
void QuickSort(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    int begin = left, end = right;
    int key = begin; // 以左边元素作为key值
    while (begin < end) {
        while (begin < end && a[end] >= a[key]) {
            end--;
        }
        while (begin < end && a[begin] <= a[key]) {
            begin++;
        }
        Swap(&a[begin], &a[end]); // 交换元素
    }
    Swap(&a[begin], &a[key]); // 将key值放到正确位置
    QuickSort(a, left, begin - 1); // 递归处理左子序列
    QuickSort(a, begin + 1, right); // 递归处理右子序列
}

左右指针法快速排序动态演示

6.3 前后指针法:

  1. 思路概述:
  2. 选取第一个元素作为key值;
  3. 初始化prev指针指向序列起始位置,cur指针指向prev+1的位置;
  4. 让cur指针一直向前移动,当遇到小于a[key]的元素时,将prev指针向前移动一格(此时prev指针所指元素一定大于a[key]),然后交换a[cur]和a[prev]的值;
  5. 经过一趟排序后,key值左边的元素都小于key值,右边的元素都大于key值;
  6. 采用分治思想,对key值左右的子序列分别进行递归排序。
void QuickSort(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = GetMidIndex(a, left, right); // 三数取中优化
    swap(&a[left], &a[index]);
    int key = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        if (a[cur] < a[key]) {
            prev++;
            swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    swap(&a[prev], &a[key]);
    QuickSort(a, left, prev - 1); // 递归处理左子序列
    QuickSort(a, prev + 1, right); // 递归处理右子序列
}
// 三数取中函数
int GetMidIndex(int* a, int left, int right) {
    int mid = (left + right) / 2;
    if (a[mid] >= a[left]) {
        if (a[mid] <= a[right]) {
            return mid;
        } else {
            if (a[right] >= a[left]) {
                return right;
            } else {
                return left;
            }
        }
    } else {
        if (a[right] >= a[left]) {
            return left;
        } else {
            if (a[right] >= a[mid]) {
                return right;
            } else {
                return mid;
            }
        }
    }
}

文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12852.html

(0)
LomuLomu
上一篇 2025 年 7 月 10 日
下一篇 2025 年 7 月 10 日

相关推荐

  • 锚点效应在独立站价格优化中的实践-《认知偏差指南》

    锚点效应在独立站价格优化中的实践-《认知偏差指南》 优化前后的价格呈现对比 原始促销价格展示方式 改进后的价格展示方案 理解锚点效应的本质 人们在做出判断时,往往会过度依赖最初获得的信息(即锚点),即便这些信息与当前决策并无直接关联。在决策过程中,人们习惯性地以这些初始信息为参照,迅速形成判断。 — 《认知偏差指南》 实施优化的心路历程 最初在搭建的几个独…

    2025 年 5 月 13 日
    14300
  • 2025年最新DataGrip激活码及永久破解方法(支持2099年)

    本教程适用于JetBrains系列开发工具,包含DataGrip、PyCharm、IDEA等所有产品! 先展示最新DataGrip版本成功破解的截图,可以看到已经完美激活到2099年,运行非常稳定! 下面通过详细的图文步骤,教你如何永久激活DataGrip至2099年。 这个方法同样适用于旧版本DataGrip! 支持Windows/Mac/Linux全平台…

    DataGrip激活码 2025 年 8 月 28 日
    9100
  • 2024 GoLand最新激活码,GoLand永久免费激活码2025-02-12 更新

    GoLand 2024最新激活码 以下是最新的GoLand激活码,更新时间:2025-02-12 🔑 激活码使用说明 1️⃣ 复制下方激活码 2️⃣ 打开 GoLand 软件 3️⃣ 在菜单栏中选择 Help -> Register 4️⃣ 选择 Activation Code 5️⃣ 粘贴激活码,点击 Activate ⚠️ 必看!必看! 🔥 获取最新激活…

    2025 年 2 月 12 日
    62000
  • 🚀 2025最新PyCharm永久激活码分享|100%破解成功教程(支持2099年)

    🔥 本教程适用于Jetbrains全家桶(IDEA/PyCharm/DataGrip/Goland等),亲测有效! 先给大家看看最新PyCharm版本破解成果,直接续命到2099年!💪 下面将用最详细的图文教程,手把手教你激活PyCharm至2099年✨ 🌟 适用所有情况:- 跨平台支持(Windows/Mac/Linux)- 兼容所有历史版本- 成功率10…

    PyCharm激活码 2025 年 6 月 17 日
    22400
  • CLion激活失败可以重置吗?附激活回退教程!

    免责声明:以下激活补丁与授权码均源自网络公开分享,仅限个人学习研究,请于 24 小时内删除,并支持购买官方正版! CLion 是 JetBrains 出品的多平台 C/C++ IDE,支持 Windows、macOS 与 Linux。下文将手把手演示如何借助第三方补丁,一键解锁全部高级特性,实现“永久”授权。 无论您当前系统或版本号为何,下方步骤均通用。 激…

    2025 年 9 月 19 日
    3500

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信