常见的网站空间,免费咨询聊天,怎么做外贸电商,wordpress 在线手册快速排序
快速排序是一种高效的排序算法#xff0c;它采用分治法策略#xff0c;将数组分为较小和较大的两个子数组#xff0c;然后递归排序两个子数组。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法#xff0c;其基本思想为#xff1a;任取待排序元素序…
快速排序
快速排序是一种高效的排序算法它采用分治法策略将数组分为较小和较大的两个子数组然后递归排序两个子数组。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序递归实现的主框架与二叉树前序遍历规则非常像我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。而将区间按照基准值划分为左右两半部分的常见方式有hoare版本、挖坑法、前后指针版本。
hoare版本
讲解
接下来我们一起看一下hoare版本的快速排序是如何实现的 选数组左端点为基准值key初始位置。 用双指针从两端向中间移动这里需要注意如果选数组左端的值为key则右指针先走如果选数组右端的值为key则左指针先走。。左指针遇到大于或等于key的值就停右指针遇到小于或等于key的值就停。停后交换两指针所指元素继续移动直到相遇 这里补充一个结论left和right相遇的值一定是小于等于key的。为什么呢这里有三种情况①当right向左移动找小于或等于key的值left向右移动找大于或等于key的值却没找到而这时left和right相遇了此时相遇的位置肯定比key小或相等②当right向左移动找小于或等于key的值但是没找到就直接遇到left那这里的left肯定就在key值的位置上那它们就在key值相遇这就是等于key值的情况③right向左移动时找到了小于或等于key的值left向右移动占到了大于或等于key的值left和right位置上的值交换然后right继续向左移动找小于或等于key的值但是right已经找不到小于或等于key的值了那它就会与left相遇此时left上的值是刚刚从right位置上交换过来的小于或等于key的值所以他们还是在小于或等于key上的值相遇。 指针相遇后交换key与相遇位置值。 key的索引要更新到相遇点接下来准备对key左右子数组分别进行重复的操作。 我们发现整体看每次对key左右子数组的排序很像二叉树结构所以我们可以通过递归完成对子区间数据的排序。
代码
void swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}int hoare(int* a, int left, int right)
{int keyIndex left;while (left right){while (left right a[keyIndex] a[right]){--right;}while (left right a[keyIndex] a[left]){left;}swap(a[left], a[right]);}swap(a[keyIndex], a[right]);keyIndex right;return keyIndex;
}void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;int keyIndex hoare(a, left, right);quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}
在代码中有两个点要注意hoare函数里的最内层的两个while循环中必须要有leftright这个条件,不然会越界while (left right a[keyIndex] a[right])不能写成while (left right a[keyIndex] a[right])while (left right a[keyIndex] a[left])不能写成 while (left right a[keyIndex] a[left])不然出现与key一样的值会进入死循环。
挖坑法
接下来我们再看一下挖坑法的快速排序是如何实现的
讲解 选数组左端点为key用双指针准备从两端向中间移动。选数组左端的值为key则还是右指针先走。 双指针移动右指针遇小于或等于key值的填左坑左指针遇大于或等于key值的填右坑直到两个指针相遇。 指针相遇key值填入相遇的位置。key填入相遇的位置后别忘了更新key的索引位置
接下来准备对key左右子数组分别进行重复的操作与hoare的做法是一样的进行递归排序。
代码
void swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}int hole(int* a, int left, int right)
{int keyIndex left;int key a[keyIndex];while (left right){while (left right a[right] key) {--right;}a[left] a[right];while (left right a[left] key) {left;}a[right] a[left];}a[right] key;keyIndex right;return keyIndex;
}void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;int keyIndex hoare(a, left, right);quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}快慢指针法
讲解
接下来我们再看一下快慢指针法的快速排序是如何实现的 初始化数组左端元素为keypre慢指针和cur快指针都向右移动。 遍历数组当 cur 指向元素小于key时pre向前移动一个位置交换 cur 和 pre 位置的值pre和cur所在的位置如果相同就不用交换当cur指向元素大于或等于keypre保持不动cur继续往前走。 遍历结束后交换 pre 位置的元素和key元素然后更新key索引。
接下来准备对key左右子数组分别进行重复的操作与hoare和挖坑法的做法是一样的进行递归排序。
代码
void swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}int pre_cur(int* a, int left, int right)
{int keyIndex left, pre left, cur left 1;while (cur right){while (a[cur] a[keyIndex] pre ! cur) {swap(a[cur], a[pre]);}cur;}swap(a[pre], a[keyIndex]);keyIndex pre;return keyIndex;
}void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;int keyIndex pre_cur(a, left, right);quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}快排的时间复杂度与优化
我们前面讲了快速排序的三种写法但其实三种写法的时间复杂度都差不多只是第二种写法更好理解第三种写法代码量少且不容易写错因为在hoare和挖坑法版本的写法中最内层的两个while循环有些细节问题需要注意。所以总体来说更推荐第三中写法。
时间复杂度
在探讨快速排序算法时我们注意到其递归展开图与二叉树结构有相似之处。为了深入理解其时间复杂度和最坏情况我们可以从以下几个方面进行阐述
1.时间复杂度分析
快速排序通过递归将数组不断划分其递归深度与二叉树的深度相似。在理想情况下递归深度最多为 logn其中 n 是数组的长度。这是因为每次递归都将数组大致均匀地划分为两个子数组。
2.每层递归的工作量
在快速排序的每一层递归中需要遍历当前子数组以定位key的最终位置。尽管随着递归的深入之前的key元素不再需要考虑但这对整体工作量的影响是有限的 为了简化分析我们可以假设每层递归都需要处理 n 个元素尽管实际上这个数字会逐层减小但减小的数量相对于 n 来说是可以忽略的。
3.总体时间复杂度
结合上述两点快速排序的总体时间复杂度为 O(n log n)。这是因为每层递归需要处理 n 个元素而递归深度最多为 logn。
最坏情况分析
1.最坏情况的发生
快速排序的最坏情况发生在数组已经接近排序完成即顺序或逆序时或者key选择不当如总是选择数组的第一个元素而该元素恰好是最小值或最大值时。
2.时间复杂度与栈溢出
在最坏情况下快速排序的时间复杂度可能达到 O(n²)。这是因为每次划分都极不均匀导致递归深度接近 n从而引发大量的递归调用和栈空间消耗容易发生栈溢出。
3.key位置的影响
key的位置对快速排序的性能至关重要。如果key总是选择接近数组的一端如最小值或最大值则划分将极不均匀导致递归深度增加。 相反如果key能够接近数组的中间位置则划分将更加均匀递归深度将更接近 logn从而提高算法的效率。
对最坏情况的优化
当枢纽每次都接近数组的中间位置时快速排序的递归展开图将更接近满二叉树。满二叉树的深度均匀且每个节点都有两个子节点这有助于减少递归调用的次数和栈空间的使用。因此选择好的key策略如随机选择、三数取中法等对于提高快速排序的性能至关重要。
1.随机选择法
我们不一定让区间内第一个值作为key我们每次在区间内随机选一个值做key。虽然随机选择的情况下也有可能选到当前区间内的最小值或最大值但是那是一个低概率事件大多数情况下还是不会取到区间内的最值。
代码
void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;//随机选keyint randIndex left (rand() % (right - left));swap(a[left], a[randIndex]);int keyIndex pre_cur(a, left, right);if ((right - left 1) 10) {quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}else {insertSort(a, right);}
}
2.三数取中
三数取中将区间内的left、right和mid位置的值比较大小取中间值。这种方法是一定不会取到区间内的最值所以更推荐这种写法。
代码
int getMidIndex(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]) {if (a[mid] a[right]) {return mid;}else if (a[right] a[left]) {return right;}else {return left;}}else {if (a[left] a[right]) {return left;}else if (a[right] a[mid]) {return right;}else {return mid;}}
}void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;//三数取中int midIndex getMidIndex(a, left, right);swap(a[left], a[midIndex]);int keyIndex pre_cur(a, left, right);if ((right - left 1) 10) {quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}else {insertSort(a, right);}
}
小区间优化
在快速排序算法中当处理小规模数据时递归调用可能会变得低效。为了优化这种情况我们可以引入小区间优化策略。
背景
1.递归调用的低效性在快速排序中当数组被划分成较小的子数组时递归调用可能会变得频繁且低效。特别是当子数组的长度非常小如只有几个元素时递归调用的开销可能会超过直接排序这些元素所需的开销。 2.插入排序的优势插入排序在处理小规模数据时通常表现较好。当数据已经部分有序或数据量很小时插入排序的效率往往高于快速排序的递归调用。
原理
1.设定阈值为了避免在小规模数据上进行不必要的递归调用我们可以设定一个阈值通常取10左右。当子数组的长度小于这个阈值时我们不再使用快速排序的递归调用而是改用插入排序来排序这些元素。
2.优化二叉树结构在快速排序的递归过程中二叉树的深度和形状对算法的效率有很大影响。当子数组长度较小时递归调用会生成大量的浅层节点这些节点的处理开销较大。通过设定阈值并使用插入排序我们可以减少这些浅层节点的数量从而优化二叉树的结构提高算法的整体效率。
3.利用插入排序的优势插入排序在处理小规模或部分有序数据时非常高效。当子数组长度小于阈值时这些子数组很可能已经部分有序特别是在快速排序的后期阶段因此插入排序能够更快地完成排序任务。
为什么阈值取10左右
经验值通过大量的实验和观察人们发现当子数组长度小于10时使用插入排序通常比继续递归调用快速排序更高效。这个阈值是一个经验值但在大多数情况下都能取得良好的效果。平衡效率与开销选择10作为阈值是为了在效率即排序速度和开销即递归调用的额外负担之间找到一个平衡点。当子数组长度小于10时递归调用的开销开始变得显著而插入排序则能够更高效地处理这些小规模数据。优化二叉树深层节点通过设定阈值并使用插入排序我们可以优化二叉树中深层节点的处理。这些节点通常对应着较小的子数组使用插入排序能够减少不必要的递归调用从而提高算法的整体效率。
代码
void quickSort(int* a, int left, int right)
{if (left right)return;int begin left, end right;//随机选key/*int randIndex left (rand() % (right - left));swap(a[left], a[randIndex]);*///三路取中int midIndex getMidIndex(a, left, right);swap(a[left], a[midIndex]);int keyIndex pre_cur(a, left, right);if ((right - left 1) 10) {quickSort(a, begin, keyIndex - 1);quickSort(a, keyIndex 1, end);}else {//小区间优化insertSort(a, right);}
}
非递归版本
递归版本的快速排序有一个问题递归的深度太深容易栈溢出。
思路
非递归版本的快速排序需要借助栈来实现。其实在递归版本的快速排序中每一次递归中变化的主要是区间的大小所以我们可以在每次单趟排序完后让对应区间的子区间入栈。
具体步骤
1.初始化栈并推入初始索引
创建栈将数组的起始和结束索引入栈 2.开始循环处理栈顶元素
弹出栈顶的左右索引确定当前子数组的范围。
这里需要注意在入栈的时候如果先入栈的是end然后再入栈begin那先出栈的就是begin后出栈的就是end。先进后出 调用划分函数即前面讲hoare版本的hoare函数、挖坑法的hole函数、快慢指针的pre_cur函数获取key元素的位置 根据key元素位置将未排序的子数组索引范围入栈
如果子区间只有一个值或者没有值就不入栈 重复2的步骤直至栈为空则排序完成。
3.最后销毁栈。
代码
void quickSortNonOrder(int* a, int n)
{st s;initStack(s);int begin 0, end n - 1;pushStack(s, end);pushStack(s, begin);while (!isEmpty(s)){int left stackTop(s);popStack(s);int right stackTop(s);popStack(s);int keyIndex pre_cur(a, left, right);if (keyIndex - 1 left) //左子区间的右端索引大于左端索引说明这个子区间不止一个值就可以入栈{pushStack(s, keyIndex - 1);pushStack(s, left);}if (keyIndex 1 right) //右子区间的右端索引大于左端索引说明这个子区间不止一个值就可以入栈{pushStack(s, right);pushStack(s, keyIndex 1);}}destroyStack(s);
}
这里的栈会用到前面讲解栈的代码数据结构--栈和队列-CSDN博客
