自已建网站,传奇网站传奇,中国原材料价格网,网站优化需要上集回顾
排序学习整理#xff08;1#xff09;-CSDN博客
2.3 交换排序 交换排序的基本思想是#xff1a;根据序列中两个记录键值的比较结果#xff0c;交换这两个记录在序列中的位置。 特点#xff1a;
通过比较和交换操作#xff0c;将键值较大的记录逐步移动到序列…上集回顾
排序学习整理1-CSDN博客
2.3 交换排序 交换排序的基本思想是根据序列中两个记录键值的比较结果交换这两个记录在序列中的位置。 特点
通过比较和交换操作将键值较大的记录逐步移动到序列的尾部而键值较小的记录逐步移动到序列的前部。重复此过程直到整个序列变得有序。
2.3.1 冒泡排序
冒泡排序Bubble Sort是一种简单的交换排序算法其核心思想是通过重复的比较和交换操作将序列中的最大值或最小值逐步“冒泡”到序列的尾部或头部。
基本思想 从序列的起始位置开始依次比较相邻的两个元素 如果它们的顺序不正确如升序时前一个大于后一个则交换它们的位置。 一轮比较后当前未排序部分的最大值会被“冒泡”到末尾。 对剩下的未排序部分重复上述过程直到整个序列有序。 算法步骤
初始化一个外层循环用来控制需要比较的轮数。在每轮循环中从序列的开头开始逐一比较相邻的两个元素完成交换。每轮排序结束后未排序部分的长度减1。重复上述操作直到不需要再比较。 代码实现
void BubbleSort(int* arr, int n) {for (int i 0; i n - 1; i) { // 控制排序轮数int swapped 0; // 标记本轮是否发生交换for (int j 0; j n - 1 - i; j) { // 控制每轮比较次数if (arr[j] arr[j 1]) { // 如果顺序不正确int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;swapped 1; // 标记发生了交换}}if (!swapped) { // 如果本轮没有交换说明已经有序break;}}
}特性总结 算法复杂度
时间复杂度 最好情况序列已排序O(n)最坏情况序列逆序O(n^2)平均情况O(n^2)空间复杂度只需要常数级额外空间空间复杂度为 O(1)。稳定性冒泡排序是稳定的排序算法因为在比较相等元素时它不会改变它们的相对位置。 优缺点和适用场景就不介绍了冒泡的效率太过于低下基本只用于教学了
2.3.2 快速排序 基本思想是从待排序序列中随机选取一个元素作为基准值依据该基准值将序列划分为两个子序列其中左子序列的所有元素都小于基准值右子序列的所有元素都大于基准值。然后对左右子序列分别重复这一过程直到所有元素都排列到正确的位置上为止。 快速排序实现的主框架
//快速排序
void QuickSort(int* a, int left, int right){if (left right) {return;}//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分int meet _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet 1, right);
}
主要有以下几种实现方法
2.3.2.1 hoare版本
Hoare版本的快速排序是由算法提出者Tony Hoare在1962年设计的一种经典快速排序实现。该版本利用分区的思想将数组分成两部分使得一部分元素小于基准值另一部分元素大于基准值。随后对两部分递归地应用快速排序直到数组有序。
基本思想 核心操作是“分区”使用左右指针分别从两端向中间扫描找到需要交换的元素位置最终将数组划分为左右两部分。 Hoare版本的快速排序通过分区的思想将数组分成两部分 左子数组中的元素均小于等于基准值。右子数组中的元素均大于等于基准值。 采用递归或迭代方式对子数组继续进行快速排序直到子数组长度为1或0排序完成。
算法步骤
选择基准值 通常选择当前子数组的第一个元素作为基准值。分区 设置左右两个指针分别指向当前子数组的两端。右指针向左移动找到第一个小于等于基准值的元素。左指针向右移动找到第一个大于等于基准值的元素。如果左右指针未交错交换两指针指向的元素继续移动指针。当左右指针交错时分区完成并返回分界点。递归排序 将数组按照分界点划分为左右两部分。分别对左右部分递归执行上述过程直到子数组长度为1或0。 问题1为什么跳出循环后right位置的值⼀定不大于key 当 left right 时右指针right已经移动到了左指针left的左侧。由于在分区过程中左指针从左到右扫描的所有数据均不大于基准值key因此跳出循环时右指针right所指向的数据一定不大于基准值key。 问题2为什么left 和 right指定的数据和key值相等时也要交换 相等的值参与交换确实有一些额外消耗但在实际中数组可能存在大量重复元素如果相等的值不参与交换可能导致分区无法有效进行从而影响排序的正确性和效率。 代码实现
// 交换函数
void Swap(int* p1, int* p2) {int tmp *p1;*p1 *p2;*p2 tmp;
}
// 快速排序
void QuickSort(int* a, int left, int right) {if (left right) { // 递归边界条件区间只有一个元素或无元素return;}int begin left, end right; // 记录当前区间int keyi left; // 基准值初始为第一个元素的下标while (left right) {// 从右向左寻找比基准值小的元素while (a[right] a[keyi] left right) {right--;}// 从左向右寻找比基准值大的元素while (a[left] a[keyi] left right) {left;}// 交换左右指针指向的值Swap(a[left], a[right]);}// 基准值归位Swap(a[left], a[keyi]);keyi left; // 更新基准值位置// 对左右两部分递归排序QuickSort(a, begin, keyi - 1); // 左部分QuickSort(a, keyi 1, end); // 右部分
}
特性总结
算法复杂度
时间复杂度 最好情况O(n logn)每次分区都能平均划分为两半。 最坏情况O(n^2)当基准值总是选择到最小或最大值时分区极不均衡。 平均情况O(n logn)这是快速排序的典型表现。
空间复杂度 O(logn)递归调用栈的深度。 优缺点
优点
时间复杂度低平均性能优于大多数排序算法适合大规模数据。原地排序不需要额外的内存仅递归栈空间。实现简单通过分区逻辑实现高效的递归。
缺点
不稳定相同元素的相对顺序可能改变。最坏情况效率低对于完全有序或接近有序的数据性能可能退化为O(n^2)。递归调用栈问题当数据规模过大时递归调用深度可能导致栈溢出。 适用场景
大规模数据排序快速排序在大数据场景下表现良好。对稳定性无要求的场景例如数字或字符排序。通用排序需求适合随机分布的无序数据集。
很明显的缺点不少接下来介绍针对不同情况优化的另外三种快排 2.3.2.2 挖坑法
挖坑法也称为坑填法或坑填交换法是一种在排序算法中常用的技巧特别是在快速排序和堆排序等算法的实现中。常用于处理两个元素交换问题并且通常配合双指针或者分区操作来完成排序。
挖坑法在大量重复元素的情况下能减少交换次数因此在这些场景下的优化效果明显。
基本思想 在元素交换过程中使用一个临时“坑”来存储一个元素的值避免出现直接交换时元素覆盖的情况。这使得元素能够顺利地放到正确的位置并且交换过程更加高效。 在快速排序的分区操作中使用两个指针分别从两端扫描遇到需要交换的元素时利用“坑”存储其中一个元素等另一个元素找到合适位置后再进行交换。最终基准值会被放置到“坑”中实现正确的分区。 算法步骤
选择基准值选择一个元素作为基准值通常是第一个元素或随机选择一个。左右指针扫描 右指针从右侧开始向左扫描找到一个小于等于基准值的元素。 左指针从左侧开始向右扫描找到一个大于等于基准值的元素。
交换元素 如果左指针和右指针没有交错就交换这两个元素。 交换时使用一个临时“坑”来存放其中一个元素的值避免覆盖问题。
继续扫描重复步骤2和步骤3直到左右指针交错。放置基准值当左右指针交错时将基准值放入当前“坑”位置即完成分区。递归排序对左右两部分继续递归执行快速排序。 代码实现
void QuickSort(int* a, int left, int right) {if (left right) {return; // 当区间为空或只有一个元素时递归结束}int begin left;int end right;int keyi a[left]; // 基准值while (left right) {// 从右向左寻找比基准值小的数while (a[right] keyi left right) {right--;}if (left right) {a[left] a[right]; // 填坑}// 从左向右寻找比基准值大的数while (a[left] keyi left right) {left;}if (left right) {a[right] a[left]; // 填坑}}// 最后将基准值填入当前坑位a[left] keyi;// 对左右区间递归排序QuickSort(a, begin, left - 1); // 左区间QuickSort(a, left 1, end); // 右区间
}复杂度优缺点什么的和hoare版差不多就介绍下与hoare法相对的优化情况吧 减少了交换次数Hoare法在某些情况下需要交换多个位置尤其是当扫描到不满足条件的元素时。挖坑法则通过填坑和直接交换使得不需要频繁交换进一步提升了效率。 保持数据的稳定性挖坑法对于数据的处理方式相对较为稳定避免了一些冗余的交换且能够使得算法执行过程中更有序。 提高了数据的分区效果挖坑法有助于实现更平衡的分区尤其是在遇到重复元素或者大范围的相同值时能够更均匀地进行分割。由于它通过“填坑”的方式保持了分区的连续性因此在数据比较“均匀”的情况下能够带来较好的分割效果。 2.3.2.3 前后指针法
前后指针法Two-pointer technique是一种常用的技术通常用于排序算法中的分区操作特别是在快速排序的分区阶段。它通过设置两个指针从数组的两端向中间扫描逐步找到需要交换的位置从而实现分区操作。
前后指针法对于提高交换效率和减少不必要的交换有很大帮助尤其是在数据量大且分布不均匀时
基本思想 使用两个指针一个从数组的左端开始前指针另一个从数组的右端开始后指针。前指针向右扫描直到找到一个大于等于基准值的元素后指针向左扫描直到找到一个小于等于基准值的元素。当前指针小于后指针时交换这两个元素。交换后继续移动两个指针直到指针交错或相遇。当指针交错时结束扫描将基准值放到指针交错的位置完成分区。 算法步骤
选择基准值选择一个基准值通常选择数组的第一个元素或者最后一个元素。初始化指针设置两个指针前指针left指向数组的起始位置后指针right指向数组的结束位置。扫描交换 前指针从左向右扫描找到第一个大于等于基准值的元素。后指针从右向左扫描找到第一个小于等于基准值的元素。如果前指针小于后指针则交换这两个元素继续扫描。基准值放置当指针交错或相遇时将基准值放入指针交错的位置实现分区。递归排序对左侧和右侧子数组进行递归排序。
代码实现
Swap函数和上面的一样就不再水一次了
void QuickSort(int* a, int left, int right) {// 如果区间无效或只剩一个元素直接返回if (left right) {return;}// 设置初始基准值的位置选取左边的元素作为基准值int prev left; // prev 用于标记小于基准值的区域的末尾位置int cur prev 1; // cur 用于遍历数组int pivotIndex left; // 基准值的位置初始化为左边界// 遍历整个区间进行分区while (cur right) {// 如果当前元素小于基准值并且 prev 位置还没有与 cur 交换if (a[cur] a[pivotIndex] prev ! cur) {// 如果符合条件则交换 a[prev] 和 a[cur]Swap(a[prev], a[cur]);}cur; // 继续向右移动 cur 指针}// 最后将基准值与 prev 位置的元素交换将基准值放到正确的位置Swap(a[prev], a[pivotIndex]);pivotIndex prev; // 更新基准值位置// 递归处理左右两个子区间QuickSort(a, left, pivotIndex - 1); // 处理左区间QuickSort(a, pivotIndex 1, right); // 处理右区间
}
算法复杂度和优缺点一样继续与hoare同优化在于 减少了交换次数在Hoare法中当左右指针扫描时可能会在每次比较时都进行交换。而前后指针法则是只在需要时才交换并且扫描过程是从两端开始的能够更高效地找到合适的交换元素。 提高了分区效率前后指针法可以确保左右指针每次都能找到需要交换的元素因此比传统的Hoare法可能更快地将数据分割为两部分。这种方法避免了多个不必要的交换提高了分区的速度。 优化情况当数据的顺序比较混乱或者大部分元素都较接近基准值时前后指针法能够更有效地进行数据分割减少了不必要的比较和交换操作。 2.3.2.4 非递归版本
饺子醋来咯尝试尽量讲清楚
首先这个版本需要栈来实现学了栈再来先上官方一点的介绍 传统的快速排序算法通常使用递归来实现分区和排序操作但在某些情况下例如当递归深度过大时可能导致栈溢出可以使用非递归版的快速排序来避免递归带来的开销。非递归版快速排序使用显式的栈来模拟递归的调用借助栈保存子数组的边界逐步进行分区和排序。 非递归版则主要解决了递归带来的栈溢出问题适合处理大规模数据或栈空间受限的情况但对于排序速度并没有显著提高。
基本思想
非递归版快速排序的基本思想是 使用栈代替递归的调用栈通过显式地维护子数组的起始和结束位置。每次分区操作后将新的左右子数组的边界压入栈中继续分区直到栈为空。由于栈模拟了递归过程因此在内存方面比传统递归方法更加高效。 算法步骤
初始化栈初始化一个栈用来存储子数组的左右边界。压入初始边界将整个数组的左右边界压入栈中即初始的低位和高位。分区操作 从栈中弹出一个子数组的边界即子数组的左端点和右端点。对该子数组进行分区操作将其分为两个部分基准值将放在正确位置。压入子数组的边界根据分区结果将两个子数组的边界压入栈中继续分区。循环直到栈为空重复上述步骤直到栈为空即所有子数组都被处理完。
其实就记住这个操作就好了取栈顶区间单趟排序右左子区间入栈不断重复及完成了整个函数。 代码实现
void QuickSortNonR(int* a, int left, int right) {ST st;STInit(st); // 初始化栈STPush(st, right); // 将右边界入栈STPush(st, left); // 将左边界入栈// 循环栈中的区间进行排序while (!STEmpty(st)) {int begin STTop(st); // 获取当前区间的左边界STPop(st); // 弹出左边界int end STTop(st); // 获取当前区间的右边界STPop(st); // 弹出右边界int keyi begin; // 选择基准元素的初始位置int cur begin 1; // 当前元素指针int prev begin; // 上一个小于基准元素的位置// 对区间内的元素进行排序while (cur end) {if (a[cur] a[keyi] prev ! cur) // 如果当前元素小于基准元素则交换Swap(a[prev], a[cur]);cur;}// 将基准元素放到正确的位置Swap(a[keyi], a[prev]);keyi prev; // 更新基准元素位置// 如果基准元素右边还有元素继续排序右边区间if (keyi 1 end) {STPush(st, end);STPush(st, keyi 1);}// 如果基准元素左边还有元素继续排序左边区间if (keyi - 1 begin) {STPush(st, keyi - 1);STPush(st, begin);}}STDestroy(st); // 销毁栈
}
栈实现的代码拿的是自己上次的栈的实现基础-CSDN博客
特性总结
算法复杂度
时间复杂度不变空间复杂度正常也是 O(logn)但在最坏情况有序或接近有序会到O(n) 优缺点
优点
避免栈溢出非递归版的快速排序通过显式的栈来模拟递归避免了因递归深度过大而导致栈溢出的风险。节省栈空间在递归方法中栈的空间随着递归深度的增加而增加而非递归版的快速排序通过显式栈管理节省了递归栈空间。
缺点
代码复杂度增加非递归版的快速排序实现需要额外的栈结构来模拟递归增加了代码的复杂性。空间开销尽管非递归版避免了递归栈的开销但仍然需要额外的栈空间来存储子数组的边界尤其对于大数组时空间开销可能较大。 适用场景
递归深度较大时当数据集非常大或递归深度较深时非递归版快速排序通过避免栈溢出使得排序过程更稳定。内存限制如果系统的栈空间有限递归深度可能会导致栈溢出此时非递归版更为适用。需要改进性能的应用场景对于一些对性能要求较高的应用避免递归栈开销可能会带来一定的性能提升。
2.3.2.5 优化方法
2.3.2.5.1 三数取中
这个方法针对前面4种都不利的有序数组从这个角度出发我们有了三数取中的优化方式
即选出mid(leftright)/2
a[left]、a[right]、a[mid]这三个数中值为中位数的那个数然后将它于a[keyi]交换。
下面代码基于前后指针法
// 三数取中法
int GetMidi(int* a, int begin, int end) {// 计算中间元素的索引int mid begin ((end - begin) 1);// 判断mid元素是否在begin和end之间即a[mid] 是位于 [a[begin], a[end]] 之间if ((a[mid] a[begin] a[mid] a[end]) || (a[mid] a[end] a[mid] a[begin])) {return mid; // 如果mid符合条件返回mid的索引}// 如果a[begin]比a[mid]大且a[begin]比a[end]小或者a[begin]比a[mid]小且a[begin]比a[end]大if ((a[begin] a[mid] a[begin] a[end]) ||(a[begin] a[mid] a[begin] a[end])) {return begin; // 返回begin的索引}// 默认返回end的索引return end;
}// 快速排序主函数
int QuickSort(int* a, int begin, int end) {// 三数取中法优化选择begin, mid, end三个元素的中位数作为基准元素int ki GetMidi(a, begin, end); // 获取中位数元素的索引Swap(a[begin], a[ki]); // 将中位数元素与begin位置的元素交换int keyi begin; // keyi是基准元素的初始位置int prev begin; // prev是扫描过程中已排序元素的最右边的位置int next begin 1; // next是当前扫描到的元素位置// 前后指针法进行分区操作while (next end) {// 如果当前元素小于基准元素交换到prev位置并更新prev的位置if (a[next] a[keyi] prev ! next) {Swap(a[prev], a[next]);}next; // 移动next指针扫描下一个元素}// 将基准元素放到正确的位置即prev位置并返回基准元素的位置Swap(a[keyi], a[prev]);return prev; // 返回基准元素的最终位置
}注释这么详细就不用额外介绍了吧
来下一个优化
2.3.2.5.2 小区间优化
当区间很小时直接采用插入排序就不用继续递归了。
void QuickSort(int* a, int left, int right)
{// 如果区间内的元素只有一个或没有直接返回因为已经是最小子问题即已经排好序if (left right)return;// 对于小区间小于10个元素使用插入排序可以减少递归深度提高效率if (right - left 1 10){InsertSort(a left, right - left 1); // 对[aleft, right]区间的元素进行插入排序}else{int begin left, end right;int midi GetMidi(a, left, right); // 获取三数取中的基准索引Swap(a[left], a[midi]); // 将基准元素交换到left位置// 定义keyi为基准元素的索引进行分区操作int keyi left;// 进行前后指针法分区while (left right){// 从右边开始找一个小于基准的元素while (left right a[right] a[keyi]){--right; // right指针向左移动}// 从左边开始找一个大于基准的元素while (left right a[left] a[keyi]){left; // left指针向右移动}// 找到符合条件的元素后交换Swap(a[left], a[right]);}// 将基准元素放到正确的位置即left位置完成分区Swap(a[left], a[keyi]);keyi left;// 递归调用对左右子数组进行排序QuickSort1(a, begin, keyi - 1); // 对左子数组进行排序QuickSort1(a, keyi 1, end); // 对右子数组进行排序}
}下一篇就讲归并排序和非比较排序吧估计不长了
