标签：ios 改进 因此 cas art def clock ons min
我们要使Srot能排序Array数组类。
Sort应该既能排序静态数组类又能排序动态数组类。
这个函数返回原生数组的首地址。
数组类需要新增成员函数array，排序类需要新增六个静态成员函数。
Array.h添加array函数：
1 #ifndef ARRAY_H
2 #define ARRAY_H
3
4 #include "Object.h"
5 #include "Exception.h"
6
7 namespace DTLib
8 {
9
10 template 11 class Array : public Object
12 {
13 protected:
14 T* m_array;
15 public:
16 virtual bool set(int i, const T&e) //O(1)
17 {
18 bool ret = ((0 length()));
19
20 if( ret )
21 {
22 m_array[i] = e;
23 }
24
25 return ret;
26 }
27
28 virtual bool get(int i, T& e) const //O(1)
29 {
30 bool ret = ((0 length()));
31
32 if( ret )
33 {
34 e = m_array[i];
35 }
36
37 return ret;
38 }
39
40 T& operator[] (int i) //O(1)
41 {
42 if((0 length()))
43 {
44 return m_array[i];
45 }
46 else
47 {
48 THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
49 }
50 }
51
52 T operator[] (int i) const //O(1)
53 {
54 return (const_cast>(*this))[i];
55 }
56
57 T* array()const
58 {
59 return m_array;
60 }
61
62 virtual int length() const = 0;
63 };
64
65 }
66
67 #endif // ARRAY_H
Sort.h改进如下：
1 #ifndef SORT_H
2 #define SORT_H
3
4 #include "Object.h"
5 #include
6
7 namespace DTLib
8 {
9
10 class Sort : public Object
11 {
12 private:
13 Sort();
14 Sort(const Sort&);
15 Sort& operator = (const Sort&);
16
17 template 18 static void Swap(T& a, T& b)
19 {
20 T c(a);
21 a = b;
22 b = c;
23 }
24
25 template
26 static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max=true)
27 {
28 int i = begin;
29 int j = mid + 1;
30 int k = begin; //代表辅助空间起始位置
31
32 while( (i end) )
33 {
34 if( min2max ? (src[i] src[j]) )
35 {
36 helper[k++] = src[i++];
37 }
38 else
39 {
40 helper[k++] = src[j++];
41 }
42 }
43
44 while( i mid)
45 {
46 helper[k++] = src[i++];
47 }
48
49 while( j end )
50 {
51 helper[k++] = src[j++];
52 }
53
54 for(i = begin; i )
55 {
56 src[i] = helper[i];
57 }
58 }
59
60 template
61 static void Merge(T src[], T helper[], int begin, int end, bool min2max)
62 {
63 if( begin end )
64 {
65 int mid = (begin + end) / 2;
66
67 Merge(src, helper, begin, mid, min2max);
68 Merge(src, helper, mid+1, end, min2max);
69
70 Merge(src, helper, begin, mid, end, min2max); //真正的归并操作
71 }
72 }
73
74 template
75 static int Partition(T array[], int begin, int end, bool min2max)
76 {
77 T pv = array[begin];
78
79 while( begin end )
80 {
81 while( (begin pv) : (array[end] pv)) )
82 {
83 end--;
84 }
85
86 Swap(array[begin], array[end]);
87
88 while( (begin = pv)) )
89 {
90 begin++;
91 }
92
93 Swap(array[begin], array[end]);
94 }
95
96 array[begin] = pv; //基准就位
97
98 return begin;
99 }
100
101 template
102 static void Quick(T array[], int begin, int end, bool min2max)
103 {
104 if( begin end )
105 {
106 int pivot = Partition(array, begin, end, min2max);
107
108 Quick(array, begin, pivot - 1, min2max);
109 Quick(array, pivot + 1, end, min2max);
110 }
111 }
112
113 public:
114 template
115 static void Select(T array[], int len, bool min2max=true)
116 {
117 for(int i = 0; i )
118 {
119 int min = i;
120 for(int j = i + 1; j )
121 {
122 if( min2max ? (array[min] > array[j]) : (array[min] array[j]) )
123 {
124 min = j;
125 }
126 }
127
128 if( min != i)
129 {
130 Swap(array[i], array[min]);
131 }
132 }
133 }
134
135 template
136 static void Insert(T array[], int len, bool min2max=true)
137 {
138 for(int i=1; i //从1开始，第0个元素没有必要插入操作
139 {
140 int k = i;
141 T e = array[i];
142
143 for(int j=i-1; (j>=0) && (min2max ? (array[j] > e) : (array[j] )
144 {
145 array[j+1] = array[j];
146 k = j;
147 }
148
149 if( k != i ) //赋值比“比较操作耗时”
150 {
151 array[k] = e;
152 }
153 }
154 }
155
156 template
157 static void Bubble(T array[], int len, bool min2max=true)
158 {
159 bool exchange = true;
160
161 for(int i=0; (i)
162 {
163 exchange = false;
164
165 for(int j=len-1; j>i; j--)
166 {
167 if(min2max ? (array[j] 1]) : (array[j] > array[j-1]))
168 {
169 Swap(array[j], array[j-1]);
170 exchange = true;
171 }
172 }
173 }
174 }
175
176 template
177 static void Shell(T array[], int len, bool min2max=true)
178 {
179 int d = len;
180 do
181 {
182 d = d / 3 + 1; //d的减小方式（实践证明这样做效果比较好）
183
184 for(int i = d; i d)
185 {
186 int k = i;
187 T e = array[i];
188
189 for(int j=i-d; (j>=0) && (min2max ? (array[j] > e) : (array[j] d)
190 {
191 array[j+d] = array[j];
192 k = j;
193 }
194
195 if( k != i ) //赋值比“比较操作耗时”
196 {
197 array[k] = e;
198 }
199 }
200
201 }while( d > 1 );
202 }
203
204 template
205 static void Merge(T array[], int len, bool min2max=true)
206 {
207 T* helper = new T[len];
208
209 if( helper != NULL )
210 {
211 Merge(array, helper, 0, len - 1, min2max);
212 }
213
214 delete[] helper;
215 }
216
217 template
218 static void Quick(T array[], int len, bool min2max=true)
219 {
220 Quick(array, 0, len - 1, min2max);
221 }
222
223 template
224 static void Select(Array& array, bool min2max=true)
225 {
226 Select(array.array(), array.length(), min2max);
227 }
228
229 template
230 static void Insert(Array& array, bool min2max=true)
231 {
232 Insert(array.array(), array.length(), min2max);
233 }
234
235 template
236 static void Bubbble(Array& array, bool min2max=true)
237 {
238 Bubble(array.array(), array.length(), min2max);
239 }
240
241 template
242 static void Shell(Array& array, bool min2max=true)
243 {
244 Shell(array.array(), array.length(), min2max);
245 }
246
247 template
248 static void Merge(Array& array, bool min2max=true)
249 {
250 Merge(array.array(), array.length(), min2max);
251 }
252
253 template
254 static void Quick(Array& array, bool min2max=true)
255 {
256 Quick(array.array(), array.length(), min2max);
257 }
258 };
259
260 }
261
262 #endif // SORT_H
无代理时的测试程序：
1 #include 2 #include 3 #include "Sort.h"
4
5
6
7 using namespace std;
8 using namespace DTLib;
9
10 struct Test : public Object
11 {
12 int id;
13 int data1[1000];
14 double data2[500];
15
16 bool operator const Test& obj)
17 {
18 return id obj.id;
19 }
20
21 bool operator >= (const Test& obj)
22 {
23 return id >= obj.id;
24 }
25
26 bool operator > (const Test& obj)
27 {
28 return id > obj.id;
29 }
30
31 bool operator const Test& obj)
32 {
33 return id obj.id;
34 }
35 };
36
37 Test t[1000];
38
39
40 int main()
41 {
42 clock_t begin = 0;
43 clock_t end = 0;
44
45 for(int i=0; i 1000; i++)
46 {
47 t[i].id = i;
48 }
49
50 begin = clock();
51
52 Sort::Bubble(t, 1000, false);
53
54 end = clock();
55
56 cout "Time : " endl;
57
58 for(int i=0; i 1000; i++)
59 {
60 //cout
61 }
62
63 return 0;
64 }
结果如下：
使用代理类：
1 #include 2 #include 3 #include "Sort.h"
4
5
6
7 using namespace std;
8 using namespace DTLib;
9
10 struct Test : public Object
11 {
12 int id;
13 int data1[1000];
14 double data2[500];
15
16 bool operator const Test& obj)
17 {
18 return id obj.id;
19 }
20
21 bool operator >= (const Test& obj)
22 {
23 return id >= obj.id;
24 }
25
26 bool operator > (const Test& obj)
27 {
28 return id > obj.id;
29 }
30
31 bool operator const Test& obj)
32 {
33 return id obj.id;
34 }
35 };
36
37 class TestProxy : public Object
38 {
39 protected:
40 Test* m_pTest;
41
42 public:
43
44 //原始对象能干的事代理对象必须也要能干，因此要实现以下函数
45 int id()
46 {
47 return m_pTest->id;
48 }
49
50 int* data1()
51 {
52 return m_pTest->data1;
53 }
54
55 double* data2()
56 {
57 return m_pTest->data2;
58 }
59
60 Test& test() const //请出委托者的函数
61 {
62 return *m_pTest;
63 }
64
65 bool operator const TestProxy& obj)
66 {
67 return test() //代理类对象的比较就是原始对象的比较
68 }
69
70 bool operator >= (const TestProxy& obj)
71 {
72 return test() >= obj.test(); //代理类对象的比较就是原始对象的比较
73 }
74
75 bool operator > (const TestProxy& obj)
76 {
77 return test() > obj.test(); //代理类对象的比较就是原始对象的比较
78 }
79
80 bool operator const TestProxy& obj)
81 {
82 return test() //代理类对象的比较就是原始对象的比较
83 }
84
85 Test& operator = (Test& test)
86 {
87 m_pTest = &test;
88
89 return test;
90 }
91 };
92
93 Test t[1000];
94 TestProxy pt[1000];
95
96
97 int main()
98 {
99 clock_t begin = 0;
100 clock_t end = 0;
101
102 for(int i=0; i 1000; i++)
103 {
104 t[i].id = i;
105 pt[i] = t[i]; //一一映射
106 }
107
108 begin = clock();
109
110 Sort::Bubble(pt, 1000, false);
111
112 end = clock();
113
114 cout "Time : " endl;
115
116 for(int i=0; i 1000; i++)
117 {
118 //cout
119 }
120
121 return 0;
122 }
结果如下：
小结：
第五十课 排序的工程应用示例
标签：ios 改进 因此 cas art def clock ons min
原文地址：https://www.cnblogs.com/wanmeishenghuo/p/9688404.html