1 //版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
2 //http://shexinwei.blogbus.com/logs/74827291.html
3
4
5 /*
6
7 Subject: Quick sort
8
9 Author: shexinwei
10
11 School: xidian university
12
13 Date: 2010-09-12
14
15 Laguage: C++
16
17 IDE | Tool: GCC
18
19 Version: 1.0
20
21 Modify Time: 2010-09-12
22
23 */
24
25 #include <iostream>
26
27 using namespace std;
28
29 int sort(int begin,int end,int data[],int n);
30
31 int recurs(int begin,int end,int data[],int n);
32
33 int print(int data[],int n);
34
35 int main()
36
37 {
38
39 int data[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
40
41 //打印初始序列
42
43 print(data,20);
44
45 //递归排序
46
47 recurs(0,19,data,20);
48
49 //打印最终序列
50
51 print(data,20);
52
53 cout<<endl;
54
55 return 1;
56
57 }
58
59
60
61 //打印序列
62
63 int print(int data[],int n)
64
65 {
66
67 for(int i = 0;i<n;i++)
68
69 cout<<data[i]<<" ";
70
71 cout<<endl;
72
73 return 1;
74
75 }
76
77
78
79
80
81 int sort(int begin,int end,int data[],int n)
82
83 {
84
85 //选择最后一位做初始的中枢
86
87 int pos = end;
88
89 int key = data[end];
90
91 //索引初始化
92
93 int front = begin;
94
95 int last = end;
96
97 for(;front != last;front++)
98
99 { //向后查找
100
101
102
103 if((data[front] < key) || (data[front] == key)) continue;
104
105 else
106
107 { //遇到比中枢值大的元素，交换位置，修改pos的值，并开始从后向前找
108
109 data[pos] = data[front];
110
111 pos = front;
112
113 //以下一句可注释，只需要保存中枢的位置，可以不修改值，因中枢值在key中保存，最后找到最终位置后再赋值即可
114
115 data[pos] = key;
116
117 //输出改变一次后的序列
118
119 print(data,n);
120
121 for(;front != last;last--)
122
123 {//从后向前查找
124
125 if((data[last] > key)||(data[last] == key)) continue;
126
127 else
128
129 { //遇到比中枢值小的元素，交换位置，修改pos值，并重新开始从前向后查找
130
131 data[pos] = data[last];
132
133 pos = last;
134
135 //以下一句可注释，只需要保存中枢的位置，可以不修改值，因中枢值在key中保存，最后找到最终位置后再赋值即可
136
137 data[pos] = key;
138
139 //打印修改以后的序列
140
141 print(data,n);
142
143 //重新开始从前向后查找
144
145 break;
146
147 }
148
149 }
150
151
152
153 }
154
155 //如果从后向前已经使得front==last，那么一趟分割完毕
156
157 if(front == last) break;
158
159 }
160
161 data[pos] = key;
162
163 return pos;
164
165 }
166
167 int recurs(int begin,int end,int data[],int n)
168
169 {
170
171 //递归出口
172
173 if((begin == end) || (begin > end)) return 1;
174
175 else
176
177 {
178
179 //做分割
180
181 int index = sort(begin,end,data,n);
182
183 //前一部分递归
184
185 recurs(begin,index-1,data,n);
186
187 //后一部分递归
188
189 recurs(index+1,end,data,n);
190
191 }
192
193 }