个人网站尺寸,廊坊手机网站制作,住房和城乡建设部资质延期,徐州金网网站建设「前言」文章内容是对快速排序算法的补充#xff0c;之前的算法流程细节多难处理#xff0c;这里补充三指针随机数法#xff08;递归#xff09;#xff0c;这个容易理解#xff0c;在时间复杂度上也更优秀。 快排#xff1a;三指针随机数法
原理跟之前的一致#xff… 「前言」文章内容是对快速排序算法的补充之前的算法流程细节多难处理这里补充三指针随机数法递归这个容易理解在时间复杂度上也更优秀。 快排三指针随机数法
原理跟之前的一致这里就不再解释前面版本的细节太多换成这个三指针很好。
传统的快速排序使用两个指针一个指向当前序列的开始另一个指向结束并在每次迭代中根据一个选定的“基准值”来重新排列数组。
然而为了处理一些特殊情况比如包含大量重复元素的数组有时可以使用三指针技术来优化性能。同时为了增加算法的随机性并减少最坏情况发生的概率即当输入数组已排序或接近排序时可以使用随机数法来选择基准值。 随机数法选择基准值 为了避免最坏情况的发生即当输入数组已排序或接近排序时可以选择一个随机的元素作为基准值而不是总是选择第一个或最后一个元素。这可以通过生成一个随机数来实现该随机数对应于数组中的一个有效索引。 三指针 left指针指向当前已经处理好的小于基准值的元素的末尾。right指针指向当前尚未处理的元素的开始且这些元素都大于基准值。icurrent指针当前指针用于遍历数组找到小于或大于基准值的元素。
开始时left 和 i 指向数组的起始位置right 指向数组的末尾。遍历数组时i 会向右移动同时更新 left 和 right 的位置。
数组会分成三块[l, left-1] [left, right] [right1, r]。
1.1 递归实现 算法大致分三步 取基准值采用随机数法数组分三块递归排序
代码如下C
#include iostream
#include vector
#include ctime
using namespace std;// 创建随机数
int GetRandom(vectorint nums, int left, int right)
{int rNum rand();return nums[left rNum % (right - left 1)];
}
// quick sort: 三指针随机数法
void QuickSort(vectorint nums, int l, int r)
{if (l r) return;// 数组分三块int key GetRandom(nums, l, r);int left l, i l, right r;while (i right){if (nums[i] key){swap(nums[left], nums[i]);left;i;}else if (nums[i] key){i;}else // nums[i] key{std::swap(nums[i], nums[right]);--right;}}// 递归去排序// [l, left-1] [left, right] [right1, r]QuickSort(nums, l, left - 1);QuickSort(nums, right 1, r);
}int main()
{srand(time(nullptr));vectorint arr { 4, 6, 1, 0, 9, 5, 7, 7, 6, 6, 2, 3, 8 };QuickSort(arr, 0, arr.size() - 1);for (auto x : arr) cout x ;cout endl;return 0;
}1.2 非递归实现 快速排序的非递归算法基本思路 使用栈代替递归 在递归版本中函数调用栈会自动管理待排序的区间。使用 std::stack 来保存区间的起始和结束索引。 初始化栈 初始时将整个数组的起始索引 left 和结束索引 right 压入栈中。 处理栈中的区间 进入一个循环直到栈为空。每次从栈中弹出一个区间left 和 right。检查当前区间是否有效即 left right如果无效则跳过。 选择基准值使用 GetRandom 函数从当前区间随机选择一个基准值 key。三指针分区 初始化三个指针 l 指向当前区间的左端。i 用于遍历当前区间。r 指向当前区间的右端。 遍历数组根据元素与基准值的比较进行分区 如果 nums[i] key将元素交换到左侧并移动指针。如果 nums[i] key只移动 i 指针。如果 nums[i] key将元素交换到右侧并移动 r 指针。 压入新的区间 在完成分区后可能会产生两个新的子区间 左侧区间 [left, l - 1]右侧区间 [r 1, right] 将这两个区间的起始和结束索引压入栈中以便后续处理。 重复过程 重复上述过程直到栈为空所有的区间都被处理完毕数组就会被排序完成。
C代码如下升序
int GetRandom(vectorint arr, int left, int right)
{int rNum rand();return arr[left rNum % (right - left 1)];
}void QuickSortNonRecursive(std::vectorint nums, int left, int right)
{std::stackint stack;stack.push(left);stack.push(right);while (!stack.empty()) // 栈为空结束{right stack.top(); stack.pop();left stack.top(); stack.pop();// 判断左右区间是否合理若不合理则跳过本次循环if (left right) continue;// 三指针随机数法int key GetRandom(nums, left, right);int l left, i left, r right;while (i r) {if (nums[i] key){std::swap(nums[l], nums[i]);l;i;}else if (nums[i] key){i;}else // nums[i] key{std::swap(nums[i], nums[r]);--r;}}// 将需要排序的部分压入栈中if (left l - 1){stack.push(left);stack.push(l - 1);}if (r 1 right){stack.push(r 1);stack.push(right);}}
}
--------------- END ---------------
「 作者 」 枫叶先生
「 更新 」 2024.4.9
「 声明 」 余之才疏学浅故所撰文疏漏难免或有谬误或不准确之处敬请读者批评指正。
