地图网站怎么做,怎样网络营销推广,杭州优质网站建设,设计师网址导航sdc前言 1#xff0c;数据结构排序篇章是一个大的工程#xff0c;这里是一个总结篇章#xff0c;配备动图和过程详解#xff0c;从难到易逐步解析。 2#xff0c;这里我们详细分析几个具备教学意义和实际使用意义的排序#xff1a; 冒泡排序#xff0c;选择排序#xff0c… 前言 1数据结构排序篇章是一个大的工程这里是一个总结篇章配备动图和过程详解从难到易逐步解析。 2这里我们详细分析几个具备教学意义和实际使用意义的排序 冒泡排序选择排序插入排序希尔排序快排递归霍尔版本快排递归前后指针版本快排非递归版本堆排序解决top_k问题归并排序递归归并排序非递归计数排序 3这里我想说一下学习排序之前需要了解一些相关的知识 复杂度目的是了解算法的时间复杂度复杂度精讲时间空间-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138073981栈和队列目的是在排序非递归实现里面我们需要用到栈比如速排的非递归实现数据结构-栈和队列(速通版本)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138715165二叉树目的是在排序计算里面递归的解决方式是比较常用的方式二叉树正好是用递归来完成的可以辅助我们深入的了解一下排序的递归数据结构-二叉树系统性学习四万字精讲拿捏-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138799868 4当然最后一点就是这些知识也可以不直接涉及到如果你的时间比较紧张的话只是理解起来相对而言需要一点难度这些知识不是必须的。需要知道的是这些知识可以帮助你深入理解排序的逻辑。 5对于排序的学习很重要的一点就是每次实现的时候我们往往需要先实现单趟排序的实现之后再实现多趟的完结这个是很重要的思路 6这里的代码观看尤其是对于排序代码的实现 先看内循环因为内循环是单趟实现再看外循环因为外循环是全部实现逻辑。这里一定不能搞错顺序不然数据结构排序篇章很容易就无法看懂。并且单趟实现往往重于多趟实现因为多趟实现往往是单趟循环的循环和重复 冒泡排序 前言 冒泡排序具备很强的教学意义但是没有什么实践意义这里作为第一个讲解的排序目的是从简单开始讲解方便理解 冒泡排序gif 冒泡排序单趟实现 冒泡排序一次只解决一个数字交换一个数字之后开始交换第二个数字 那么多趟实现就直接for循环多趟实现就可以了 冒泡排序多趟实现逻辑 举例2无法理解可以先不看举例2这里是参照组 假设初始数组 [4, 2, 9, 1, 5] 第一轮后 [2, 4, 9, 1, 5] (9移到末尾) 第二轮后 [2, 4, 1, 5, 9] (9和5移到末尾) 第三轮后 [2, 1, 4, 5, 9] (9、5和4移到末尾) 第四轮后 [1, 2, 4, 5, 9] (9、5、4和2移到末尾) 第五轮后 [1, 2, 4, 5, 9] (数组已经排序完成) 冒泡排序注意事项 单趟循环需要注意事项 这里如果传参如果传递是是n那么单趟实现的时候我们不能循环n次数只能循环n-1次数因为 多趟循环需要注意事项 冒泡排序的交换逻辑 冒泡排序代码实现 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){for (int j 0; j n - i - 1; j){if (a[j] a[j 1]){Swap(a[j], a[j 1]);}}}
} 解释 交换函数Swap 函数原型void Swap(int* p1, int* p2)参数p1 和 p2 是指向两个整数的指针。功能交换两个指针所指向的整数的值。实现首先使用一个临时变量 tmp 存储 p1 指向的值。然后将 p2 指向的值赋给 p1 指向的位置最后将临时变量 tmp原来 p1 的值赋给 p2 指向的位置。 冒泡排序BubbleSort 函数原型void BubbleSort(int* a, int n)参数a 是指向整数数组的指针n 是数组中元素的数量。功能对数组 a 进行原地排序使数组中的元素按照非递减顺序排列。实现冒泡排序通过重复遍历要排序的数组比较相邻元素如果它们的顺序错误就把它们交换过来。遍历数组的工作是在外层循环中完成的内层循环负责实际的比较和交换。交换函数就是一个交换函数因为后面我还需要调用所以这里我单独拿出来。 冒泡排序时间复杂度计算 冒泡排序的时间复杂度计算基于算法执行的比较和交换操作的次数。下面是冒泡排序的时间复杂度分析 最佳情况当数组已经完全有序时冒泡排序只需要进行一次遍历即可确定数组已经有序不需要进行任何交换。在这种情况下时间复杂度是 O(n)其中 n 是数组的长度。 平均情况和最坏情况在平均情况和最坏情况下冒泡排序需要进行 n-1 次遍历每次遍历中进行的比较次数依次减少。具体来说 第一次遍历最多进行 n-1 次比较。第二次遍历最多进行 n-2 次比较。...最后一次遍历进行 1 次比较。总的比较次数可以表示为(n-1) (n-2) ... 1。这是一个等差数列求和问题其和为 n(n-1)/2。因此平均情况和最坏情况下的时间复杂度是 O(n^2)。 空间复杂度冒泡排序是原地排序算法它不需要额外的存储空间来创建另一个数组只需要一个临时变量用于交换元素。因此冒泡排序的空间复杂度是 O(1)。 稳定性冒泡排序是稳定的排序算法因为它不会改变相同元素之间的相对顺序。 总结来说冒泡排序的时间复杂度是 最佳情况O(n)平均情况O(n^2)最坏情况O(n^2) 由于冒泡排序在大多数情况下效率不高特别是对于大数据集它通常不作为首选排序算法。然而它的简单性和稳定性使其在某些特定情况下如小数据集或基本有序的数据仍然有用。 直接选择排序 前言 直接选择排序也是一个比较简单的排序所以这里放在第二个进行讲解这里和冒泡排序是有一点相似。直接选择排序和冒泡排序一样也是具备一定的教学意义但是没有什么实际操作的意义因为直接选择排序的时间复杂度比较高书写起来和插入排序又差不多所以没有必要写直接选择排序。 直接选择排序gif 直接选择排序单趟实现 1初始化min最小值0也就是最左边的下标的元素为最小值 2遍历数组如果此时出现更小的元素这个元素的下标是i那么我们设定mini 3之后交换最左边的元素和数值最小元素因为这个时候我们已经找到下标了 4最后排序好的最小值放在了最左边那么此时最左边所在位置不需要进行排序了分离出来就可以 5这里因为选择排序效率太低了 我们稍微进阶一下我们从两侧开始选出最小和最大从而进行交换虽然没有提高多少效率但是还是比之前的速度快两倍 直接选择排序注意事项 1这里begin和end都是外层循环也就是随着和--进行缩小差距 2这里begin和end不是索引而是缩小差距用的 3这里是mini和maxi是索引 4最后交换的时候交换的是下标的元素不是下标 直接选择排序多趟实现图解 直接选择排序代码实现 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//直接选择排序
void SelectSort(int* a, int n)
{//多趟循环int begin 0, end n - 1;while (begin end){//单趟循环找出最小值和最大值int mini begin, maxi end;for (int i begin; i end; i){//找到最小值赋值下标if (a[i] a[mini]){mini i;}//找到最小值赋值下标if (a[i] a[maxi]){maxi i;}}//把最小值和最大值放到开头和结尾去Swap(a[mini], a[begin]);Swap(a[maxi], a[end]);begin; end--;}
} 解释 外层循环从索引0开始直到倒数第二个元素。在每次外层循环中假设当前索引位置的元素是未排序部分的最小值。内层循环从外层循环的下一个位置开始遍历未排序部分的元素寻找最小值的索引minIndex。如果找到的最小值不在当前索引位置使用Swap函数将其交换到当前索引位置。这样每次外层循环结束时未排序部分的最小值都被移动到了排序好的部分的末尾。 注意 直接选择排序不是稳定的排序算法即相等元素之间的相对顺序可能会改变。直接选择排序的时间复杂度是O(n^2)在大多数情况下它不如其他更高效的排序算法。直接选择排序的空间复杂度是O(1)因为它是原地排序算法。 选择排序时间复杂度计算 外层循环选择排序算法有一个外层循环它从第一个元素遍历到倒数第二个元素。这个循环执行了 n−1 次其中 n 是数组的长度。 内层循环对于外层循环的每一次迭代都有一个内层循环它从当前考虑的元素之后的第一个元素遍历到数组的最后一个元素。在第一次外层循环迭代时内层循环执行 n−1 次在第二次迭代时执行n−2 次依此类推直到最后一次迭代只执行一次。 总迭代次数内层循环的总迭代次数可以表示为一个等差数列之和 (−1)(−2)…21n(n−1)/2 时间复杂度由于外层循环和内层循环的迭代次数都是 Θ()即线性关系因此选择排序的总时间复杂度是 Θ(^2)。 空间复杂度选择排序是原地排序算法它只需要一个额外的变量来存储最小元素的索引因此空间复杂度是 Θ(1)。 插入排序 前言 插入排序是很重要的排序著名的希尔排序就是从插入排序演变过来的所以我们需要并且很多时候有些面试也是会面试插入排序的所以需要好好捋清楚插入排序的逻辑是什么 插入排序gif 插入排序单趟实现 1插入排序我们需要假设最后一个数值也就是end1是需要排序的其他都是排序好的 2把end1这个下标的数值存放在tmp里面并且和前面进行比较 3如果遇见的元素比tmp大我们继续往前移动进行比较同时a[end]a[end1]往后覆盖 4当遇见的是比tmp小的数值的时候此时我们找到了tmp数值应该在的位置进行插入 插入排序注意事项 这里需要注意的关键也是区间问题假设数组有n个那么end就是倒数第二个下标end1就是最后一个下标是为了防止越界 我们需要小于n-1因为endn-1end1n那么就越界了 所以在循环最大值里面endin-2,end1n-1最后一个数值 插入排序代码的实现 //插入排序
void InsertionSort(int* a, int n)
{//多趟实现,这里n的截止条件-1是因为下标从n-1就结束了//不过我们需要小于n-1因为endn-1end1n那么就越界了for (int i 0; i n - 1; i){//单趟实现int end i; int tmp a[end 1];while (end 0){//判断是不是比前一个数值小小的话就往前走不小的话停下来进行赋值if (tmp a[end]){a[end 1] a[end];end--;}else//找到了此时跳出循环就可以{break;}}//这里是很多人会搞混乱的一点//因为是找到了所以end还没有继续移动但是end11的元素已经移动所以end1的位置是tmp应该出现的位置a[end 1] tmp;}
}解释 函数InsertionSort接受两个参数一个指向整数数组a的指针和数组的长度n。 外层循环从索引0遍历到n-1。每次迭代i代表已排序部分的最后一个元素的索引。 在外层循环的每次迭代中end变量被设置为当前索引i表示当前考虑的元素的索引。tmp变量存储了a[i 1]的值这是未排序的第一个元素也是我们准备插入到已排序部分的元素。 内层while循环用于在已排序部分从后向前扫描找到tmp应该插入的位置。end变量随着比较逐步递减。 在while循环中如果tmp小于当前比较的元素a[end]则将a[end]向后移动一个位置为tmp腾出空间。 如果tmp大于或等于a[end]则while循环通过break语句结束找到了tmp应该插入的位置。 循环结束后将tmp赋值给a[end 1]完成插入操作。 这个过程重复进行直到数组中的所有元素都被扫描并插入到正确的位置。 代码逻辑 插入排序的基本思想是对于数组中的每个元素将其插入到前面已经排好序的子数组中的正确位置。初始时认为数组的第一个元素是已排序的。然后从第二个元素开始逐个插入到前面的已排序序列中。每次插入操作都需要将元素与已排序序列中的元素进行比较直到找到合适的插入点。 注意 这段代码在插入元素时如果插入点是数组的开始那么不需要进行任何移动操作直接插入即可。代码中的end变量用于记录当前比较的元素在数组中的位置而tmp变量用于暂存当前要插入的元素。插入排序是稳定的排序算法因为它不会改变相等元素的相对顺序。 性能 插入排序的平均时间复杂度和最坏时间复杂度都是 (^2)其中 n 是数组的长度。插入排序的空间复杂度是 (1)因为它是原地排序算法不需要额外的存储空间。 插入排序的时间复杂度 插入排序算法的时间复杂度取决于数组的初始顺序具体如下 最佳情况如果输入数组已经是完全有序的插入排序只需要进行 n 次比较每次比较后插入一个元素到已排序部分而不需要进行任何交换。在这种情况下时间复杂度是O(n)。 平均情况在平均情况下插入排序的时间复杂度是 O(n^2)。这是因为每个元素都需要与已排序部分的多个元素进行比较平均下来每个元素需要比较n/2次。 最坏情况如果输入数组是完全逆序的插入排序需要进行n(n−1)/2次比较和 n(n−1)/2次交换时间复杂度是 O(n^2)。 空间复杂度插入排序是原地排序算法它只需要一个额外的存储空间来暂存当前比较的元素因此空间复杂度是 O(1)。 稳定性插入排序是稳定的排序算法它保持了相等元素的原始顺序。 时间复杂度的详细分析 插入排序通过构建有序序列来工作对于未排序的数据在已排序的序列中从后向前扫描找到相应位置并插入。在每次迭代中算法将当前元素与已排序序列中的元素逐一比较找到合适的插入点。对于每个元素比较操作可能需要进行 i 次其中 i 是当前元素在数组中的位置从第一个元素到最后一个元素所需比较的总次数是递增的。 时间复杂度的数学表达式是 总比较次数123…(−1)(−1)/2总比较次数 这表明插入排序的时间复杂度是 Θ(^2),尽管在最坏情况下时间复杂度较高插入排序对于小规模数据集或部分有序的数据集来说是非常高效的。 希尔排序 前言 从希尔开始排序的速度就开始上升了这里的排序开始上一个难度了当然难一点的排序其实也不是很难当你对于插入排序了解的足够深入的时候你会发现其实希尔就是插入的异形但是本质上还是一样的 希尔排序gif 希尔排序单趟实现 1希尔排序本质就是插入排序的进化插入排序是寻找比较进行插入希尔这个人觉得插入排序有点慢就觉得我们可不可以进行预排序也就是数值原来是0-9的情况下最坏的情况我们需要循环9次数才能找到需要插入的点在哪那么此时我们能不能进行一个预排序 2所谓的预排序就是我们假设几个为一组几个为一组这个组的变量我们设置为gap。假设处置3个为一组那么gap3 3此时我们可以把这一组先采取插入排序的方式进行预排序预排序之后我们就会发现这一组的这条线上的数值已经有序 4多趟实现只是反复的实现第一趟的实现的逻辑 希尔排序的多趟实现 1多趟实现只是反复的实现第一趟的实现的逻辑 2我们需要先知道单趟遍历的时候我们需要假设gap一组的这个中间的元素是没有的那么此时此时一组就是两个数值我们需要让这两个数值进行交换 3这两个数值交换之后我们这个时候需要循环开始插入排序的逻辑也就是假设前面的两个数值是已经有序的那么新插入的一个数值是需要排序的我们进行排序 4一趟结束之后我们继续多趟实现这几个数值继续预排序 5继续预排序 6此时gap3那么我们继续gap/21之后继续进行预排序此时我们就得到了这个排序正确的数值 希尔排序代码的实现-版本1 //希尔排序
void ShellSort(int* a, int n)
{int gap n - 1;//定义gap,这里循环停止的条件是1原因是1了已经恒大于0了所以需要大于1等于都不可以while (gap 1){gap gap / 3 1;//循环实现每一组for (int j 0; j gap; j){//gap单趟实现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;}}}
} 解释 函数ShellSort接受两个参数一个指向整数数组a的指针和数组的长度n。 初始化间隔gap为数组长度n - 1这是希尔排序开始时的最大间隔。 while循环用于逐步减小间隔直到间隔为1。当gap大于1时循环继续。 在每次while循环的开始重新计算间隔gap。这里使用的是gap gap / 3 1这是一种常见的间隔序列由Donald Shell提出。 外层for循环用于遍历数组步长为当前的间隔gap。 内层for循环用于实现插入排序但仅限于间隔gap内的范围。 在内层循环中end变量记录当前考虑的元素的索引tmp变量暂存当前要插入的元素。 while循环用于在间隔gap内从后向前扫描找到tmp应该插入的位置。 如果tmp小于当前比较的元素a[end]则将a[end]向后移动一个间隔gap的距离为tmp腾出空间。 如果tmp大于或等于a[end]则while循环结束找到了tmp应该插入的位置。 循环结束后将tmp赋值给a[end gap]完成插入操作。 这个过程重复进行直到数组中的所有元素都被扫描并插入到正确的位置。 代码逻辑 希尔排序通过多个插入排序的变体来工作每个变体都有一个特定的间隔。初始时间隔较大排序的稳定性较差但可以快速减少无序度。随着间隔逐渐减小排序的稳定性逐渐提高最终当间隔为1时算法变为普通的插入排序确保数组完全有序。 注意 希尔排序不是稳定的排序算法因为它可能会改变相等元素的相对顺序。希尔排序的时间复杂度通常在 (log) 和 (^2) 之间具体取决于间隔序列的选择。希尔排序的空间复杂度是 (1因为它是原地排序算法不需要额外的存储空间。 希尔排序代码的实现-版本2 上面那个代码一般是教学使用书写会更加详细理解但是很多书本会这样写 这里的关键在于不再进行先一组排序结束再反过来进行下一组反复执行 而是直接这一组实现完毕之后直接进行下一组的实现本质上还是一样的 只是直接这样书写容易不理解 //希尔排序
void ShellSort02(int* a, int n)
{int gap n - 1;//定义gap,这里循环停止的条件是1原因是1了已经恒大于0了所以需要大于1等于都不可以while (gap 1){gap gap / 3 1;//循环实现每一组//gap单趟实现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;}}
} 解释 函数ShellSort02接受两个参数一个指向整数数组a的指针和数组的长度n。 初始化间隔gap为数组的最后一个索引n - 1。 while循环用于逐步减小间隔直到间隔小于或等于1。循环的条件是gap 1这是因为间隔在每次迭代中都会减小所以不需要检查gap 1的情况。 在while循环内部重新计算间隔gap。这里使用的计算方法是gap gap / 3 1这是一种常见的间隔序列旨在逐步减小间隔直到达到1。 外层for循环遍历数组直到i n - gap即遍历到数组的末尾减去当前间隔的位置。 在外层for循环中end变量记录当前考虑的元素的索引tmp变量暂存当前间隔位置的元素值。 内层while循环用于在数组中找到tmp应该插入的位置。它从当前索引end开始向前以间隔gap的距离进行比较。 如果tmp小于当前比较的元素a[end]则将a[end]向后移动一个间隔gap的距离为tmp腾出空间。 如果tmp大于或等于a[end]则while循环结束找到了tmp应该插入的位置。 循环结束后将tmp赋值给a[end gap]完成插入操作。 这个过程重复进行直到数组中的所有元素都被扫描并插入到正确的位置。 代码逻辑 希尔排序通过多个插入排序的变体来工作每个变体都有一个特定的间隔。初始时间隔较大随着算法的进行间隔逐渐减小直到变为1此时算法变为普通的插入排序。通过逐步减小间隔希尔排序能够在每次迭代中对数组的更大范围内的元素进行排序从而减少比较和移动的次数。 希尔排序gap的界定 一般来说一组为多少这个不好说希尔开始书写的时候gap是/2,来进行书写的但是被认为效率最高的是除以31但是/31有一个弊端就是这个是恒大于0的所以终止条件应该换为大于1就继续循环小于等于1就停止循环 希尔排序的时间复杂度 希尔排序的时间复杂度取决于所选择的间隔序列它通常介于以下范围 最好情况对于某些特定的间隔序列希尔排序可以达到O(nlogn) 的时间复杂度这与快速排序或归并排序相当。 平均情况平均情况下希尔排序的时间复杂度通常被认为是 O(n(logn)2)这比O(nlogn) 稍差但仍然比普通插入排序的 (^2) 好得多。 最坏情况最坏情况下希尔排序的时间复杂度可以退化到(^2)这通常发生在间隔序列选择不佳时。 实际性能在实际应用中希尔排序的性能通常比普通插入排序好但不如快速排序、堆排序或归并排序。它的实际性能还取决于数据的初始状态和间隔序列的选择。 间隔序列的影响不同的间隔序列对希尔排序的性能有很大影响。例如使用Hibbard 间隔序列或Sedgewick间隔序列可以提高性能有时甚至可以达到接近 O(nlogn) 的效率。 空间复杂度希尔排序是原地排序算法其空间复杂度为 (1)。 稳定性希尔排序不是稳定的排序算法这意味着相等的元素在排序后可能会改变它们原来的顺序。 总的来说希尔排序是一种有效的排序算法特别是对于中等大小的数据集或者当数据已经部分有序时。然而对于大型数据集通常推荐使用其他更高效的排序算法如快速排序、堆排序或归并排序。 快排霍尔版本-递归解决 前言 快排是很重要的排序也是一种比较难以理解的排序这里我们会用递归的方式和非递归的方式来解决递归来解决是比较简单的非递归来解决是有点难度的 快排也称之为霍尔排序因为发明者是霍尔本来是命名为霍尔排序的但是霍尔这个人对于自己创造的排序很自信所以命名为快排 当然也是如他所料快排确实很快但是还没有达到第一批次那个程度 快排gif 快排实现逻辑排序 单趟实现逻辑: 1.假设左边为keyi也就是对比数值 2右边R先走循环寻找比keyi小的数值 3左边l走循环寻找比keyi大的数值 4交换找到的比keyi大的数值和小的数值此时会导致小的在左边大的在右边最后相遇的时候交换keyi和相遇的元素 多趟实现: 1多趟实现可以采取递归和非递归但是总体逻辑都是一样的这里先讲解一下递归的方式2此时我们会发现keyi下标所在位置就是从前往后6的位置所以6回到自己的位置我们以keyi为分界点进行切割【left,keyi-1】keyi【keyi1,right】 进行递归从而实现简易版的速排完善逻辑: 1此时是快排还是有点问题的当数值本身就是顺序的时候 会发现此时的时间复杂度就变成了n^2也就是不快了 2原因是当本身就是排序好的时候right右边会一直往左边寻 找直到找到left和自己交换此时的时间复杂度也就是 n,n-1..1.0 3解决办法我们可以三个数值取中什么意思?也就是不管什么情况我们都取出前三个数值比如这里的 6 1 2 我们取出6 1 2取出中间的位置2和keyi进行交换其他逻辑不变完善逻辑: 1此时我们发现逻辑没有问题但是速度还是和堆排序有点差距那么此时我们继续进行优化 2因为这里是用递归来实现的我们发现递归的实现是逐级实现的也就是 第-层-第n层:1-2-3-4-…-n-1-n 这样的递归方式来实现的所以越到下面递归的越多 我们可以把最后十层的递归用插入排序来实现一下 3为什么用插入排序?在排序里面有希尔排序冒泡排序选 择排序堆排序 希尔排序-插入排序的进阶(书写复杂) 冒泡排序-时间复杂度高 选择排序-时间复杂度和冒泡一样比较高 堆排序-处理大型数字问题这里没必要 所以我们采取插入排序的方式进行解决 4解决我们只需要在递归的时候加一个判断就可以当数 值小于等于10 的时候我们直接调用插入排序解决问题。 此时速排(霍尔排序)递归的方式也就结束了。 图解 快排单趟实现 快排多趟实现 简易版本的代码实现 //霍尔方法(递归实现)
void QuickSort01(int* a, int left, int right)
{//递归停止条件if (left right)return;//单趟实现//右边找小左边找大int begin left; int end right;int keyi begin;while (begin end){//右边找小不是的话移动,是的话不移动并且跳出循环while (begin end a[keyi] a[end]){end--;}//左边找大不是的话移动是的话不移动并且跳出循环while (begin end a[keyi] a[begin]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);keyi begin;//多趟递归实现//[left,keyi-1] keyi [keyi1,right] 这里传递的是区间// 1 0 1 2 1 当只剩一个数值的时候也就是这个区间的时候递归停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi 1, right);
} 解释 函数定义QuickSort01函数接受一个整数数组的指针a以及两个整数left和right分别表示要排序的数组部分的起始和结束索引。 递归终止条件如果left大于或等于right则当前子数组无需排序递归结束。 初始化设置两个指针begin和end分别指向子数组的起始和结束位置keyi作为基准元素的索引初始位置设为left。 单趟排序 使用两个内层循环一个从右侧向左寻找比基准值小的元素另一个从左侧向右寻找比基准值大的元素。当找到合适的元素时交换这两个元素的位置然后继续寻找直到begin和end相遇。 基准值定位将基准值a[keyi]与begin指向的元素交换此时begin指向的位置是基准值的最终位置。 递归排序对基准值左边的子数组[left, keyi - 1]和右边的子数组[keyi 1, right]递归调用QuickSort01函数进行排序。 效率快速排序的平均时间复杂度为O(n log n)但在最坏情况下如数组已经排序时间复杂度会退化到O(n^2)。霍尔方法通过减少不必要的数据交换来提高排序效率。 辅助函数Swap函数用于交换两个元素的值虽然在代码中未给出定义但它是快速排序中交换元素的关键操作。 快速排序算法的效率和性能在实际应用中通常优于其他O(n log n)算法如归并排序尤其是在数据量较大时。然而其稳定性不如归并排序且在最坏情况下性能较差。在实际应用中快速排序通常与其他排序算法结合使用以提高整体排序性能。 注意事项 注意事项1 这里有一个关键点是很重要的也就是我们是从右边先出发的因为我们的keyi的位置在左边。 如果我们的keyi的下标在左边并且左边先走的话就会产生一种结果 如图 注意事项2 不是等于就交换是等于会跳过往下找 当我们写的是不等于的时候 快排完整代码实现-三数值取中 此时存在的最大问题就是如果排序本身就是顺序排序的情况下这时间复杂度反而高了所以我们对排序进行修改 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//霍尔方法(递归实现)
//三数取中
int GetMid(int* a, int left, int right)
{//三数取中传参的是下标我们取中也是根据下标进行计算的int mid (left right) / 2;if (a[left] a[right]){if (a[mid] a[left])//a[mid] a[left] a[right]{return left;}else if(a[mid] a[right])// a[left] a[right] a[mid] {return right;}else{return mid;}}else//a[left] a[right]{if (a[mid] a[left])//a[mid] a[left] a[right]{return left;}else if (a[mid] a[right])//a[left] a[right] a[mid] {return right;}else{return mid;}}
}
void QuickSort01(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 keyi begin;while (begin end){//右边找小不是的话移动,是的话不移动并且跳出循环while (begin end a[keyi] a[end]){end--;}//左边找大不是的话移动是的话不移动并且跳出循环while (begin end a[keyi] a[begin]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);keyi begin;//多趟递归实现//[left,keyi-1] keyi [keyi1,right] 这里传递的是区间// 1 0 1 2 1 当只剩一个数值的时候也就是这个区间的时候递归停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi 1, right);
} 总结 函数目的选择一个合适的基准值以提高快速排序算法的效率。 传入参数接受一个整数数组的指针a以及表示数组部分边界的整数left和right。 计算中间索引通过(left right) / 2计算中间元素的索引mid。 三数取中逻辑 如果数组的第一个元素a[left]小于最后一个元素a[right] 如果中间元素a[mid]小于第一个元素则选择第一个元素作为基准。如果中间元素大于最后一个元素则选择最后一个元素作为基准。否则选择中间元素作为基准。如果第一个元素大于或等于最后一个元素即数组首尾元素已经排序或相等 如果中间元素大于第一个元素则选择第一个元素作为基准。如果中间元素小于最后一个元素则选择最后一个元素作为基准。否则选择中间元素作为基准。 返回值函数返回基准值的索引。 优化目的通过三数取中法选择基准可以减少快速排序在特定情况下性能退化的问题如数组已经排序或包含大量重复元素。 适用场景适用于快速排序算法中作为选择基准值的策略。 性能影响选择一个好的基准值可以确保数组被均匀地划分从而接近快速排序的最佳平均时间复杂度O(n log n)。 三数取中法是一种简单而有效的基准选择策略它通过比较数组的首元素、尾元素和中间元素来确定一个相对平衡的基准值有助于提高快速排序的整体性能和稳定性。 快排完整代码实现-减少递归次数 此时我们还面临的问题就是底层的递归次数过多的问题递归会随着次数的增加呈现倍数增长就像三角形一样 最后我们减少递归次数把最底层从递归改为插入排序逻辑完成 快排完整代码 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//霍尔方法(递归实现)
//三数取中
int GetMid(int* a, int left, int right)
{//三数取中传参的是下标我们取中也是根据下标进行计算的int mid (left right) / 2;if (a[left] a[right]){if (a[mid] a[left])//a[mid] a[left] a[right]{return left;}else if(a[mid] a[right])// a[left] a[right] a[mid] {return right;}else{return mid;}}else//a[left] a[right]{if (a[mid] a[left])//a[mid] a[left] a[right]{return left;}else if (a[mid] a[right])//a[left] a[right] a[mid] {return right;}else{return mid;}}
}
void QuickSort01(int* a, int left, int right)
{//递归停止条件if (left right)return;//当区间数值小于10个此时我们直接采取插入排序进行排序if (right - left 1 10){//这里记得是左右区间所以不能只传递a而是传递a leftInsertionSort(a left, right - left 1);}else{//三数取中int mid GetMid(a, left, right);Swap(a[mid], a[left]);//单趟实现//右边找小左边找大int begin left; int end right;int keyi begin;while (begin end){//右边找小不是的话移动,是的话不移动并且跳出循环while (begin end a[keyi] a[end]){end--;}//左边找大不是的话移动是的话不移动并且跳出循环while (begin end a[keyi] a[begin]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);keyi begin;//多趟递归实现//[left,keyi-1] keyi [keyi1,right] 这里传递的是区间// 1 0 1 2 1 当只剩一个数值的时候也就是这个区间的时候递归停止 QuickSort01(a, left, keyi - 1);QuickSort01(a, keyi 1, right);}
} 代码解释 三数取中函数 GetMid: 计算中间索引 mid。通过比较数组的首元素、尾元素和中间元素选择一个合适的基准值。如果首元素小于尾元素选择中间元素和首尾元素中较小或较大的一个作为基准。如果首元素大于尾元素选择中间元素和首尾元素中较大或较小的一个作为基准。 快速排序函数 QuickSort01: 递归停止条件如果当前区间的左右索引 left 和 right 交叉或重合则不需要排序。当区间大小小于或等于10时使用插入排序因为小数组上插入排序更高效。使用 GetMid 函数获取基准值的索引并将基准值与首元素交换。霍尔方法的分区操作通过两个指针 begin 和 end 进行分区。递归地对基准值左边和右边的子区间进行快速排序。 辅助函数 Swap: 交换两个元素的值虽然代码中未给出定义但通常是一个简单的值交换操作。 总结 算法优化: 通过三数取中法选择基准值可以提高基准值的选中质量从而提高快速排序的效率。小数组优化: 当子数组的大小小于或等于10时使用插入排序代替快速排序因为小数组上插入排序的性能通常更好。递归与迭代: 快速排序是一个递归算法但在小数组上切换到迭代的插入排序可以减少递归开销。分区策略: 使用霍尔方法进行分区这是一种高效的分区策略可以减少不必要的数据交换。适用场景: 这种改进的快速排序适用于大多数需要排序的场景尤其是在大数据集上它能够保持较好的性能。时间复杂度: 平均情况下时间复杂度为 O(n log n)最坏情况下已排序数组时间复杂度为 O(n^2)但由于三数取中法和插入排序的结合最坏情况出现的概率降低。 通过这种改进快速排序算法在处理小数组时更加高效同时在大数据集上也能保持较好的性能使其成为一种更加健壮的排序算法。 快排的时间复杂度 快速排序算法的时间复杂度取决于分区过程中基准值的选择。 理想情况下 基准值会将数组均匀地分成两部分每部分的元素数量大致相等。对于这种理想情况快速排序的时间复杂度是 O(n log n)其中 n 是数组中的元素数量。 最坏情况下 如果基准值的选择非常不均匀从而导致每次分区都极不平衡快速排序的最坏时间复杂度会退化到 O(n^2)。这种情况通常发生在数组已经排序或所有元素相等的情况下。 在当前代码中 使用了三数取中法来选择基准值这种方法可以在大多数情况下避免选择极端值作为基准从而减少最坏情况发生的概率。但是如果数组的元素分布非常不均匀或者存在大量重复元素仍然可能遇到性能退化的情况。 此外代码中还引入了一个优化当子数组的大小小于或等于10时使用插入排序而不是快速排序。这是因为对于小数组插入排序的性能通常比快速排序更好而且插入排序是稳定的。这个优化可以提高算法在处理小数组时的效率。 总的来说这个改进的快速排序算法的平均时间复杂度是 O(n log n)但在最坏情况下仍然是 O(n^2)。然而由于三数取中法和插入排序的优化最坏情况的发生概率被大大降低了。在实际应用中这种改进的快速排序算法通常能够提供非常高效的排序性能。 前后修改之后速度进行对比 优化和不优化之间的区别 这里计算的是一千万个数值进行排序的毫秒数值也就是不到一秒还是很快的尤其是修改之后解决了大量的递归问题 注意事项 这里调用的插入排序是升序写的快排也是升序如果你需要测试降序那么你需要把插入排序一起改成降序不然会导致排序冲突 快排前后指针-递归解决 前言 快排解决办法有很多种这里我再拿出来一种前后指针版本 虽然这个版本的时间复杂度和霍尔一样逻辑也差不多但是实际排序过程确实会比霍尔慢一点 快排gif 快排前后指针实现逻辑 前后指针实现逻辑(升序):单趟排序: 1我们使用递归来进行实现所以我们先实现单趟排序 2定义两个下标也就是所谓的指针初始的时候一个指向最左边第一个元素(prev)一个指向第二个元素(cur)最后定义一个对比keyi3此时先判断我们的cur是不是小于keyi。cur小于keyi的话:prev交换之后cur4但是我们如果和自己交换此时没有什么意义所以这里我们需要做一个处理 5继续往前走如果遇见的是:比keyi下标大的元素此时cur直到遇见的是比keyi下标小的元素循环执行.prev交换之后cur 6最后cur走到最后一个元素我们交换keyi的下标元素和prev的下标元素 多趟实现: 1递归进行分割:【leftkeyi-1】keyi【keyi1right】 2停止条件就是当leftright 原因:【left, keyi-1】keyi【keyi1, right】 快排单趟实现 这里只是图解单趟实现逻辑因为多趟实现的逻辑和霍尔的一样也是递归所以不进行多次书写 代码实现 这里的代码实现的核心逻辑不一样大的框架是一样的也就是三数取中以及减少递归从而使用插入排序这样的逻辑是一样的下面我们来看看这个新的组装怪 //快排前后指针方法(递归实现)
void QuickSort02(int* a, int left, int right)
{//递归停止条件if (left right)return;//创建两个变量作为前后指针使用int prev left; int cur prev 1;int keyi left;//当快指针到尾的时候跳出循环-交换while (cur right){//前后指针中间是比a[keyi]大的数值所以遇见大的小的停止if (a[keyi] a[cur]){//停止之后慢指针,并且进行交换,因为中间才是大的数值cur遇见大数值。遇见小数值才停下来prev;Swap(a[prev], a[cur]);//同理快指针也进行往后移动cur;}else{cur;}}Swap(a[prev], a[keyi]);keyi prev;//多趟递归实现//[left,keyi-1] keyi [keyi1,right] 这里传递的是区间// 1 0 1 2 1 当只剩一个数值的时候也就是这个区间的时候递归停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi 1, right);
} 总结 算法基础快速排序是一种分而治之的排序算法它通过递归地将数组分为较小的子数组然后对这些子数组进行排序。 分区策略使用前后指针prev和cur进行分区而不是传统的左右指针。这种方法在某些情况下可以减少元素交换的次数。 基准值选择基准值keyi是数组的第一个元素即left索引对应的元素。 指针移动规则 prev作为慢指针用于跟踪比基准值小的元素的边界。cur作为快指针从left 1开始遍历数组。 元素交换当快指针指向的元素大于基准值时不进行交换快指针继续移动当快指针指向的元素小于或等于基准值时与慢指针所指元素交换然后慢指针和快指针都向前移动。 递归排序在基准值确定之后递归地对基准值左边和右边的子数组进行排序。 时间复杂度平均情况下快速排序的时间复杂度为O(n log n)。最坏情况下如果每次分区都极不平衡时间复杂度会退化到O(n^2)。 空间复杂度由于递归性质快速排序的空间复杂度为O(log n)。 算法优化通过前后指针方法可以在某些情况下提高快速排序的性能特别是当基准值接近数组中间值时。 适用场景快速排序适用于大多数需要排序的场景特别是在大数据集上它通常能够提供非常高效的排序性能。 优化 这里我们可以看到cur无论是if还是else里面都需要所以我们直接放到外面 其次我们为了效率不和自己交换我们不和自己交换进行一个判断条件 快慢指针代码优化完整 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//快排前后指针方法(递归实现)
void QuickSort02(int* a, int left, int right)
{//递归停止条件if (left right)return;if (right - left 1 10){InsertionSort(a left, right - left 1);}else{//三数取中int mid GetMid(a, left, right);Swap(a[mid], a[left]);//单趟实现//创建两个变量作为前后指针使用int prev left; int cur prev 1;int keyi left;//当快指针到尾的时候跳出循环-交换while (cur right){//前后指针中间是比a[keyi]大的数值所以遇见大的小的停止if (a[keyi] a[cur] prev ! cur){//停止之后慢指针,并且进行交换,因为中间才是大的数值cur遇见大数值。遇见小数值才停下来Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyi]);keyi prev;//多趟递归实现//[left,keyi-1] keyi [keyi1,right] 这里传递的是区间// 1 0 1 2 1 当只剩一个数值的时候也就是这个区间的时候递归停止 QuickSort02(a, left, keyi - 1);QuickSort02(a, keyi 1, right);}
} 总结 基本递归结构算法使用递归调用来处理子数组这是快速排序算法的核心结构。 小数组优化当子数组的大小小于或等于10时算法使用插入排序而不是快速排序因为插入排序在小规模数据上更高效。 三数取中法为了更均匀地分割数组算法使用三数取中法选择基准值这有助于减少最坏情况发生的概率。 前后指针方法算法使用两个指针prev和cur其中prev作为慢指针cur作为快指针通过这种方式进行一次遍历完成分区。 分区操作快指针从left 1开始遍历如果当前元素小于基准值则与慢指针所指的元素交换然后慢指针向前移动。 递归排序子数组基准值确定后算法递归地对基准值左边和右边的子数组进行排序。 时间复杂度平均情况下算法的时间复杂度为O(n log n)最坏情况下为O(n^2)。但由于采用了小数组优化和三数取中法最坏情况的发生概率降低。 空间复杂度算法的空间复杂度为O(log n)这主要由于递归调用导致的栈空间使用。 适用场景这种改进的快速排序算法适用于大多数需要排序的场景尤其是在大数据集上它能够提供非常高效的排序性能同时在小数据集上也表现出较好的效率。 算法稳定性由于使用了插入排序对小规模子数组进行排序算法在处理小规模数据时具有稳定性。 注意在实际测试·里面前后指针比霍尔排序慢一点 通过这种混合排序策略算法在保持快速排序优点的同时也提高了在特定情况下的排序效率使其成为一种更加健壮的排序方法。 注意事项 这里调用的插入排序是升序写的快排也是升序如果你需要测试降序那么你需要把插入排序一起改成降序不然会导致排序冲突 快排霍尔版本-非递归解决 前言 快拍不仅需要学习递归还需要学东西非递归这样更有助于我们理解快拍 首先我们需要知道非递归的学习需要使用栈所以如果我们的栈的学习是不完善的建议学习一下栈 非递归gif 这里其实单词循环是谁其实不重要可以是前后指针也可以是霍尔方式这里我们拿出来霍尔的gif来观看 实现图解 非递归实现主要是依赖栈来进行实现依赖栈的特点先进后出后进前出 1首先我们需要写一个栈的库进行调用 2入区间调用单次排序的实现思路 3入区间的时候我们需要把握入栈和出栈的关键 代码实现前后指针 首先我们调用栈 头文件 #define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int STDataType;
typedef struct Stack
{STDataType* _a; // 首元素的地址int _top; // 栈顶初始化为0也就是等同于size初始化为-1等同于下标int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈尾元素
STDataType Stackhop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps); 实现文件 #includeStack.h
// 初始化栈
void StackInit(Stack* ps)
{ps-_a NULL;ps-_capacity ps-_top 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps ps-_top);free(ps-_a);ps-_a NULL;ps-_capacity ps-_top 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{//判断需不需要扩容,相等的时候需要扩容if (ps-_capacity ps-_top){//判断空间是不是0因为为0的时候再多的数值*2,也是0int newcapacity ps-_capacity 0 ? 4 : ps-_capacity * 2;STDataType* tmp (STDataType*)realloc(ps-_a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(StackPush:tmp:err:);return;}ps-_capacity newcapacity;ps-_a tmp;}ps-_a[ps-_top] data;ps-_top;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);ps-_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{//这里必须大于0 因为我们这里等同size也就是个数等于0都不行assert(ps);return ps-_a[ps-_top - 1];
}
// 获取栈尾元素
STDataType Stackhop(Stack* ps)
{assert(ps ps-_top 0);return ps-_a[0];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{//获取有效元素的时候里面可以没有元素assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{//这里的判断是不是空也就是里面是不是有数值这里等于是一个判断没有的话返回ture有的话返回falseassert(ps);return ps-_top 0;
}其次调用前后指针来实现 //快排前后指针方法(单趟)
int one_QuickSort02(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 keyi left;//当快指针到尾的时候跳出循环-交换while (cur right){//前后指针中间是比a[keyi]大的数值所以遇见大的小的停止if (a[keyi] a[cur] prev ! cur){//停止之后慢指针,并且进行交换,因为中间才是大的数值cur遇见大数值。遇见小数值才停下来Swap(a[prev], a[cur]);}cur;}Swap(a[keyi], a[prev]);return prev; //快排 非递归实现
void QuickSort003(int* a, int left, int right)
{//非递归实现主要是用栈来模拟实现在c里面我们可以直接调用栈但是在C语言里面我们只能写出来栈再进行调用//思路霍尔方式//1单趟的思路还是一样的如果是升序的情况下依旧是先从右边出发找小后从左边出发找大//2,循环递归过程我们改为利用进栈出栈来实现。首先我们需要明确这里传递的是区间也就是利用栈实现的时候我们传递的是数组和区间利用区间进行计算。这里的关键在于传递区间的时候我们需要详细知晓栈的特点先进后出后进后出。所以在传递区间的时候如果多趟循环一分为二的时候我们需要先传递右侧的区间再传递左侧区间因为我们需要先计算左侧。同理进去之后我们需要继续入栈需要先-入计算左侧的区间的右侧区间后入左侧区间。这样就会先计算左侧区间。栈的特性先进后出后进先出// // 所以这里我们把霍尔排序单趟实现来单独拿出来这样的话我们接受的返回值是中间值//[left,keyi-1] keyi [keyi1,right]//这里需要用非递归来解决Stack ps;StackInit(ps);StackPush(ps, right);StackPush(ps, left);while (!StackEmpty(ps)){int begin StackTop(ps);StackPop(ps);int end StackTop(ps);StackPop(ps);//假设入栈区间此时来到- 0-2int mini one_QuickSort02(a, begin, end);//经过计算之后此时中间值是keyi1//0 1 2 三个区间三个数值此时进行入栈判断//[begin,keyi-1]keyi[keyi1,end]//[ 0 , 0 ] 1 [ 2 , 2 ]//所以不继续入栈if (mini 1 end){//右边先入栈后计算StackPush(ps, end);StackPush(ps, mini 1);}if (mini - 1 begin){//左边区间后入栈先计算StackPush(ps, mini - 1);StackPush(ps, begin);}}StackDestroy(ps);
} 解释 one_QuickSort02 函数 这个函数是快速排序算法中的单趟排序实现。它使用前后指针法来实现具体步骤如下 初始化指针prev 初始化为 leftcur 初始化为 prev 1keyi 也初始化为 left。循环当 cur 小于等于 right 时执行循环体内的操作。比较和交换如果当前 cur 指向的元素小于 keyi 指向的元素并且 prev 指针不等于 cur说明找到了一个比基准值小的元素需要交换。将 a[prev] 和 a[cur] 交换并将 prev 指针向前移动一位。移动快指针无论是否发生交换cur 指针都向前移动一位。交换基准值循环结束后将 keyi 指向的元素与 prev 指向的元素交换此时 prev 指向的是比基准值小的元素的最后一个位置。返回值函数返回 prev 的值这个值是下一次分区的起始位置。 QuickSort003 函数 这个函数是快速排序的非递归实现使用栈来模拟递归过程。具体步骤如下 初始化栈创建并初始化一个栈 ps。入栈将 left 和 right 作为初始区间入栈。循环只要栈不为空就执行循环。单趟排序每次从栈中取出两个值作为区间的左右边界调用 one_QuickSort02 函数进行单趟排序得到中间值 mini。判断区间根据 mini 的位置判断是否需要继续对左右区间进行排序。 如果 mini 1 end则说明右侧还有元素需要排序将 end 和 mini 1 入栈。如果 mini - 1 begin则说明左侧还有元素需要排序将 begin 和 mini - 1 入栈。出栈每次循环结束都会从栈中弹出两个值直到栈为空。销毁栈循环结束后销毁栈。 对于栈和队列不是很明白的推荐看一下栈和队列篇章 数据结构-栈和队列(速通版本)-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138715165 代码实现霍尔排序 这里其实不管是前后指针还是霍尔排序其实都是一样的因为本质上都是让数值到应该到的位置所以本质上是一样的这里我再调用一个霍尔的方式是因为一方面和前后指针的调用形成对比一方面有不同的注释 //交换函数
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
//霍尔方法(单趟实现)
int one_QuickSort01(int* a, int left, int right)
{//三数取中int mid GetMid(a, left, right);Swap(a[mid], a[left]);//单趟实现//右边找小左边找大int begin left; int end right;int keyi begin;while (begin end){//右边找小不是的话移动,是的话不移动并且跳出循环while (begin end a[keyi] a[end]){end--;}//左边找大不是的话移动是的话不移动并且跳出循环while (begin end a[keyi] a[begin]){begin;}Swap(a[begin], a[end]);}Swap(a[keyi], a[begin]);return begin;
}
//霍尔方法再次调用
void QuickSort03(int* a, int left, int right)
{Stack ps;StackInit(ps);StackPush(ps, right);StackPush(ps, left);while (!StackEmpty(ps)){//取出左区间int begin StackTop(ps);StackPop(ps);//取出右边区间int end StackTop(ps);StackPop(ps);int mini one_QuickSort01(a, begin, end);//计算区间//假设传递的区间是2-4 --- 传递过来的数值也就是下标是14-22/21 ---此时mini2,也就是此时我们返回的数值要么是第一个数值要么的第二个数值的下标不管是哪个此时都会变成一个数值//此时我们继续入栈入栈的是mini1 也就是3-4继续传递区间此时传递回来的mini还是3但是此时344了 所以不继续入栈因为数值只有一个不是区间了//右区间入栈后出if (mini 1 end){//入右边之后左边这样取的时候栈顶先取左边之后右边StackPush(ps, end);StackPush(ps, mini 1);}//左区间入栈先出if (mini - 1 begin){StackPush(ps, mini - 1);StackPush(ps, begin);}}StackDestroy(ps);
}解释 one_QuickSort01 函数 这个函数是霍尔快速排序算法的单趟实现具体步骤如下 三数取中使用 GetMid 函数找到数组 a 中间位置的元素并将其与数组第一个元素交换left 索引位置的元素。初始化指针begin 初始化为 leftend 初始化为 rightkeyi 初始化为 begin。循环使用 while 循环只要 begin 小于 end就继续执行循环。右边找小从 end 向 begin 扫描找到第一个小于基准值 a[keyi] 的元素。如果找到end 指针向前移动否则跳出循环。左边找大从 begin 向 end 扫描找到第一个大于基准值 a[keyi] 的元素。如果找到begin 指针向后移动否则跳出循环。交换元素将找到的两个元素 a[begin] 和 a[end] 交换位置。基准值交换循环结束后将 keyi 指向的元素与 begin 指向的元素交换此时 begin 指向的是基准值的正确位置。返回值函数返回 begin 的值这个值是下一次分区的起始位置。 QuickSort03 函数 这个函数是快速排序的非递归实现使用栈来模拟递归过程 初始化栈创建并初始化一个栈 ps。入栈将初始区间的左右边界 left 和 right 入栈。循环只要栈不为空就继续执行循环。单趟排序每次从栈中取出两个值作为区间的左右边界调用 one_QuickSort01 函数进行单趟排序得到中间值 mini。计算新区间根据 mini 的位置计算新的左右区间。 如果 mini 1 end则说明右侧还有元素需要排序将 end 和 mini 1 入栈。如果 mini - 1 begin则说明左侧还有元素需要排序将 begin 和 mini - 1 入栈。栈的特性由于栈是后进先出LIFO的数据结构所以先入栈的是右侧区间后入栈的是左侧区间这样在出栈时会先处理左侧区间再处理右侧区间。销毁栈循环结束后销毁栈。 这种非递归实现的快速排序算法利用了栈的特性来避免递归调用从而减少了函数调用的开销并且在处理大数据集时可以避免递归深度过大导致的栈溢出问题。 归并排序 递归实现 前言 归并排序是一种逻辑很简单但是实现有点难度的排序尤其是非递归对于区间的把握更是需要一点逻辑的推导但是没有关系轻松拿捏 归并排序gif 归并排序单趟实现 1创建tmp数组 2递归到最小值进行排序同时拷贝到题目破数组里面 3这里的关键逻辑实现是递归回来的时候进行排序 4最后我们把数值重新拷贝回去原数组 注意这里的取值我们直接取中间值进行递归一分为二 代码实现注意事项 关于创建tmp数组我们需要创建的数组应该是等大的要么就进行初始化。 因为我们是malloc出来的空间为什么malloc出来的空间必须是等大的因为这里我们用的是Visual Studio 2022的编译器这个编译器里面是不支持可变长数组的。所以我们需要用malloc或者realloc来实现创建空间也就是动态内存的分配malloc创建空间的时候空间里面是有随机值的realloc创建的空间里面的数值是0所以一旦我们进行排序的时候如果我们不进行覆盖的话这里面的数值也会参与排序从而导致数值出现偏差 这里对于这一点不清楚的可以看看之前写的文章因为当时写这个文章的时候刚接触编程所以讲述的主要是以语法和一些简单的性质特点希望可以起到帮助 动态内存函数的使用和综合实践-mallocfreerealloccalloc_内存申请函数-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/137075045 代码实现 //归并排序递归实现子函数(实现函数)
void _MergeSort01(int* a, int* tmp, int begin, int end)
{if (begin end)return;int mini (begin end) / 2;//注意这里关键在于区间的传递//不应该传递【left,mini-1】【mini,right】// 应该传递【left,mini】【mini1,right】//递归左右区间, 递归到最小个数进行对比_MergeSort01(a, tmp, begin, mini);_MergeSort01(a, tmp, mini 1, end);int begin1 begin, end1 mini;int begin2 mini 1, end2 end;int i begin;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];}//数据从tmp拷贝回去数组a里面memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}
//归并排序递归实现创建tmp函数
void MergeSort01(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}_MergeSort01(a, tmp, 0, n - 1);free(tmp);tmp NULL;
} 解释 _MergeSort01 函数这是归并排序的递归子函数它接收三个参数数组 a临时数组 tmp以及要排序的数组区间 [begin, end]。 如果 begin 大于或等于 end则表示区间内没有元素或只有一个元素不需要排序直接返回。计算区间的中点 mini将数组分为两部分[begin, mini] 和 [mini 1, end]。对这两部分分别递归调用 _MergeSort01 函数进行排序直到每个子区间只有一个元素。 合并过程 初始化两个指针 begin1 和 end1 指向第一个子区间的开始和结束位置begin2 和 end2 指向第二个子区间的开始和结束位置。使用一个索引 i 指向 tmp 数组的当前位置用于存放合并后的有序元素。使用两个 while 循环来比较两个子区间的元素将较小的元素复制到 tmp 数组中并移动对应的指针。如果第一个子区间的所有元素已经被复制到 tmp 中但第二个子区间还有剩余元素将这些剩余元素复制到 tmp 数组的剩余位置。同理如果第二个子区间的所有元素已经被复制将第一个子区间的剩余元素复制到 tmp。 拷贝回原数组 使用 memcpy 函数将 tmp 数组中从索引 begin 开始的元素复制回原数组 a。这里计算了需要复制的元素数量为 end - begin 1乘以 sizeof(int) 来确定字节数。 MergeSort01 函数这是归并排序的初始化函数接收数组 a 和数组的长度 n。 首先使用 malloc 分配一个临时数组 tmp大小为 n 个 int。如果内存分配失败使用 perror 打印错误信息并调用 exit(1) 退出程序。调用 _MergeSort01 函数传入数组 a、临时数组 tmp 和整个数组的区间 [0, n - 1] 进行排序。排序完成后使用 free 释放 tmp 所占用的内存并设置 tmp 为 NULL。 归并排序的时间复杂度为 O(n log n)在大多数情况下表现良好尤其是当数据量大且需要稳定排序时。不过由于它需要额外的内存空间如这里的 tmp 数组在内存受限的情况下可能不是最佳选择。 递归排序非递归解决 前言 这里递归排序的非递归方式还是比较有难度的所以需要多次观看两遍我也会多次详细的讲解促进知识的理解 非递归实现gif 非递归实现单趟实现 这里的关键的在于对于区间的理解 尤其是 //但是此时可能产生越界行为,我们可以打印出来看一下 //产生越界的 //begin1, end1, begin2, end2 - end2-[,][,15] //begin1, end1, begin2, end2 - begin2, end2-[,][12,15] //begin1, end1, begin2, end2 - end1, begin2, end2-[,11][12,15] //解决 //begin2, end2区间越界的我们直接下一次进行递归就可以 //end2我们重新设定新的end2的区间 所以我们需要对这个区间进行解决 代码的逐步实现 这里代码的实现因为非递归实现是有难度的所以这里我不会直接给出答案而是逐步的写出步骤促进理解 1创建拷贝空间tmp设定gap一组假设初始1个数值当然初始的时候实际也是一个数值 //归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;
} 2区间的设定 这里依旧是两个区间我们根据这个区间设定的数值 这里是很关键的一点 int begin1 0, end1 0 gap - 1; int begin2 0 gap, end2 0 2 * gap - 1; //假设此时就两个数值一组是一个数值也就是这两个数值进行最小对比 //begin1左区间的初始位置肯定是0 //end1左区间的结束位置。 也就是第一个区间的结束位置也就是一组-1是因为一组是实际的个数0这里因为加的是第一个区间起始位置因为我们也可能是2-4区间的不可能只是这一个区间 //begin2第二个区间的起始位置这里还是比较好理解的只要理解了end1 //end2第二个区间的结束位置这里同理 我们有可能是2-4区间的不只是0-1或者0-2区间的。而且随着第一次排序的结束第二次排序就变成两个合并了继续和另外的对比所以是变化的0也就是初始位置2*gap因为这里是需要加上中间两组最后-1因为gap是个数不是下标 //归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;int begin1 0, end1 0 gap - 1;int begin2 0 gap, end2 0 2 * gap - 1;
} 3排序的实现
//归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;while (gap n){//递归到最小值,假设一组是一个,也就是此时是最小值进行比较并且入数组关键是找出区间//这里一次跳过两组for (int i 0; i n - 1; i i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 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];}}gap * 2;}
} 4区间的拷贝 这里区间的拷贝我们需要注意的是我们拷贝的是区间并且我们需要一边拷贝一边拷贝回去为什么需要一边排序一边拷贝回去在接下来的越界行为里面我们会进行讲解 最后需要关注的点是关于拷贝空间的大小一定是end2-begin1因为这两个区间是排序成功然后进入到tmp里面 所以我们需要从tmp拷贝回去不能弄错了
//归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;while (gap n){//递归到最小值,假设一组是一个,也就是此时是最小值进行比较并且入数组关键是找出区间//这里一次跳过两组for (int i 0; i n - 1; i i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 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数组里面,这里的区间是end2-begin1之间的区间memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}
} 5解决越界行为 这里我们可以很清楚的看到哪些位置会产生越界行为 这里我们处理一下之后我们发现就解决了 //产生越界的区间有 //begin1, end1, begin2, end2 - end2-[,][,15] //begin1, end1, begin2, end2 - begin2, end2-[,][12,15] //begin1, end1, begin2, end2 - end1, begin2, end2-[,11][12,15] //解决 //begin2, end2区间越界的我们直接下一次进行递归就可以 //end2我们重新设定新的end2的区间
//归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;while (gap n){//递归到最小值,假设一组是一个,也就是此时是最小值进行比较并且入数组关键是找出区间//这里一次跳过两组for (int i 0; i n - 1; i i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//但是此时可能产生越界行为,我们可以打印出来看一下//产生越界的//begin1, end1, begin2, end2 - end2-[,][,15]//begin1, end1, begin2, end2 - begin2, end2-[,][12,15]//begin1, end1, begin2, end2 - end1, begin2, end2-[,11][12,15]//解决//begin2, end2区间越界的我们直接下一次进行递归就可以//end2我们重新设定新的end2的区间printf([begin1%d,end1%d][begin2%d,end2%d]\n, begin1, end1, begin2, end2);if (begin2 n){break;}if (end2 n){//记得这里需要是n-1不能是n因为end2是下标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数组里面,这里的区间是end2-begin1之间的区间memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}
} 时间复杂度 时间复杂度分析如下 分解阶段归并排序首先将原始数组分解成多个子数组每个子数组的大小为1。这个过程是线性的时间复杂度为 O(n)其中 n 是原始数组的大小。 合并阶段在合并阶段算法将这些有序的子数组逐步合并成更大的有序数组。每次合并操作都需要将两个有序数组合并成一个更大的有序数组这个过程的时间复杂度是 O(n)。 重复合并归并排序的合并阶段会重复进行直到所有的元素都被合并成一个有序数组。合并的次数可以看作是对数级的具体来说是 log2(n) 次。 综合以上两点归并排序的总时间复杂度主要由合并阶段决定因为分解阶段是线性的而合并阶段虽然每次都是线性的但由于重复了对数级次数所以总的时间复杂度是 ()(log) 由于在大 O 符号中我们只关注最高次项和系数所以归并排序的时间复杂度通常被简化为(log) 这意味着归并排序的时间效率与数组的大小成对数关系是相当高效的排序算法。此外归并排序是一种稳定的排序算法它保持了相等元素的原始顺序。然而它需要与原始数组同样大小的额外空间来存储临时数组这可能会在空间受限的情况下成为一个问题。 代码实现
//归并排序非递归实现创建tmp函数
void MergeSort02(int* a, int n)
{//这里n传递过来的是个数int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(MergeSort01:tmp:err:);exit(1);//正常退出}//假设初始化起始是一组int gap 1;while (gap n){//递归到最小值,假设一组是一个,也就是此时是最小值进行比较并且入数组关键是找出区间//这里一次跳过两组for (int i 0; i n - 1; i i gap * 2){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//但是此时可能产生越界行为,我们可以打印出来看一下//产生越界的//begin1, end1, begin2, end2 - end2-[,][,15]//begin1, end1, begin2, end2 - begin2, end2-[,][12,15]//begin1, end1, begin2, end2 - end1, begin2, end2-[,11][12,15]//解决//begin2, end2区间越界的我们直接下一次进行递归就可以//end2我们重新设定新的end2的区间printf([begin1%d,end1%d][begin2%d,end2%d]\n, begin1, end1, begin2, end2);if (begin2 n){break;}if (end2 n){//记得这里需要是n-1不能是n因为end2是下标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数组里面,这里的区间是end2-begin1之间的区间memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}
} 解释 内存分配首先函数使用 malloc 分配一个与原数组 a 同样大小的临时数组 tmp。如果内存分配失败使用 perror 打印错误信息并调用 exit 退出程序。 初始化间隔gap 变量初始化为 1表示每个元素自身作为一个有序的子数组。 外层循环使用 while 循环来逐步增加 gap 的值每次迭代将 gap 乘以 2。这个循环继续进行直到 gap 大于或等于数组的长度 n。 内层循环对于每个 gap 值使用 for 循环遍历数组计算每次合并操作的起始索引 i。每次迭代i 增加 gap * 2以确保每次处理的子数组间隔是 gap。 计算子数组边界在每次迭代中计算两个子数组的起始和结束索引begin1、end1 和 begin2、end2。这两个子数组的间隔是 gap。 处理数组越界如果 begin2 大于数组长度 n循环将终止。如果 end2 超出了数组的界限将其调整为 n-1。 合并子数组使用 while 循环来合并两个子数组。比较 a[begin1] 和 a[begin2]将较小的元素复制到 tmp 数组中并相应地移动索引。当一个子数组的所有元素都被复制后使用另外两个 while 循环复制剩余子数组中的元素。 拷贝回原数组使用 memcpy 将 tmp 中的有序子数组复制回原数组 a。这里拷贝的区间是从索引 i 到 end2拷贝的元素数量是 end2 - i 1。 更新间隔外层循环的 gap 每次迭代后翻倍这样在每次迭代中处理的子数组的大小逐渐增加直到整个数组被排序。 非递归的归并排序在某些情况下可能比递归版本更有效因为它避免了递归调用的开销尤其是在深度很大的递归树中。然而它需要更多的迭代来逐步构建有序数组因此在实际应用中选择哪种实现取决于具体的需求和场景。 计数排序 前言 计数排序是速度特别快的一种排序方式甚至说可以达到on什么概念一趟就可以实现这是很快的虽然具备一定的局限性但是这个速度也是叹为观止的 计数排序gif 实现图解 这里的核心逻辑就在于我们需要入数组和出数组这两点 代码实现
//计数排序
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];}}//计算差值,需要最小值和最大值//0 1 2三个数值但是2-12也就是两个数值所以我们需要1 ,这个差值也就是我们开辟多大的空间int delta max - min 1;//创建数组空间int* tmp (int*)calloc(delta, sizeof(int));if (tmp NULL){perror(Countsort:tmp:err:);exit(1);//正常退出}//把原数组里面的数值计算之后-存放到tmp数组里面,但是需要控制差值存放在数组里面for (int i 0; i n; i){tmp[a[i] - min];}//从数组读取出放到原数组里面int j 0;for (int i 0; i delta; i){while (tmp[i]--){a[j] i min;}}
} 解释 求最小值和最大值 首先初始化 max 和 min 为数组的第一个元素的值。遍历整个数组 a更新 max 和 min 为数组中的最大值和最小值。 计算差值 计算最大值和最小值的差值 delta这个差值加1后将用于确定计数数组 tmp 的大小。 创建计数数组 使用 calloc 分配一个大小为 delta 的数组 tmp并将所有元素初始化为0。calloc 会初始化分配的内存为0这对于计数排序是必要的。 计数 遍历原数组 a对于数组中的每个元素 a[i]计算其与最小值 min 的差值并在 tmp 数组的相应位置增加计数。例如如果 a[i] 是3且 min 是0则 tmp[3] 会增加1。 输出排序结果 使用两个指针 i 和 ji 用于遍历 tmp 数组j 用于指向原数组 a 的当前位置。对于 tmp 数组中的每个非零元素将其对应的值加回到原数组 a 中直到 tmp[i] 减至0。这意味着将 min i 赋值给 a[j]然后 j 增加重复这个过程直到 tmp[i] 为0。 结束排序 当所有计数都减至0时原数组 a 已经是部分有序的排序完成。 错误处理 如果 calloc 分配内存失败使用 perror 打印错误信息并调用 exit 退出程序。 计数排序的时间复杂度是 O(n k)其中 n 是数组 a 的长度k 是整数的范围在这个例子中是 delta。由于 k 通常远小于 n计数排序对于大量数据的排序非常高效。然而计数排序的空间复杂度也是 O(k)如果整数的范围非常大它可能需要大量的内存。 计数排序是一种稳定的排序算法它不会改变相等元素的相对顺序。它特别适用于当数据范围不大且数据量很大时的场景。 时间复杂度 寻找最大值和最小值遍历整个数组以找到最大值和最小值这个过程的时间复杂度是 O(n)其中 n 是数组中元素的数量。 创建计数数组使用 calloc 为计数数组分配内存并初始化这个操作的时间复杂度是 O(k)其中 k 是最大值和最小值的差值加 1即整数的范围。 计数再次遍历数组将每个元素的计数在计数数组中增加。这个过程的时间复杂度也是 O(n)。 输出排序结果最后根据计数数组重建排序后的数组。这个过程涉及遍历计数数组并且对于每个非零计数将对应的元素值放入原数组中。如果计数数组中的非零元素数量接近 n则这个操作的时间复杂度接近 O(n)。 综合上述步骤计数排序的总时间复杂度主要由以下两个 O(n) 操作决定 寻找最大和最小值计数和输出排序结果 因此计数排序的总时间复杂度是 O(n k)。然而实际上当 k整数的范围远小于 n 时k 可以被视为一个常数所以时间复杂度可以简化为 O(n)。但是如果 k 很大接近或大于 n时间复杂度就接近 O(n k)。 计数排序的空间复杂度是 O(k)因为需要额外的计数数组来存储每个可能整数的出现次数。如果 k 非常大这可能会成为一个问题。 堆排序 前言 堆排序是速度很快的一种排序方式尤其是处理大数据的情况下这个堆排序展现了无与伦比的速度当然这里比较吃二叉树篇章所以我放在了最后要是有二叉树理解不深入的可以看一下这个博客基本上看完之后就没有问题了 数据结构-二叉树系统性学习四万字精讲拿捏-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/138799868 需要在数组里面进行排序我们可以采取堆排序对其解决问题 版本1 创建一个数组等大的堆把数组里面的数值输入到堆里面进行堆排序但是这样的弊端就是不是顺序排序 版本2 每次我们取堆顶然后打印最后出堆循环 弊端就是这样是时间复杂度我们发现还是o(n)没有必要那么麻烦半天时间复杂度还是这样 版本3:推荐 在数组上面进行排序直接输出顺序排序 逻辑讲解 1需要在数组里面进行排序我们可以采取在数组建堆 2然后交换收尾元素每次调整的数值减少1 讲解逻辑 首先我们需要知道 如果我们需要排序的是降序我们就需要建立小堆 如果我们需要排序的是升序我们就需要建立大堆 如果我们需要的是升序建立小堆的话 如果我们采取相反的方式的话就会导致出现两个根 首先n个数建小堆固定第一个值是最小值 剩下的n-1个数再建堆 效率就很差了 如果相反的话会导致根节点变化从而导致逻辑混乱数组里面的数值少的时候是不明显的但是多的时候就不行了 逻辑实现图解 代码实现 //向下调整大堆
void AdjustDown(HPDataType* a, int n, int parent)
{int chile parent * 2 1;//循环条件不能是父亲不然会导致越界while (chile n){//三个孩子进行比较if (chile 1 n a[chile] a[chile 1]){chile;}if (a[chile] a[parent]){Swap(a[chile], a[parent]);parent chile;chile parent * 2 1;}else{break;}}
}
//堆排序数组内进行调整解决
void sort_test(int* a, int sz)
{//放出来的是小堆所以我们只能排序降序这样逻辑更融洽//建堆for (int i 0; i sz; i){AdjustUp(a, i);}//交换排序 把首个元素和最后一个交换进行排序 每次--while (sz 0){Swap(a[0], a[sz - 1]);AdjustDown(a, sz - 1, 0);sz--;}
} 这个 sort_test 函数实现了一个堆排序算法它接收一个整数数组 a 和它的大小 sz 建堆首先函数通过调用 AdjustUp 函数来构建一个小顶堆最小堆。建堆过程是从最后一个非叶子节点开始向上调整直到堆顶。 交换和排序在建堆之后函数进入一个循环每次循环中它将堆顶元素当前堆中的最小元素与当前堆的最后一个元素交换。然后堆的大小减少 1并且对剩余的堆进行向下调整以保持最小堆性质。 循环结束循环继续进行直到堆的大小减小到 0。最终数组 a 将被排序为降序 堆排序衍生的top_k问题 前言 这里本质还是堆排序的衍生问题 也就是还是堆排序问题我们最终需要学习的就是处理大型数据的问题 top_k问题时间复杂度的计算 这里提前说明时间复杂度的计算的目的是来计算向上调整的更优还是向下调整更优从肉眼看的话向下调整优于向上调整接下来我们进行时间复杂度的计算。 此时我们会用到等比数列求和以及裂项相消 首先我们需要我们建堆的时候是向上调整还是向下调整 如图详解 首先我们假设求的是满二叉树我们求节点的个数 满二叉树节点个数 建堆问题 建堆的话往往的倒数第一个非叶子结点建堆会时间复杂度最优解也就是 在构建堆尤其是二叉堆时从最后一个非叶子节点开始进行调整是时间复杂度最优解的原因是这种方法可以减少不必要的调整操作。 为什么从最后一个非叶子节点开始 叶子节点在完全二叉树中叶子节点不包含任何子节点因此不需要进行调整。 非叶子节点从最后一个非叶子节点开始向上逐个进行调整可以确保每个节点在调整时其子树已经是堆结构。这样可以减少调整的深度因为每个节点最多只需要与其子节点交换一次。 减少调整次数如果从根节点开始调整那么每个节点可能需要多次调整才能达到堆的性质特别是那些位于树底部的节点。而从底部开始每个节点只需要调整一次即可。 时间复杂度分析 构建堆的过程涉及对每个非叶子节点进行调整。对于一个具有 n 个节点的完全二叉树 叶子节点有 ⌈/2⌉个叶子节点它们不需要调整。 非叶子节点有 ⌊/2⌋个非叶子节点需要进行调整。 对于非叶子节点从最后一个非叶子节点开始向上调整每个节点最多只需要进行 loglogkk 是节点的深度次交换。但是由于树的结构底部的节点不需要进行多次交换因此整个调整过程的时间复杂度比 (log) 要低。 实际上构建堆的时间复杂度是 ()这是因为 从最后一个非叶子节点开始每个节点的调整次数与其深度成反比。 根节点的调整次数最多但只需要一次。 越往下节点的深度越小但需要调整的节点数量越多。 总结 从最后一个非叶子节点开始建堆可以确保每个节点的调整次数与其深度成反比从而减少总的调整次数。这种方法利用了完全二叉树的性质使得整个建堆过程的时间复杂度达到最优即 ()。这是构建堆的最优策略因为它最小化了必要的调整操作从而提高了算法的效率。 建堆复杂度讲解向下调整建堆计算 如图 这里为什么-2呢因为我们的向下调整只是调整h-1层第h层的节点的个数是2^h-1所以第h-1层自然就是-2 所以我们发现建堆的时候我们h-1高度的节点的个数相加得出的结果 为T(n) 所以我们进行计算 从而得出时间复杂度为什么时间复杂度是高度因为向下调整的时候我们循环终止条件是循环的高度也就是当父亲节点不小于sz的时候所以计算出高度也就计算出了时间复杂度 建堆复杂度讲解向上调整建堆计算 如图 计算图解 所以我们得出结论这里多了n次 对比 向上调整AdjustUp和向下调整AdjustDown的时间复杂度通常与堆的高度相关即 log其中 k 是堆中元素的数量。然而在特定情况下特别是在构建堆的过程中这些操作的总时间复杂度可以是 ()这里的 是堆中元素的数量。 单个操作的时间复杂度 向上调整 (AdjustUp)对于单个元素向上调整的时间复杂度是 (log)因为它可能需要从叶子节点一直调整到根节点最多涉及 log层的比较和交换。 向下调整 (AdjustDown)同样对于单个元素向下调整的时间复杂度也是 (log)因为它可能需要从根节点调整到叶子节点同样最多涉及 log层的比较和交换。 构建堆的总时间复杂度 当我们讨论构建一个包含 个元素的堆时所有元素的向上调整操作的总时间复杂度是 ()。这是因为 树的非叶子节点大约是 /2因为叶子节点也是 /2 左右。 每个非叶子节点的调整操作最多涉及 log 的时间但是由于树的结构从根到叶的路径上的节点数量总和大致是 n。 因此所有节点的向上调整操作加起来的时间复杂度是 ()。 为什么是 () 而不是 (log) 树的结构特性在完全二叉树中每个层级的节点数量是指数增长的。从根节点1个节点到第二层2个节点再到第三层4个节点等等。因此较低层级的节点数量远多于较高层级的节点数量。 调整深度根节点的调整可能需要 log 的时间但较低层级的节点只需要较少的调整时间。由于底部层级的节点数量较多它们较短的调整时间在总体上对总时间复杂度的贡献较小。 总结 对于单个元素向上调整和向下调整的时间复杂度是 (log) 在构建堆的过程中所有元素的向上调整操作的总时间复杂度是 ()而不是 (log)这是由于完全二叉树的结构特性和调整操作的分布。 因此向上调整和向下调整在构建堆的过程中的总时间复杂度是 ()而不是 (log)。这个线性时间复杂度是构建堆算法的一个重要特性使得它在处理大量数据时非常高效。 向上调整和向下调整虽然最后计算的都是O(N) 但是满二叉树最后一层占据一半的节点 所以我们得出结论向下调整的复杂度优于向上调整的复杂度 top_k问题的实现逻辑 1首先我们创建一个文件写入随机数值1000w个 2如果需要读取文件里面最大的10个数值那么我们就需要创建一个小堆 原因 这样的话输入数值的时候如果读取的数值比堆顶大就会替换堆顶从而进堆然后进行堆排序。 3在读取文件的时候我们需要读取一个接收一个然后进行数值的对比从而进行交换。 4最后打印最大的数值 5备注我们如何判断我们的找到的最大的前十个数值的正确的 也是很简单的我们设定的随机数值是10000以内的然后设定完之后我们不调用进入TXT里面更改一些数值。设定一些大于一万的数值此时我们就可以发现我们筛选的数值对不对。 当然如果我们需要找最小的数值那么我们设定数值最好为-1因为十万个数值很可能是有很多0的。但是我们肉眼看不出来。 top_k计算的代码实现 //进行计算
void TOP_K()
{int k 10;//scanf(%d, k);FILE* ps fopen(data.txt, r);if (ps NULL){perror(Error:opening:file);exit(1);}//创建空间存储int* tmp (int*)malloc(sizeof(int) * k);if (tmp NULL){perror(TOP_K():Heap* tmp:error);exit(1);}//读取个数for (int i 0; i 10; i){fscanf(ps, %d, tmp[i]);}// 建堆,从最后一个非叶子节点开始建堆,// 这里的 -1-1 实际上看起来像是一个错误。// 通常当我们需要找到最后一个非叶子节点的索引以开始建堆过程时我们会从倒数第二个节点开始因为数组索引从0开始。对于大小为 k 的数组最后一个非叶子节点的索引计算如下// 简单的说就是k是数值我们需要传参传递是下标找到父亲节点需要减去1 除以2 所以就有了-2的情况for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(tmp, k, i);}//排序int val 0;int ret fscanf(ps, %d, val);while (ret ! EOF){if (tmp[0] val){tmp[0] val;AdjustDown(tmp, k, 0);}ret fscanf(ps, %d, val);}//打印for (int i 0; i k; i){printf(%d , tmp[i]);}fclose(ps);} top_k完整代码 //TOP_K问题的实现 小堆寻找最大值
//创建随机数值
void TOP_K_fopen_w()
{FILE* ps fopen(data.txt, w);if (ps NULL){perror(FILE* ps :fopen:error);exit(1);}srand(time(0));for (int i 0; i 100000; i){int s rand() % 10000;fprintf(ps, %d\n, s);}fclose(ps);
}
//进行计算
void TOP_K()
{int k 10;//scanf(%d, k);FILE* ps fopen(data.txt, r);if (ps NULL){perror(Error:opening:file);exit(1);}//创建空间存储int* tmp (int*)malloc(sizeof(int) * k);if (tmp NULL){perror(TOP_K():Heap* tmp:error);exit(1);}//读取个数for (int i 0; i 10; i){fscanf(ps, %d, tmp[i]);}// 建堆,从最后一个非叶子节点开始建堆,// 这里的 -1-1 实际上看起来像是一个错误。// 通常当我们需要找到最后一个非叶子节点的索引以开始建堆过程时我们会从倒数第二个节点开始因为数组索引从0开始。对于大小为 k 的数组最后一个非叶子节点的索引计算如下// 简单的说就是k是数值我们需要传参传递是下标找到父亲节点需要减去1 除以2 所以就有了-2的情况for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(tmp, k, i);}//排序int val 0;int ret fscanf(ps, %d, val);while (ret ! EOF){if (tmp[0] val){tmp[0] val;AdjustDown(tmp, k, 0);}ret fscanf(ps, %d, val);}//打印for (int i 0; i k; i){printf(%d , tmp[i]);}fclose(ps);} 解释 TOP_K_fopen_w 函数 这个函数用于生成随机数据并写入到 data.txt 文件中。使用 fopen 打开文件如果失败则打印错误并退出程序。使用 srand 和 time 初始化随机数生成器的种子。循环生成100000个0到9999之间的随机整数并使用 fprintf 将它们写入文件每个数字一行。最后使用 fclose 关闭文件。 TOP_K 函数 首先定义了要找出的最大的数的个数 k这里设置为10。使用 fopen 打开 data.txt 文件进行读取如果失败则打印错误并退出程序。分配一个大小为 k 的数组 tmp 用于存储小顶堆的元素。读取前10个数字存入 tmp 数组中这里假设文件中的数字至少有10个。 建堆 从最后一个非叶子节点开始调整堆以确保 tmp 数组是一个有效的小顶堆。这里的注释提到 -1-1 实际上看起来像是一个错误但实际上计算最后一个非叶子节点的索引是正确的。对于大小为 k 的完全二叉树最后一个非叶子节点的索引是 (k - 2) / 2。这里的计算 (k - 1 - 1) / 2 实际上得到的是倒数第二个非叶子节点的索引使用 AdjustDown 函数从最后一个非叶子节点开始向下调整堆确保堆的性质。 排序 使用 fscanf 从文件中读取数字直到文件结束EOF。对于每个读取的数字如果它大于堆顶即 tmp[0]则替换堆顶元素并调用 AdjustDown 函数向下调整堆。这个过程确保了 tmp 数组中始终存储着当前读取到的最大的K个数。 打印结果 循环打印 tmp 数组中的所有元素这些元素就是最大的K个数。使用 fclose 关闭文件。 注意 代码中没有提供 AdjustDown 函数的实现这个函数用于向下调整堆以保持堆的性质。代码假设文件中的数字数量至少为10如果少于10个需要额外的错误处理。代码中没有考虑内存分配失败的情况实际使用中应该检查 malloc 的返回值。 整体上这段代码展示了如何使用小顶堆来解决TOP-K问题通过维护一个大小为K的最小堆可以有效地找到数据流中最大的K个数。
