1 int partition(int * const al, int low, int high, int &mid)
2 {
3 if (NULL == al) return -1;
4 if (low >= high) return 0;
5 int pivo = low;
6 int midV = al[pivo];
7 ++low;
8 while (low <= high) {
9 while (low <= high && al[low] <= midV) ++low;
10 while (low <= high && al[high] > midV) --high;
11 if (low < high) {
12 swap (al, low, high);
13 ++low;
14 --high;
15 }
16 }
17 al[pivo] = al[high];
18 al[high] = midV;
19 mid = high;
20 return 0;
21 }
22
23 int quickSort2(int * const al, int num)
24 {
25 // not recurrence
26 if (NULL == al) return -1;
27 if (2 > num) return 0;
28 SimpleQueue queue(num*2);
29 queue.push(0);
30 queue.push(num-1);
31 while (!queue.empty()) {
32 int low = 0;
33 int high = 0;
34 if (0 != queue.pop(&low) || 0 != queue.pop(&high)) {
35 return -1;
36 }
37 int mid = 0;
38 if (0 != partition(al, low, high, mid)) return -1;
39 /*/
40 printf("low:%d, high:%d, mid:%d, ", low, high, mid);
41 dumpList(al, num, "[inDBG]");
42 /*/
43 if (low < mid - 1) {
44 queue.push(low);
45 queue.push(mid-1);
46 }
47 if (mid + 1 < high) {
48 queue.push(mid+1);
49 queue.push(high);
50 }
51 }
52 return 0;
53 }
54
55 int quickSort(int * const al, int low, int high)
56 {
57 if (NULL == al) return -1;
58 if (low >= high) return 0;
59
60 int L = low;
61 int H = high;
62 int midV = al[L];
63 ++low;
64 while (low <= high) {
65 while (low <= high && al[low] <= midV) ++low;
66 while (low <= high && al[high] > midV) --high;
67 if (low < high) {
68 swap (al, low, high);
69 ++low;
70 --high;
71 }
72 }
73 al[L] = al[high];
74 al[high] = midV;
75 quickSort(al, L, high - 1);
76 quickSort(al, high + 1, H);
77 return 0;
78 }
79
80 int quickSort(int * const al, const int num)
81 {
82 return quickSort(al, 0, num-1);
83 }