有没有什么网站做泰国的东西,西安app网站开发,wordpress自定义登录地址,东莞设计企业网站的有哪些前言 本片博客主要讲解一下八大排序算法的思想和排序的代码 #x1f493; 个人主页#xff1a;普通young man-CSDN博客 ⏩ 文章专栏#xff1a;排序_普通young man的博客-CSDN博客 若有问题 评论区见#x1f4dd; #x1f389;欢迎大家点赞#x1f44d;收藏⭐文章 目录
… 前言 本片博客主要讲解一下八大排序算法的思想和排序的代码 个人主页普通young man-CSDN博客 ⏩ 文章专栏排序_普通young man的博客-CSDN博客 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录
引言
排序的概念
基本概念
常见排序算法分类
排序的运用
冒泡排序Bubble Sort
算法原理与步骤
动态演示或图解
代码实现C语言
时间复杂度与空间复杂度分析
适用场景与局限性
选择排序Selection Sort
原理与实现
性能分析
插入排序Insertion Sort
算法描述
实现
性能
时间复杂度
空间复杂度
希尔排序Shell Sort
分组插入的概念
实现
复杂度分析
归并排序Merge Sort
分治思想的应用
递归实现与迭代实现对比
1. 分解Divide
2. 解决Conquer
3. 合并Combine
非递归版本具体思路
稳定性与效率
快速排序Quick Sort
分区操作详解
递归
快速排序基本思想
“三数取中”策略的引入
前后指针法
三数取中 挖坑法
非递归
堆排序Heap Sort
计数排序Counting Sort
图解 代码
算法总结与比较
结语 在计算机科学与编程领域排序算法是基础且核心的知识点之一它们在数据处理、信息检索、数据分析等多个场景中扮演着至关重要的角色。掌握不同的排序算法不仅能提升解决问题的效率还能加深对算法原理和时间空间复杂度分析的理解。本文将深入浅出地介绍八大经典排序算法通过实例解析、算法比较及代码示例帮助读者全面掌握这些算法的精髓为日后的开发工作打下坚实的基础。 引言
排序的概念
基本概念 排序对象待排序的数据集合可以是一维数组、列表或其他数据结构中的元素。排序准则决定元素间先后顺序的规则通常基于元素的某个属性或键值如数值大小、字母顺序。稳定性如果两个相等的元素在排序前后相对位置不变则称排序算法是稳定的反之则为不稳定。时间复杂度衡量排序算法执行速度的指标描述算法执行时间与数据规模的关系常见的是最好、平均和最坏情况下的时间复杂度。空间复杂度算法在运行过程中额外占用内存的量原地排序算法的空间复杂度为O(1)表示不需要或仅需很小的额外空间。内部排序与外部排序内部排序指全部数据载入内存完成排序而外部排序适用于数据量过大无法一次性装入内存的情况需要借助外部存储进行数据交换。 常见排序算法分类
排序算法依据不同的策略和技术可以分为多种类型以下是一些经典的排序算法 比较排序通过比较元素之间的大小关系进行排序如冒泡排序、选择排序、插入排序、归并排序、快速排序等。非比较排序不直接比较元素大小而是利用元素的某种特性如数学属性进行排序如计数排序、基数排序、桶排序等这类算法通常适用于特定类型的数据集。线性时间排序在最好和平均情况下具有O(n)时间复杂度的算法如计数排序、基数排序但这类算法的适用范围有限。 排序的运用
商品 学校排名 还有很多地方都会用到我们的排序所以可以看出排序的重要性 冒泡排序Bubble Sort 算法原理与步骤 冒泡排序Bubble Sort是一种简单的排序算法其基本原理是通过重复遍历要排序的数列比较每对相邻元素的值如果它们的顺序不符合要求例如希望升序排序时前一个元素大于后一个元素就交换这两个元素的位置。这个过程就像水中的气泡一样小的元素逐渐“浮”到数列的前端大的元素则“沉”到数列的末端。下面是冒泡排序的详细步骤 动态演示或图解 代码实现C语言
// 冒泡排序函数
// 参数:
// a: 一个整型指针指向需要排序的数组
// n: 整型表示数组中的元素数量
void BubbleSort(int* a, int n) {// 外层循环控制排序的轮次共进行n轮比较for (int i 0; i n; i) {// 设置一个标记用于判断本轮循环中是否有元素交换int flag 0;// 内层循环负责每一轮的具体比较和交换操作// 注意每轮比较后最大的元素会被排到最后所以下一轮可以少比较一个元素for (int j 0; j n - 1 - i; j) {// 如果当前元素比下一个元素大就交换它们的位置if (a[j] a[j 1]) {Swap(a[j], a[j 1]); // 交换函数传入两个元素地址进行交换flag 1; // 发生了交换设置flag为1}}// 如果在某一轮遍历中没有发生任何交换说明数组已经是有序的可以提前结束排序if (flag 0) {break;}}
}// 辅助函数交换两个元素的值
// 参数:
// x, y: 整型指针分别指向需要交换的两个元素
void Swap(int* x, int* y) {int temp *x;*x *y;*y temp;
} 时间复杂度与空间复杂度分析 最好情况已排序如果输入数组已经是有序的冒泡排序只需进行一轮遍历就能发现没有交换发生此时时间复杂度为O(n)因为只需要进行一次遍历即可确认数组有序。 最坏情况逆序或完全无序当数组完全逆序或随机无序时每次遍历几乎都会发生交换需要进行完整的n*(n-1)/2次比较此时时间复杂度为O(n^2)。 平均情况考虑到所有可能的输入情况平均时间复杂度同样为O(n^2)。这是因为尽管存在最好情况但在实际应用中很难预先知道数据的排序状态故平均复杂度反映了一般情况下的性能。 适用场景与局限性
这个排序就入门的时候学习一下因为它好理解这个排序只有教学意义比较拉跨实际开发不用但是你也要知道有这个排序。 选择排序Selection Sort 原理与实现
我写的选择排序做了一点优化有一点分治的思想吧从两边向后向前找最大或最小的数逐渐缩小区间(left right) // 注意检查重叠情况如果起始位置同时也是最大值的位置// 那么在上面的交换后max位置已经被更新为min的位置无需再次寻找if (begain max) { // 这里实际上逻辑上可以省略因为下面的交换操作会自动处理这种情况max min; // 但为了清晰表达逻辑这里保留了注释的处理方式}
这个代码是这种情况 // 选择排序改进版同时找出最大和最小值进行交换适用于偶数长度数组以优化性能
void SelectSort(int* a, int n) {int begain 0, end n - 1; // 初始化起始和结束指针// 当起始指针小于结束指针时继续进行排序while (begain end) {int max begain, min begain; // 初始化最大值和最小值的索引为起始位置// 遍历未排序的部分寻找最大值和最小值for (int i begain 1; i end; i) {// 更新最大值索引if (a[i] a[max]) {max i;}// 更新最小值索引if (a[i] a[min]) {min i;}}// 交换起始位置与最小值Swap(a[begain], a[min]);// 注意检查重叠情况如果起始位置同时也是最大值的位置// 那么在上面的交换后max位置已经被更新为min的位置无需再次寻找if (begain max) { // 这里实际上逻辑上可以省略因为下面的交换操作会自动处理这种情况max min; // 但为了清晰表达逻辑这里保留了注释的处理方式}// 交换结束位置与最大值Swap(a[end], a[max]);// 缩小排序范围--end; // 移动结束指针向前begain; // 移动起始指针向后}
} 性能分析 时间复杂度无论原始数据如何选择排序都需要进行n-1轮比较每轮比较都需要遍历剩余未排序的元素因此时间复杂度为O(n^2)。空间复杂度选择排序也是原地排序除了用于交换的少量临时变量外不需要额外空间空间复杂度为O(1)。 插入排序Insertion Sort 算法描述 看这个图想必大家已经能看懂这个排序
选择排序就是选择一个比他大的值或比他小的值前插入比如1 3 5我们要把2插入进去是不是应该插入在1和3之间。 实现
// 插入排序
void InsertSort(int* a, int n) {// 遍历数组中的每个元素i从1开始因为0位置的元素默认已排序for (int i 1; i n; i) {int current a[i]; // 当前需要插入的元素int j i - 1; // 已排序部分的最后一个元素的索引// 将current与已排序部分的元素从后向前比较如果当前元素小则将已排序的元素向后移动while (j 0 a[j] current) {a[j 1] a[j]; // 向后移动元素j--;}// 将当前元素放到正确的位置a[j 1] current;}
} 性能 时间复杂度 最好情况当输入数组已经是升序或降序排列时插入排序的性能最优。在这种情况下每次比较后都不需要移动元素算法只需进行n-1次比较时间复杂度为O(n)。 最坏情况当输入数组是反序时每次插入都相当于在数组最前面插入新元素每次插入操作可能需要移动大量的元素。因此需要进行大约n(n-1)/2次比较和移动时间复杂度为O(n^2)。 平均情况对于随机排列的数组插入排序的平均时间复杂度也是O(n^2)。这是因为尽管某些情况下可以较早停止但总体上仍然需要进行大量比较和移动操作。 空间复杂度 插入排序是一种原地排序算法除了几个用于交换和临时存储的变量外不需要额外的存储空间。因此其空间复杂度为O(1)非常节省内存。 希尔排序Shell Sort 分组插入的概念 实现
这是第一种写法
// 定义ShellSort函数用于执行Shell排序算法传入一个整型数组a和数组长度n
void ShellSort(int* a, int n) {// 初始化间隔(gap)大小这里采用常见策略n/3可根据具体需求调整间隔序列int gap n / 3;// 遍历每个间隔段的起始位置j从0到gap-1控制不同的子序列for (int j 0; j gap; j) {// 对当前间隔段[j, n-gap)内的每个元素执行插入排序for (int i j; i n - gap; i gap) {// 记录待插入元素的索引及值int end i;int tmp a[end gap];// 插入排序逻辑将tmp插入到已排序的a[end...0]区间中的正确位置while (end 0) {// 若tmp小于其前面的元素a[end]则将a[end]后移if (tmp a[end]) {a[end gap] a[end];end - gap; // 缩小检查范围}else {// tmp不小于a[end]说明已找到插入位置跳出循环break;}}// 将tmp放置到最终确定的位置a[end gap] tmp;}}
}
简化的写法
/*
定义ShellSort函数用于执行Shell排序算法传入一个整型数组a和数组长度n
*/
/*
初始化间隔(gap)大小为数组长度n随后通过循环不断更新gap值
采用公式gap gap / 3 1来逐步减小间隔直至gap 1
这样的间隔序列选择是Shell排序的一种常见策略旨在平衡效率与简单性
*/
int gap n;
while (gap 1) {// 更新间隔大小gap gap / 3 1;// 针对当前的gap值对数组进行插入排序for (int j 0; j gap; j) {for (int i j; i n - gap; i gap) {// 记录待插入元素的位置及其值int end i;int tmp a[end gap];// 执行插入排序逻辑将tmp插入到正确位置while (end 0) {// 若tmp小于其前面的元素则将前元素后移if (tmp a[end]) {a[end gap] a[end];end - gap; // 缩小检查范围}else {// 找到tmp的正确插入位置跳出循环break;}}// 将tmp放置到最终确定的位置a[end gap] tmp;}}
}
// 希尔排序函数定义传入一个整型数组a和数组的元素个数n
void ShellSort(int* a, int n) {// 初始化间隔(gap)为数组的长度int gap n;// 当间隔大于1时持续执行以下过程while (gap 1) {// 更新间隔这里使用gap gap / 3 1的方式递减间隔大小gap gap / 3 1;// 遍历数组步长为当前的gap值for (int i 0; i n - gap; i) {// 记录当前位置i及其对应的值tmpint end i;int tmp a[end gap];// 插入排序逻辑将tmp插入到其应在的正确位置while (end 0) {// 如果tmp小于其前面的元素则将前面的元素向后移动if (tmp a[end]) {a[end gap] a[end]; // 向后移动元素end - gap; // 缩小检查范围}else {// tmp不小于前一个元素说明找到了插入位置退出循环break;}}// 将tmp放到最终确定的位置a[end gap] tmp;}}
}
注意这里的gap / 3 1是特定的写法你可以计算一下 这边对最后一个写法进行一个动图解释 复杂度分析 最佳情况与平均情况: 对于一些精心设计的间隔序列例如Hibbard增量序列、Sedgewick增量序列等希尔排序可以在理论上达到接近O(n log n)的平均时间复杂度。这些序列的设计目的是使得数据在排序过程中迅速趋向有序从而减少了后续插入排序步骤中的比较和交换次数。 一般情况: 对于常见的间隔序列比如每次将间隔除以某个常数如3加上一个修正值如1得到序列如n/31, n/91, ...希尔排序的平均时间复杂度大致在O(n log n)到O(n^(3/2))之间。这是由于随着排序的进行数据的无序程度逐渐降低但具体的时间复杂度会受到间隔序列选取和数据初始状态的影响。 最坏情况: 在某些不太理想的间隔序列选择下或者对于特定的输入数据希尔排序的时间复杂度可能会退化到O(n^2)。这种情况虽然不如快速排序或归并排序稳定但在实践中通过合理的间隔序列设计通常能够避免最坏情况的发生使得实际表现优于O(n^2)排序算法。 归并排序Merge Sort 分治思想的应用
学这个排序之前我们先要看一下这个博客
数据结构-二叉树-CSDN博客文章浏览阅读1.2k次点赞28次收藏28次。数据结构-堆(带图)详解-CSDN博客。https://blog.csdn.net/2302_78381559/article/details/139549132?spm1001.2014.3001.5502如果你连二叉树是什么如何实现都不知道的话抱歉这个排序可能你听不懂。 递归看一下最上面的数不是有序的将它分成两个小组再将两个小组递归成一个数一个组是不是每个小组就有序了归并然后我们将小组和小组之间比较最总就有序了 递归实现与迭代实现对比
递归
注意我们每个小组排序后最终也要拷贝一次,因为下一次归并的时候用这个排好序的数据和另一个数据比较然后再存。
// 归并排序函数参数包括原始数组a、临时数组tmp、当前子数组的起始索引left和结束索引right
void My_MergeSort(int *a, int *tmp, int left, int right) {// 基准情况如果子数组只剩一个元素或为空则无需排序直接返回if (left right) {return;}// 计算中间索引进行分割int mid (left right) / 2;// 递归地对左右两半进行归并排序// 左半边: [left, mid-1]// 右半边: [mid, right]My_MergeSort(a, tmp, left, mid);My_MergeSort(a, tmp, mid 1, right);// 初始化两个指针数组的起始和结束位置int begin1 left, end1 mid;int begin2 mid 1, end2 right;// 初始化临时数组的索引int i left;// 合并过程当两个子数组都有剩余时比较并放入临时数组tmpwhile (begin1 end1 begin2 end2) {// 如果左边数组的当前元素小于右边数组的当前元素if (a[begin1] a[begin2]) {tmp[i] a[begin1]; // 将较小的元素放入tmp并移动指针} else {tmp[i] a[begin2];}}// 处理剩余元素如果左边数组有剩余直接复制到tmpwhile (begin1 end1) {tmp[i] a[begin1];}// 处理剩余元素如果右边数组有剩余直接复制到tmpwhile (begin2 end2) {tmp[i] a[begin2];}// 将tmp中的已排序数据拷贝回原数组a// 注意这里拷贝的是[left, right]区间的数据memcpy(a left, tmp left, (right - left 1) * sizeof(int));
}
void MergeSort(int *a,int n) {int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){assert(MergeSort:malloc);}My_MergeSort(a,tmp,0,n);
}非递归 1. 分解Divide 将当前区间一分为二即找到中间位置然后对两个子区间分别进行排序。这个过程一直递归进行直到每个子区间只剩下一个元素这时可以认为单个元素的区间自然就是有序的。 2. 解决Conquer 将上一步得到的有序子区间合并成一个大的有序区间。合并的过程是这样的设立两个指针最初分别指向两个子区间的起始位置比较两个指针所指元素的大小将较小的元素放到结果数组中并移动对应指针到下一位置直到某一个子区间的所有元素都被放入结果数组中。然后将另一个子区间中剩余的元素依次放入结果数组。 3. 合并Combine 在递归实现中每次递归调用返回后都会进行合并操作将两个有序子数组合并成一个有序数组。在非递归实现中通过控制“gap”步长逐步扩大排序区间每轮迭代中对每个“gap”大小的子序列进行合并直到整个数组变为有序。 非递归版本具体思路 初始化首先创建一个与原数组相同大小的临时数组tmp用于辅助合并排序。设定间隔gap初始时gap设为1表示只考虑单个元素为一个子序列。随后每轮迭代将gap翻倍逐步扩大排序的区间直到gap大于等于数组长度的一半。多路归并在每一轮迭代中对于每个间隔为gap的子序列将其看作是两个或一个如果越界已排序的子序列然后进行合并操作。合并过程中使用双指针技巧比较并移动元素到临时数组tmp中最后再拷贝回原数组。重复随着gap的增加原本小范围有序的子序列会逐渐合并成更大范围的有序序列直至整个数组排序完成。释放资源最后释放临时数组tmp占用的内存。 // 非递归实现的归并排序函数
void MergeSort_No(int* a, int n) {// 为临时数组分配内存int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL) {assert(MergeSort:malloc); // 内存分配失败时断言}int gap 1; // 初始化间隔大小// 当间隔小于数组长度时进行排序while (gap n) {// 对每个子序列进行归并操作for (int i 0; i n; i 2 * gap) {// 定义两个子序列的边界int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// 打印当前处理的子序列范围仅用于调试printf([%d,%d][%d,%d] , begin1, end1, begin2, end2);// 检查第二个子序列是否越界if (begin2 n) {break; // 越界则跳出本次循环}if (end2 n) {end2 n - 1; // 调整第二个子序列的结束位置以避免越界}// 合并两个子序列到tmp数组中int j i;while (begin1 end1 begin2 end2) {if (a[begin1] a[begin2]) {tmp[j] a[begin1];} else {tmp[j] a[begin2];}}// 复制剩余的元素到tmp中while (begin1 end1) {tmp[j] a[begin1];}while (begin2 end2) {tmp[j] a[begin2];}// 将tmp中的有序数据拷贝回原数组amemcpy(a i, tmp i, sizeof(int) * (end2 - i 1)); // 拷贝当前处理范围的数据}printf(\n); // 换行方便观察输出gap * 2; // 增大间隔进行下一轮归并}// 释放临时数组的内存free(tmp);tmp NULL;
} 稳定性与效率 时间复杂度。归并排序的时间复杂度为O(n log n)无论是在最好、最坏还是平均情况下这一复杂度保持不变。这是因为归并排序总是将数组分成两半处理然后对这两半分别排序最后合并这个过程总共需要执行大约n log n次比较和交换操作。即使数据已经是部分有序或者完全无序归并排序的性能表现都是恒定的。 空间复杂度。归并排序需要额外的存储空间来存放临时数组用于合并操作因此其空间复杂度为O(n)。这是归并排序的一个缺点特别是在处理大量数据时可能面临较大的内存消耗问题。 快速排序Quick Sort 分区操作详解
递归 快速排序基本思想 选取基准值Pivot: 在待排序的数组中选择一个元素作为基准值。理想情况下这个基准值应该能将数组大致分为两个数量相当的部分从而最大化分治的效果。传统的快速排序随机选择一个元素作为基准但为了提高效率可以采用“三数取中法”即从数组的首元素、尾元素以及中间元素中选择中位数作为基准值这样做可以在一定程度上避免最坏情况的发生。 分区Partition: 将所有比基准值小的元素放置在基准值的左侧所有比基准值大的元素放置在右侧。这个过程称为分区操作。完成这一步骤后基准值就位于其最终排序后的位置上。 递归排序子数组: 对基准值左右两侧的子数组分别递归地执行上述两个步骤。递归的终止条件是子数组只剩下一个或没有元素这时可以认为它们已经排序好了。 “三数取中”策略的引入 为何使用三数取中: 目的是为了避免在数组已经有序或接近有序的情况下快速排序退化为O(n^2)的最差时间复杂度。通过选择中位数作为基准可以减少这种极端情况发生的概率提高算法的平均性能。 如何实施: 在每次递归调用时先找到数组的第一个元素、最后一个元素和中间元素然后比较这三个元素的值将它们中的中位数作为此次排序的基准值。 // 快速排序函数实现
void Quick_Sort(int* a, int left, int right) {// 基本情况检查如果待排序区间不足两个元素则无需排序直接返回if (left right) {return;}// 对于小数组使用插入排序以提高效率这里设定阈值为10if ((right - left 1) 10) {InsertSort(a left, right - left 1); // 从left位置开始对长度为right-left1的子数组进行插入排序}else {// 三数取中从数组的首元素、中间元素、尾元素中选取中位数作为基准值以优化快速排序性能int mid GetMid(a, left, right); // 获取中位数的索引Swap(a[mid], a[left]); // 将中位数与数组最左侧元素交换作为基准// 分区操作将基准值周围的元素分为两部分左边都小于基准右边都大于基准int begain left, end right;int key left; // 基准值的索引// 双指针法进行分区while (begain end) {// 移动end指针直到找到一个小于基准的元素while (begain end a[key] a[end]) {--end;}// 移动begain指针直到找到一个大于基准的元素while (begain end a[key] a[begain]) {begain;}// 交换找到的不满足条件的元素使得小的在左边大的在右边Swap(a[begain], a[end]);}// 交换基准值到正确位置Swap(a[key], a[begain]);key begain; // 更新基准值的位置// 对基准值左右两侧的子数组递归进行快速排序Quick_Sort(a, left, key - 1); // 排序左半部分Quick_Sort(a, key 1, right); // 排序右半部分}
}// 假设InsertSort和Swap函数已定义
// InsertSort负责对给定范围内的数组进行插入排序
// Swap用于交换两个元素的位置 前后指针法 三数取中
/找中间大小值
int GetMid(int* a, int left, int right) {int mid (right left) / 2;//left mid rightif (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if(a[left] a[right]){return right;}else{return left;}}else//left mid{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
} //指针法
// 指针法分区操作
int partsort(int* a, int left, int right) {// 三数取中选取基准值提升算法在特定数据分布下的性能int mid GetMid(a, left, right);Swap(a[mid], a[left]); // 将选中的基准值移到数组开头int prev left; // 初始化前指针标记小于基准值区域的末尾int cur prev 1; // 初始化当前指针遍历数组int key left; // 基准值的索引// 遍历数组通过交换元素将小于基准值的元素移到数组左侧while(cur right) { // 继续直到当前指针超过右边界if (a[cur] a[key]) { // 当前元素小于基准值if (prev ! cur) { // 防止自我交换Swap(a[prev], a[cur]); // 交换元素}}cur; // 移动当前指针}// 将基准值交换到其最终位置即小于基准值区域的末尾的下一个位置Swap(a[prev], a[key]);return prev; // 返回基准值的最终索引
}
// 快速排序主函数采用指针法分区
void Quick_Sort_p(int* a, int left, int right) {// 基础情况判断如果区间内元素数量小于等于1则无需排序if (left right) {return;}// 对小数组使用插入排序减少递归深度和函数调用开销if ((right - left 1) 10) {InsertSort(a left, right - left 1);} else {// 调用指针法分区函数获取基准值的最终位置int key partsort(a, left, right);// 递归地对基准值左右两侧的子数组进行排序Quick_Sort_p(a, left, key - 1); // 排序左半部分Quick_Sort_p(a, key 1, right); // 排序右半部分}
}
挖坑法 // 快速排序-挖坑版本
void Quick_Sort_hole(int* a, int left, int right) {// 基础情况如果区间内只有一个元素或为空则无需排序if (left right) {return;}// 三数取中策略选择基准值减少最坏情况概率int mid GetMid(a, left, right);Swap(a[mid], a[left]); // 将选中的基准值交换到数组开头int begin left; // 初始化左指针int end right; // 初始化右指针int hole left; // 初始化坑的位置即基准值的初始位置int key a[hole]; // 存储基准值// 双指针法进行挖坑填坑操作while (begin end) {// 从右向左找第一个小于基准值的元素while (begin end key a[end]) {end--;}// 找到后将该元素填入坑中a[hole] a[end];hole end; // 更新坑的位置// 从左向右找第一个大于基准值的元素while (begin end key a[begin]) {begin;}// 找到后再次将该元素填入坑中a[hole] a[begin];hole begin; // 更新坑的位置}// 基准值归位此时begin end即为基准值的最终位置a[hole] key;// 对基准值左右两侧的子数组递归执行快速排序Quick_Sort_hole(a, left, hole - 1); // 排序左半部分Quick_Sort_hole(a, hole 1, right); // 排序右半部分
} 快速排序Quick Sort- 挖坑版本 的核心思想依然遵循快速排序的基本原则即分而治之的策略但它的具体实现细节略有不同主要体现在如何管理“基准值pivot”的选择与定位上。以下是该算法思想的概括 选择基准值首先使用“三数取中”策略选取基准值即从数组的首元素、中间元素和尾元素中选取中位数作为基准这样做可以优化在数组已经部分有序的情况下的性能减少最坏情况发生的概率。 挖坑法与常规的快速排序直接交换元素不同挖坑法通过在数组中为基准值“挖一个坑”然后用符合条件的元素“填坑”。算法维护两个指针一个从左向右扫描另一个从右向左扫描寻找需要交换的元素。当左指针指向的元素大于基准值且右指针指向的元素小于基准值时交换这两个元素实际上是将右指针对应的元素“填入”左指针所代表的“坑”中反之亦然。这一过程不断进行直至左右指针相遇此时坑的位置即为基准值的最终位置。 分治基准值到位后数组被分为两部分一部分是所有小于基准值的元素另一部分是所有大于基准值的元素。然后对这两部分分别递归地应用同样的挖坑法进行排序。递归的终止条件是子数组的左右边界相遇或交叉这时子数组只有一个或零个元素自然有序。 效率与稳定性挖坑法的快速排序在每次迭代中减少了不必要的元素交换有时可以略微提高排序效率尤其是在交换操作成本较高的环境下。然而快速排序算法整体上是不稳定的排序算法因为相等的元素可能会因为排序过程中的交换而改变它们的原始相对位置。 非递归
非递归需要用到栈数据结构-栈(带图)-CSDN博客文章浏览阅读857次点赞54次收藏42次。栈Stack是一种基本的数据结构其特点是只允许在同一端进行插入和删除操作这一端被称为栈顶。遵循后进先出Last In, First Out, LIFO原则即最后存入栈中的元素最先被取出。形象地讲栈就像是生活中堆放盘子的架子我们总是把新的盘子放在最上面而需要拿盘子时也是从最上面开始拿。https://blog.csdn.net/2302_78381559/article/details/138810121
其实非递归也是一种分治的思想看图 左边入栈出栈完毕之后出7 5 的时候就对右边排序这边主要也要看一下partsort函数也就是上面的指针法 //快速排序(非递归)
void Quick_Sort_No(int* a, int left, int right) {Stack s1;StackInit(s1);//入栈区间StackPush(s1, right);StackPush(s1, left);while (!StackEmpty(s1))//直到栈为空循环结束{int begin StackTop(s1);StackPop(s1);int end StackTop(s1);StackPop(s1);int key partsort(a, begin, end);//走一次排序找到key(分治思想)//[begin,key-1] key [key1,end]if (key 1 end) {StackPush(s1, end);StackPush(s1, key1);}if (begin key - 1){StackPush(s1, key - 1);StackPush(s1,begin);}}StackDestroy(s1);
}堆排序Heap Sort 这个排序我专门有一个博客中讲过
数据结构-堆(带图)详解-CSDN博客文章浏览阅读1.1k次点赞35次收藏31次。节点二叉树的基本组成单位每个节点可以包含一个数据元素以及指向其左右子节点的引用。根节点树的顶端节点没有父节点。叶子节点没有子节点的节点。度节点的子节点数量二叉树中节点的度不超过2。父子关系与兄弟关系与一般树相同每个节点除了根有唯一的父节点同一父节点的子节点互为兄弟。https://blog.csdn.net/2302_78381559/article/details/139307800?spm1001.2014.3001.5502 计数排序Counting Sort 图解 大概的逻辑就是这样反正通过映射到来排序这个思想其实有点底层的想法 代码
// 计数排序函数
void Countsort(int* a, int n) {// 初始化最大值和最小值为数组的第一个元素int max a[0], min a[0];// 找最大值和最小值遍历数组更新最大值和最小值for (int i 0; i n; i) {if (max a[i]) {max a[i]; // 更新最大值}if (min a[i]) {min a[i]; // 更新最小值}}// 根据最大值和最小值计算数据范围并初始化计数数组int range (max - min) 1; // 数据范围int* count (int*)calloc(range, sizeof(int)); // 分配计数数组内存初始化为0if (count NULL) {assert(Countsort: calloc failed); // 内存分配失败时断言}// 计数遍历原数组统计每个元素的出现次数for (int i 0; i n; i) {count[a[i] - min]; // 将a[i]映射到计数数组的索引并在此索引上累加计数}// 排序根据计数数组重构原数组int j 0; // 用于记录原数组的当前位置for (int i 0; i range; i) {// 当前索引i在计数数组中表示的数值是i min// 使用计数数组的值进行多次赋值实现排序while (count[i]-- 0) {a[j] i min; // 将数值i min放回原数组中同时移动原数组的写入指针}}// 释放计数数组分配的内存free(count);
}
注意
计数排序适用于整数排序且数据范围不能太大否则计数数组将占用大量内存。只针对对整数对于非整数或者数据范围极大的情况计数排序可能不是最佳选择。计数排序是稳定的排序算法即相等的元素的相对顺序不会改变。 算法总结与比较 源代码
fun.h
#pragma once
#includestdio.h
#includetime.h
#includestdlib.h
#includeassert.h//接口
// 测试排序速度
void TestOP();//输出
void My_Print(int* p, int n);
//插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);// 冒泡排序
//void BubbleSort(int* a, int n);//快速排序
//hoare版
void Quick_Sort(int* a, int left, int right);
//填坑法
void Quick_Sort_hole(int* a, int left, int right);
//指针法
void Quick_Sort_p(int* a, int left, int right);
//非递归
void Quick_Sort_No(int* a, int left, int right);//归并排序
void MergeSort(int* a, int n);
//归并排序(非递归)
void MergeSort_No(int* a, int n);//计数排序
void Countsort(int* a, int n);
text.c
#define _CRT_SECURE_NO_WARNINGS 1
#includefun.hint main() {//int arr[] { 5,6,8,7,1,0,4,9 };int arr[] {5,2,3,4,6,9,8 ,10,20,55,11};int sz sizeof(arr) / sizeof(arr[0]);//TestOP();//InsertSort(arr, sz);/*BubbleSort(arr, sz);My_Print(arr, sz);*//*HeapSort(arr,sz);My_Print(arr, sz);*//*ShellSort(arr,sz);My_Print(arr, sz);*///My_Print(arr, sz);//SelectSort(arr, sz);//My_Print(arr, sz);//TestOP();//Quick_Sort_hole(arr, 0, sz - 1);/*Quick_Sort(arr,0,sz-1);My_Print(arr, sz);*///Quick_Sort_p(arr, 0, sz - 1);//Quick_Sort_No(arr, 0, sz - 1);//MergeSort_No(arr,sz);//My_Print(arr,sz);Countsort(arr, sz);My_Print(arr, sz);
}
fun.c
#define _CRT_SECURE_NO_WARNINGS 1
#includefun.h
#includefun2.h
//交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}//打印
void My_Print(int* p, int n) {for (int i 0; i n; i){printf(%d , p[i]);}printf(\n);
}//比较时间长
void TestOP() {// 时间戳开空间srand((unsigned int)time(0));const int n 100000;int* a1 (int*)malloc(sizeof(int) * n);int* a2 (int*)malloc(sizeof(int) * n);int* a3 (int*)malloc(sizeof(int) * n);int* a4 (int*)malloc(sizeof(int) * n);int* a5 (int*)malloc(sizeof(int) * n);// 在每一个下标生成随机数for (int i 0; i n; i) {a1[i] rand()i;a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];}int begin1 clock();//InsertSort(a1, n);int end1 clock();int begin2 clock();// ShellSort(a2, n);int end2 clock();int begin3 clock();// //SelectSort(a3, n);Quick_Sort_hole(a3, 0, n - 1);int end3 clock();int begin4 clock();HeapSort(a4, n);int end4 clock();int begin5 clock();Quick_Sort(a5,0,n-1);int end5 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2); printf(Quick_Sort_hole:%d\n, end3 - begin3); printf(HeapSort:%d\n, end4 - begin4); printf(Quick_Sort:%d\n, end5 - begin5);// // 释放free(a1);free(a2);free(a3);free(a4);free(a5);
}// 插入排序
void InsertSort(int* a, int n) {//[0,end]for (int i 0; i n - 1; i){int end i;//存储目标int tmp a[end 1];while (end 0){//如果end这个位置的值大于tmp就向后覆盖if (a[end] tmp) {a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}}
// 希尔排序
void ShellSort(int* a, int n) {//预排序/*int gap n/3;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]) {a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}*//* int gap n;while (gap 1){gap gap / 3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]) {a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}*/int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]) {a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}// 选择排序
void SelectSort(int* a, int n) {int begain 0 ,end n - 1;while (begain end){int max begain, min begain;for (int i begain1; i end; i){if (a[i] a[max]) {max i;}if (a[i] a[min]){min i;}}Swap(a[begain],a[min]);//重叠//如果begin max - begin这个位置就是最大的数这个数被min的位置换走了所以只需要将min的下标赋值if (begain max) {max min;}Swap(a[end], a[max]);--end;begain;}//标准/* for (int i 0; i n-1; i){int tmp i;for (int j i1; j n-1; j){if (a[tmp] a[j])tmp j;}Swap(a[i], a[tmp]);}*/}// 堆排序
void AdjustDwon(int* a, int n, int parent) {int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child])child;if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n) {//建堆(大堆)for (int i n/2-1; i 0 ; i--){AdjustDwon(a,n,i);}//排序int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDwon(a, end, 0);end--;}
}// 冒泡排序
//void BubbleSort(int* a, int n) {
//
// for (int i 0; i n; i)
// {
// int flag 0;
// for (int j 0; j n - 1 - i; j) {
//
// if (a[j] a[j 1])
// {
// Swap(a[j], a[j 1]);
// flag 1;
// }
//
// }
// if (flag 0)
// {
// break;
// }
// }
//}//找中间大小值
int GetMid(int* a, int left, int right) {int mid (right left) / 2;//left mid rightif (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if(a[left] a[right]){return right;}else{return left;}}else//left mid{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}//快速排序
void Quick_Sort(int* a, int left,int right) {//判断左右等于空或者左右就一个值if (left right){return;}if ((right-left1) 10) {InsertSort(aleft, right - left 1);}else{//三数取中int mid GetMid(a, left, right);Swap(a[mid], a[left]);//和左值交换int begain left, end right;int key left;//两边比较(分治思想)while (begain end){while (begain end a[key] a[end]){--end;}while (begain end a[key] a[begain]){begain;}//交换Swap(a[begain], a[end]);}//交换key,和相遇的值Swap(a[key], a[begain]);key begain;//进行递归//[begain,key-1]key[key1,end]Quick_Sort(a, left, key - 1);Quick_Sort(a, key 1, right);}}//快排(挖hole版本)
void Quick_Sort_hole(int* a, int left, int right) {if (left right){return;}//三数取中int mid GetMid(a, left, right);Swap(a[mid], a[left]);//和左值交换int begin left, end right;int hole left;//坑从最左边开始int key a[hole];//存储坑的值while (begin end) {while (begin end key a[end]) {end--;}//填坑a[hole] a[end];//更新坑位hole end;//--------------------while (begin end key a[begin]) {begin;}//填坑a[hole] a[begin];//更新坑位hole begin;}a[hole] key;//最后坑位填充存储的值//递归左右Quick_Sort_hole(a, left, hole - 1);Quick_Sort_hole(a, hole1, right);}//指针法
int partsort(int* a, int left, int right) {//三数取中int mid GetMid(a, left, right);Swap(a[mid],a[left]);int prev left;int cur prev 1;int key left;//利用循环找keywhile(cur right)//cur指针大于right边界跳出循环{if (a[cur] a[key] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[key]);return prev;
}
void Quick_Sort_p(int* a, int left, int right) {//判断左右等于空或者左右就一个值if (left right){return;}if ((right - left 1) 10) {InsertSort(a left, right - left 1);}else{int key partsort(a,left,right);//进行递归//[begain,key-1]key[key1,end]Quick_Sort(a, left, key - 1);Quick_Sort(a, key 1, right);}}//快速排序(非递归)void Quick_Sort_No(int* a, int left, int right) {Stack s1;StackInit(s1);//入栈区间StackPush(s1, right);StackPush(s1, left);while (!StackEmpty(s1))//直到栈为空循环结束{int begin StackTop(s1);StackPop(s1);int end StackTop(s1);StackPop(s1);int key partsort(a, begin, end);//走一次排序找到key(分治思想)//[begin,key-1] key [key1,end]if (key 1 end) {StackPush(s1, end);StackPush(s1, key1);}if (begin key - 1){StackPush(s1, key - 1);StackPush(s1,begin);}}StackDestroy(s1);}#includestring.h
//归并排序(递归)
//思路分治思想
void My_MergeSort(int *a,int *tmp,int left,int right) {if (left right){return;}//二分数据int mid (left right) / 2;//[left,mid-1][mid,right] -- 分治My_MergeSort(a, tmp,left,mid);My_MergeSort(a, tmp,mid1,right);//存储两边int begin1 left, end1 mid;int begin2 mid 1, end2 right;int i left;//归并while (begin1 end1 begin2 end2){//如果... if (a[begin1] a[begin2]) {tmp[i] a[begin1];//下标不断变化}else{tmp[i] a[begin2];}}//剩余数据while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a left, tmp left, (right - left 1) * sizeof(int));//没归并一次拷贝一次}void MergeSort(int *a,int n) {int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){assert(MergeSort:malloc);}My_MergeSort(a,tmp,0,n);
}//归并排序(非递归)
void MergeSort_No(int* a, int n) {//开辟一个临时空间int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){assert(MergeSort:malloc);}int gap 1;//定义gap确定间隔while (gap n){//单趟for (int i 0; i n; i 2 * gap) {//分治[begin,igap-1][igap,i(gap*2)-1]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//测试printf([%d,%d][%d,%d] , begin1, end1, begin2, end2);//判断越界if (begin2 n){break;}if (end2 n){end2 n - 1;}//比较两个区间int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]) {tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//将剩余的数也进入while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//边归并边拷贝(其实可以想一下为什么这样每拷贝一次a都会变化这样才能真正的排序)memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//(end2-i)1 这是最后一个位置1下标从0开始}printf(\n);gap * 2;}//销毁free(tmp);tmp NULL;}//计数排序
void Countsort(int* a,int n) {//找最大值/最小值int max a[0], min a[0];for (int i 0; i n; i){if (max a[i]) {max a[i];}if (min a[i]){min a[i];}}//计数int range (max - min)1;int* count (int*)calloc(range, sizeof(int));if (count NULL){assert(Countsort:calloc);}for (int i 0; i n; i){count[a[i] - min]; // a中的数字减去最小值就可以的到这个数字顺序的下标}//排序int j 0;for (int i 0; i range; i){while (count[i]--) {a[j] i min;//用i min就的到原来的数字将这些存入a数组}}//释放free(count);
} 结语 深入探讨了八大排序算法——冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、以及我们刚刚详析的计数排序之后我们不仅掌握了一系列解决排序问题的有效策略更深刻理解了算法设计背后的逻辑与权衡。每种算法如同八音盒中的音符各有其独特的旋律与应用场景它们共同编织了计算机科学领域中关于“排序”这一基本问题的华丽乐章。
