【模板小程序】快速排序算法实现（递归+非递归）

 1 /*
 2 本程序说明：
 3 
 4 递归方法参见《大话数据结构》
 5 
 6 */
 7 #include <iostream>
 8 #include <vector>
 9 using namespace std;
10 
11 
12 void print(const vector<int>& array)
13 {
14     for(auto val:array)
15         cout<<val<<" ";
16     cout<<endl;
17 }
18 
19 /*********************快速排序的划分写法1**********************/
20 int partition1(vector<int>& array,int low, int high)
21 {
22     int pivot_value=array[low];//取当前区段第一个元素为枢轴
23     while(low < high)
24     {
25         while(low<high && array[high]>=pivot_value)
26             --high;
27         swap(array[low],array[high]);
28         while(low<high && array[low]<=pivot_value)
29             ++low;
30         swap(array[low],array[high]);
31     }
32     return low;
33 }
34 /*************************************************************/
35 /**********快速排序的划分写法2:优化了不必要的交换***************/
36 int partition2(vector<int> &array, int low, int high)
37 {    
38     int pivot_value = array[low];//备份枢轴值
39     while(low < high){
40         while(low < high && array[high] >= pivot_value){
41             --high;
42         }
43         array[low] = array[high];
44         while(low < high && array[low] <= pivot_value){
45             ++low;
46         }
47         array[high] = array[low];
48     }
49     array[low] = pivot_value;
50     
51     return low;
52 }
53 /*************************************************************/
54 
55 /************************常规递归方法*************************/
56 void _qsort(vector<int>& array,int low, int high)
57 {
58     int pivot_index;
59     if(low < high)
60     {
61         pivot_index=partition2(array,low,high);
62         _qsort(array,low,pivot_index-1);
63         _qsort(array,pivot_index+1,high);
64     }
65 }
66 /*************************************************************/
67 /*************************尾递归方法**************************/
68 void _qsort_tail(vector<int>& array,int low, int high)
69 {
70     int pivot_index;
71     while(low < high)
72     {
73         pivot_index=partition2(array,low,high);
74         _qsort_tail(array,low,pivot_index-1);
75         low=pivot_index+1;//这里改成while,下一步partition2相当于_qsort_tail(array,pivot_index+1,high);
76     }
77 }
78 /*************************************************************/
79 
80 //递归排序入口函数
81 void qsort(vector<int>& array)
82 {
83     if(array.empty())
84         return;
85     //_qsort(array,0,array.size()-1);
86     _qsort_tail(array,0,array.size()-1);
87 }
88 
89 int main()
90 {
91     vector<int> array{5,2,7,1,8,-3,4,9,-7,0,88,999,-876,34567,-9876543};
92     cout<<"before_qsort: ";print(array);
93     qsort(array);
94     cout<<"after_qsort: ";print(array);
95     return 0;
96 }

 1 /*
 2 本程序说明：
 3 
 4 非递归方法利用了栈
 5 
 6 */
 7 #include <iostream>
 8 #include <vector>
 9 #include <stack>
10 using namespace std;
11 
12 
13 void print(const vector<int>& array)
14 {
15     for(auto val:array)
16         cout<<val<<" ";
17     cout<<endl;
18 }
19 
20 /*********************快速排序的划分写法1**********************/
21 int partition1(vector<int>& array,int low, int high)
22 {
23     int pivot_value=array[low];//取当前区段第一个元素为枢轴
24     while(low < high)
25     {
26         while(low<high && array[high]>=pivot_value)
27             --high;
28         swap(array[low],array[high]);
29         while(low<high && array[low]<=pivot_value)
30             ++low;
31         swap(array[low],array[high]);
32     }
33     return low;
34 }
35 /*************************************************************/
36 /**********快速排序的划分写法2:优化了不必要的交换***************/
37 int partition2(vector<int>& array, int low, int high)
38 { 
39     int pivot_value = array[low];//备份枢轴值
40     while(low < high){
41         while(low < high && array[high] >= pivot_value){
42             --high;
43         }
44         array[low] = array[high];
45         while(low < high && array[low] <= pivot_value){
46             ++low;
47         }
48         array[high] = array[low];
49     }
50     array[low] = pivot_value;
51     
52     return low;
53 }
54 /*************************************************************/
55 //辅助函数
56 void _qsort_norec(vector<int>& array,int low, int high)
57 {
58     stack<int> temp;
59     temp.push(high);
60     temp.push(low);
61     while(!temp.empty())
62     {
63         low=temp.top();temp.pop();
64         high=temp.top();temp.pop();
65         
66         if(low<high)
67         {
68             int pivot_index=partition2(array,low,high);
69             if(pivot_index>low)
70             {
71                 temp.push(pivot_index-1);
72                 temp.push(low);
73             }
74             if(high>pivot_index)
75             {
76                 temp.push(high);
77                 temp.push(pivot_index+1);
78             }
79         }
80     }
81 }
82 //非递归排序入口函数
83 void qsort_norec(vector<int>& array)
84 {
85     if(array.empty())
86         return;
87     _qsort_norec(array,0,array.size()-1);
88 }
89 
90 int main()
91 {
92     vector<int> array{5,2,7,1,8,-3,4,9,-7,0,88,999,-876,34567,-9876543};
93     cout<<"before_qsort: ";print(array);
94     qsort_norec(array);
95     cout<<"after_qsort: ";print(array);
96     return 0;
97 }