【30】非递归方法实现快速排序

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
*/