非递归式实现快速排序
快速排序基本思想是寻找一个元素作为基准，将其他元素划分为两部分，其中一部分比基准元素小，另一部分比基准元素大，然后如此继续对这两部分操作下去
快速排序最简单的实现就是通过简单的递归，实现方式之一是使用双指针，两个指针同时走，左指针找到大的，右指针找到小的，然后交换这两个元素的位置，问题在于枢纽元素和谁交换，让右指针先走，两个指针走到相同位置的时候必然是右指针走到左指针的地方了，而左指针指向的元素是刚刚交换完比枢纽元素小的，而枢纽元素选的是第一个，因此它们进行位置交换就是正确的
这里给出C版本，C++版本一般是将int *a，换成std::vector<int>&a
void QS(int *a, int low, int high) { // 两个指针同时走
if (low >= high)
return;
int pivot = a[low], i = low, j = high;
while (i != j) {
while (i < j && a[j] >= pivot) // 右指针找小的
j--;
while (i < j && a[i] <= pivot) // 左指针找大的
i++;
if(i<j)
std::swap(a[i],a[j]);
}
a[low]=a[i]; // 腾位置给枢纽元素
a[i] = pivot; // 放置枢纽元素
QS(a, low, i - 1);// 继续排左边
QS(a, j + 1, high);// 继续排右边
}而递归改非递归最简单的改法就是使用栈，这样基本上算法没有变化，递归本质也是栈的功劳，先递归的先入栈
void quickSort(std::vector<int> &arr) {
std::stack<std::pair<int,int>>recurse;
recurse.emplace(0,arr.size()-1);
while(recurse.empty()==false) {
int low=recurse.top().first,high=recurse.top().second;
recurse.pop();
if(low>=high)
continue;
int pivot=arr[low],i=low,j=high;
while(i!=j) {
while(i<j&&arr[j]>=pivot)
--j;
while(i<j&&arr[i]<=pivot)
++i;
if(i<j)
std::swap(arr[i],arr[j]);
}
arr[low]=arr[i];
arr[i]=pivot;
recurse.emplace(low,i-1);
recurse.emplace(j+1,high);
}
}测试代码
int main() {
std::vector<int>arr{9,8,7,6,5,4,3,2,1};
quickSort(arr);
for(const auto&num:arr)
std::cout<<num<<' ';
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读