[Algo][July][Homework]实现快速排序（递归和非递归）

百度百科：

https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/369842?fr=aladdin&fromid=2084344&fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

递归版快速排序

 1 void Qsort(int *a, int low, int high){
 2     //low 是数组的左边界，high是数组的右边界
 3     if(low >= high){
 4         return;
 5     }
 6     //i从左边界向右移，j从右边界向左移
 7     int i,j;
 8     i = low;
 9     j = high;
10     //数组的第一个元素设为基准key，把大于key的数移到右边，小于key的数移到它左边
11     int key = a[i];
12     while(i < j){
13         while(i < j && a[j]>=key){
14             j--;
15         }
16         a[i] = a[j];
17         
18         while(i < j && a[i]<=key){
19             i++;
20         }
21         a[j] = a[i];        
22     }
23     a[i] = key; //把key归位
24     Qsort(a,low,i-1); //按照key的左边和右边，分为两个子数组，递归。
25     Qsort(a,i+1,high);
26 }

非递归版快速排序

利用栈，每次把一分为二的子数组的头尾入栈。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int partion(int a[], int low, int high){
 6     int i = low;
 7     int j = high;
 8     int key = a[i];
 9     while(i<j){
10         while((i<j) && (a[j]>=key)){
11             j--;
12         }
13         a[i] = a[j];
14         
15         while((i<j) && (a[i]<=key)){
16             i++;
17         }
18         a[j] = a[i];
19     }
20     a[i] = key;
21     return i;//中值
22 }
23 
24 void Qsort(int a[], int low, int high){
25     stack<int> st;
26     int mid;
27     if(low < high){
28         mid = partion(a,low,high); //一次排序
29     }
30     if(low < mid-1){
31         //左边子数组压栈,先压小的再压大的
32         st.push(low);
33         st.push(mid-1);
34     }
35     if(mid+1 < high){
36         //右边子数组压栈
37         st.push(mid+1);
38         st.push(high);
39     }
40     while(!st.empty()){
41         int q = st.top();
42         st.pop();
43         int p = st.top();
44         st.pop();
45         
46         mid = partion(a,p,q);
47         if(p < mid-1){
48             st.push(p);
49             st.push(mid-1);
50         }
51         if(mid+1 < q){
52             st.push(mid+1);
53             st.push(q);
54         }
55     }
56 }