如何在网站上做支付功能,大连网络公司排名,wordpress 页面 评论,如何做各大网站广告链接前言 快排是很重要的排序#xff0c;也是一种比较难以理解的排序#xff0c;这里我们会用递归的方式和非递归的方式来解决#xff0c;递归来解决是比较简单的#xff0c;非递归来解决是有点难度的 快排也称之为霍尔排序#xff0c;因为发明者是霍尔#xff0c;本来是命名… 前言 快排是很重要的排序也是一种比较难以理解的排序这里我们会用递归的方式和非递归的方式来解决递归来解决是比较简单的非递归来解决是有点难度的 快排也称之为霍尔排序因为发明者是霍尔本来是命名为霍尔排序的但是霍尔这个人对于自己创造的排序很自信所以命名为快排 当然也是如他所料快排确实很快但是还没有达到第一批次那个程度 快排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的数据结构所以先入栈的是右侧区间后入栈的是左侧区间这样在出栈时会先处理左侧区间再处理右侧区间。销毁栈循环结束后销毁栈。 这种非递归实现的快速排序算法利用了栈的特性来避免递归调用从而减少了函数调用的开销并且在处理大数据集时可以避免递归深度过大导致的栈溢出问题。
