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

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

目录

一、冒泡排序:

二、插入排序:

三、选择排序:

四、希尔排序:

五、堆排序:

六、快速排序:

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
上一篇 10小时前
下一篇 6小时前

相关推荐

  • Java MyBatis 面试题

    谈谈MyBatis的启动过程? 加载配置文件: MyBatis的配置文件是一个XML文件,包含了数据库连接信息、映射文件的位置等配置信息。在启动过程中,MyBatis会读取并解析这个配置文件。 创建SqlSessionFactory对象: SqlSessionFactory是MyBatis的核心对象,用于创建SqlSession对象。在启动过程中,MyBat…

    未分类 2025 年 1 月 15 日
    20400
  • DataGrip破解教程,永久激活码,适用于所有操作系统的DataGrip激活

    本教程适用于DataGrip、PyCharm、DataGrip、Goland等,支持Jetbrains全家桶! 废话不多说,先给大家看一下最新DataGrip版本的破解截图,可以看到已经成功破解至2099年,激活效果非常好! 接下来,我会通过图文方式,详细讲解如何激活DataGrip至2099年。 无论你使用的是Windows、Mac还是Linux系统,无论…

    DataGrip破解教程 2025 年 4 月 18 日
    23500
  • 2025年最新IDEA激活码分享:永久破解IDEA至2099年(附详细教程)

    JetBrains全家桶通用破解指南 本教程适用于IntelliJ IDEA、PyCharm、DataGrip、GoLand等JetBrains系列开发工具,一站式解决所有激活问题! 先来看看最新IDEA版本成功破解的效果展示,有效期直达2099年,完全满足长期开发需求! 下面将详细介绍如何通过简单几步操作实现IDEA永久激活,该方法同样适用于旧版本软件,无…

    IDEA破解教程 22小时前
    2000
  • 2024 IDEA最新激活码,IDEA永久免费激活码2025-01-14 更新

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

    2025 年 1 月 14 日
    68500
  • MySQL查询语句执行流程剖析

    MySQL查询语句执行流程解析 对MySQL查询语句的执行顺序进行了梳理。 (1) FROM子句 – 最先执行 从FROM employees e开始,MySQL会率先读取FROM子句中所涉及的表的相关信息。 (2) ON条件 – 连接条件筛选 以JOIN departments d ON e.dept_id = d.id为例,此步骤是对连接起来的表的行进行…

    2025 年 6 月 21 日
    6400

发表回复

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

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

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

关注微信