1. 最简单的实现快速排序的方法是利用递归来实现,如果要利用非递归的方法实现
2. 非递归的实现快速排序,可以利用栈来实现。其实递归的本质就是栈的先进后出的性质。
利用快速排序每次是递归向左右子序列中进行排序,利用栈我们可以把左右子序列的端点值保存到栈中,然后每次取栈顶区间进行排序,直到栈为空则整个序列为有序
3. 代码
#include<stack> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; //Partition函数 int Partition(int *arrNum, int l, int r){ //数据不合法 if(arrNum == NULL || l > r){ return -1; } int mid = (l+r)>>1; swap(arrNum[mid], arrNum[r]); int leftSeqIndex = l; //扫描 for(int i = l; i < r; i++){ if(arrNum[i] < arrNum[r]){ if(i > leftSeqIndex){ swap(arrNum[i], arrNum[leftSeqIndex]); } ++leftSeqIndex; } } swap(arrNum[leftSeqIndex], arrNum[r]); return leftSeqIndex; } //非递归实现快速排序 void QuickSort(int *arrNum, int n){ //如果数据不合法 if(arrNum == NULL || n <= 0){ return; } //栈用来保存区间两个端点 stack<pair<int,int> >stk; stk.push(make_pair(0, n-1)); //栈不为空则继续排序 while(!stk.empty()){ pair<int,int> seq = stk.top(); stk.pop(); int index = Partition(arrNum, seq.first, seq.second); //返回的是-1说明无效数据 if(index == -1){ return; } if(index > seq.first){ stk.push(make_pair(seq.first, index-1)); } if(index < seq.second){ stk.push(make_pair(index+1, seq.second)); } } } int main(){ int arrNum[] = {0,9,-1,6,7,3,5}; QuickSort(arrNum, 7); for(int i = 0; i < 7; i++) cout<<arrNum[i]<<" "; cout<<endl; getchar(); return 0; } /* 输出 -1 0 3 5 6 7 9 */