非递归式实现快速排序

快速排序基本思想是寻找一个元素作为基准，将其他元素划分为两部分，其中一部分比基准元素小，另一部分比基准元素大，然后如此继续对这两部分操作下去

快速排序最简单的实现就是通过简单的递归，实现方式之一是使用双指针，两个指针同时走，左指针找到大的，右指针找到小的，然后交换这两个元素的位置，问题在于枢纽元素和谁交换，让右指针先走，两个指针走到相同位置的时候必然是右指针走到左指针的地方了，而左指针指向的元素是刚刚交换完比枢纽元素小的，而枢纽元素选的是第一个，因此它们进行位置交换就是正确的

这里给出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]);}std::swap(arr[i],arr[low]); // 腾位置给枢纽元素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]);}std::swap(arr[i],arr[low]); 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;
}