Chemmy's Blog

chengming0916@outlook.com

C#排序算法的比较

首先通过图表比较不同排序算法的时间复杂度和稳定性。

排序方法

平均时间

最坏情况

最好情况

辅助空间

稳定性

直接插入排序

O(n2)

O(n2)

O(n)

O(1)

冒泡排序

O(n2)

O(n2)

O(n)

O(1)

简单选择排序

O(n2)

O(n2)

O(n2)

O(1)

希尔排序-

O(nlog2n)~O(n2)

O(nlog2n)~O(n2)

O(1)

快速排序

O(nlog2n)

O(n2)

O(nlog2n)

O(log2n)

堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

2-路归并排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(n)

基数排序O(d(n + rd))O(d(n + rd))O(d(n + rd))O(rd)

注:1. 算法的时间复杂度一般情况下指最坏情况下的渐近时间复杂度。

        2. 排序算法的稳定性会对多关键字排序产生影响。

下面通过C#代码说明不同的排序算法

插入排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

希尔排序(shell)

时间复杂度:理想情况—O(nlog2n) 最坏情况—O(n2) 稳定性:不稳定

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

冒泡排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

快速排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(n2) 辅助空间:O(log2n) 稳定性:不稳定

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

选择排序

时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:不稳定

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

堆排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(1) 稳定性:不稳定

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法

归并排序

时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(n) 稳定性:稳定

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

冒泡排序算法(C#实现) - Eric Sun - 博客园

Excerpt

简单的冒泡排序算法,代码如下://冒泡排序(从数组的起始位置开始遍历,以大数为基准:大的数向下沉一位)privatestaticvoid BubbleSortFunction(int[] array) { try { int length = array.Length; int temp; bool


简单的冒泡排序算法,代码如下:

1
<span>//</span><span>冒泡排序(从数组的起始位置开始遍历,以大数为基准:大的数向下沉一位)</span><span><br></span><span>private</span><span>static</span><span>void</span><span> BubbleSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp;<br>                </span><span>bool</span><span> hasExchangeAction; </span><span>//</span><span>记录此次大循环中相邻的两个数是否发生过互换(如果没有互换,则数组已经是有序的)</span><span><br></span><span><br>                </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> length </span><span>-</span><span>1</span><span>; i</span><span>++</span><span>)    </span><span>//</span><span>数组有N个数,那么用N-1次大循环就可以排完</span><span><br></span><span>                {<br>                    hasExchangeAction </span><span>=</span><span>false</span><span>;  </span><span>//</span><span>每次大循环都假设数组有序</span><span><br></span><span><br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span>0</span><span>; j </span><span>&lt;</span><span> length </span><span>-</span><span> i </span><span>-</span><span>1</span><span>; j</span><span>++</span><span>)    </span><span>//</span><span>从数组下标0处开始遍历,(length - i - 1 是刨除已经排好的大数)</span><span><br></span><span>                    {<br>                        </span><span>if</span><span> (array[j] </span><span>&gt;</span><span> array[j </span><span>+</span><span>1</span><span>])    </span><span>//</span><span>相邻两个数进行比较,如果前面的数大于后面的数,则将这相邻的两个数进行互换</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            array[j] </span><span>=</span><span> array[j </span><span>+</span><span>1</span><span>];<br>                            array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;<br>                            hasExchangeAction </span><span>=</span><span>true</span><span>;   </span><span>//</span><span>发生过互换</span><span><br></span><span>                        }<br>                    }<br><br>                    </span><span>if</span><span> (</span><span>!</span><span>hasExchangeAction) </span><span>//</span><span>如果没有发生过互换,则数组已经是有序的了,跳出循环</span><span><br></span><span>                    {<br>                        </span><span>break</span><span>;<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

。。。。。

posted @ 2011-08-17 16:02  Eric Sun  阅读(7637)  评论()  编辑  收藏  举报

C# 经典排序算法大全

Excerpt

文章浏览阅读84次。C# 经典排序算法大全选择排序using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace sorter{ public class SelectionSorter { private int min; …_c# case复杂排序


C# 经典排序算法大全

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class SelectionSorter

{

private int min;

public void Sort(int[] arr)

{

for (int i = 0; i < arr.Length - 1; ++i)

{

min = i;

for (int j = i + 1; j < arr.Length; ++j)

{

if (arr[j] < arr[min])

{

min = j;

}

}

int t = arr[min];

arr[min] = arr[i];

arr[i] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

SelectionSorter selSor = new SelectionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class EbullitionSorter

{

public void Sort(int[] arr)

{

int i, j, temp;

bool done = false;

j = 1;

while ((j < arr.Length) && (!done))

{

done = true;

for (i = 0; i < arr.Length - j; i++)

{

if (arr[i] > arr[i + 1])

{

done = false;

temp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = temp;

}

}

j++;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

EbullitionSorter selSor = new EbullitionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

高速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class QuickSorter

{

private void swap(ref int l, ref int r)

{

int temp;

temp = l;

l = r;

r = temp;

}

public void Sort(int[] list, int low, int high)

{

int pivot;

int l, r;

int mid;

if (high <= low)

{

return;

}

else if (high == low + 1)

{

if (list[low] > list[high])

{

swap(ref list[low], ref list[high]);

}

return;

}

mid = (low + high) >> 1;

pivot = list[mid];

swap(ref list[low], ref list[mid]);

l = low + 1;

r = high;

do

{

while (l <= r && list[l] < pivot)

{

l++;

}

while (list[r] >= pivot)

{

r--;

}

if (l < r)

{

swap(ref list[l], ref list[r]);

}

} while (l < r);

list[low] = list[r];

list[r] = pivot;

if (low + 1 < r)

{

Sort(list, low, r - 1);

}

if (r + 1 < high)

{

Sort(list, r + 1, high);

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

QuickSorter selSor = new QuickSorter();

selSor.Sort(arrInt, 0, arrInt.Length - 1);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class InsertionSorter

{

public void Sort(int[] arr)

{

for (int i = 1; i < arr.Length; i++)

{

int t = arr[i];

int j = i;

while ((j > 0) && (arr[j - 1] > t))

{

arr[j] = arr[j - 1];

--j;

}

arr[j] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

InsertionSorter selSor = new InsertionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class ShellSorter

{

public void Sort(int[] arr)

{

int inc;

for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;

for (; inc > 0; inc /= 3)

{

for (int i = inc + 1; i <= arr.Length; i += inc)

{

int t = arr[i - 1];

int j = i;

while ((j > inc) && (arr[j - inc - 1] > t))

{

arr[j - 1] = arr[j - inc - 1];

j -= inc;

}

arr[j - 1] = t;

}

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

ShellSorter selSor = new ShellSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class Function

{

private int Groups;

private int CopyGroups;

private int mergerows;

private int[] Array27;

private static Random ran = new Random();

public Function(int length)

{

Array27 = new int[length];

for (int i = 0; i < length; i++)

Array27[i] = ran.Next(1, 100);

}

public void ToMergeSort()

{

MergeSort(Array27);

}

public void ToRecursiveMergeSort()

{

RecursiveMergeSort(Array27, 0, Array27.Length - 1);

}

public void ToNaturalMergeSort()

{

NaturalMergeSort(Array27);

}

public void RecursiveMergeSort(int[] Array, int left, int right)

{

int middle = (left + right) / 2;

if (left < right)

{

RecursiveMergeSort(Array, left, middle);

RecursiveMergeSort(Array, middle + 1, right);

MergeOne(Array, left, middle, right);

}

}

public void MergeOne(int[] Array, int left, int middle, int right)

{

int leftindex = left;

int rightindex = middle + 1;

int[] merge = new int[right + 1];

int index = 0;

while (leftindex <= middle && rightindex <= right)

merge[index++] = (Array[leftindex] - Array[rightindex]) >= 0 ? Array[rightindex++] : Array[leftindex++];

if (leftindex <= middle)

{

for (int i = leftindex; i <= middle; i++)

merge[index++] = Array[i];

}

if (rightindex <= right)

{

for (int i = rightindex; i <= right; i++)

merge[index++] = Array[i];

}

index = 0;

for (int i = left; i <= right; i++)

Array[i] = merge[index++];

}

public void MergeSort(int[] Array)

{

int[] merge = new int[Array.Length];

int P = 0;

while (true)

{

int index = 0;

int ENumb = (int)Math.Pow(2, P);

if (ENumb < Array.Length)

{

while (true)

{

int TorFAndrightindex = index;

if (TorFAndrightindex <= Array.Length - 1)

MergeTwo(Array, merge, index, ENumb);

else

break;

index += 2 * ENumb;

}

}

else

break;

P++;

}

}

public void MergeTwo(int[] Array, int[] merge, int index, int ENumb)

{

int left = index;

int middle = left + ENumb - 1;

if (middle >= Array.Length)

{

middle = index;

}

int mergeindex = index;

int right;

int middleTwo = (index + ENumb - 1) + 1;

right = index + ENumb + ENumb - 1;

if (right >= Array.Length - 1)

{

right = Array.Length - 1;

}

while (left <= middle && middleTwo <= right)

{

merge[mergeindex++] = Array[left] >= Array[middleTwo] ? Array[middleTwo++] : Array[left++];

}

if (left <= middle)

{

while (left <= middle && mergeindex < merge.Length)

merge[mergeindex++] = Array[left++];

}

if (middleTwo <= right)

{

while (middleTwo <= right)

merge[mergeindex++] = Array[middleTwo++];

}

if (right + 1 >= Array.Length)

Copy(Array, merge);

}

public void NaturalMergeSort(int[] Array)

{

int[,] PointsSymbol = LinearPoints(Array);

if (PointsSymbol[0, 1] == Array.Length - 1)

return;

else

NaturalMerge(Array, PointsSymbol);

}

public void NaturalMerge(int[] Array, int[,] PointsSymbol)

{

int left;

int right;

int leftend;

int rightend;

mergerows = GNumberTwo(Groups);

CopyGroups = Groups;

int[] TempArray = new int[Array.Length];

while (true)

{

int[,] TempPointsSymbol = new int[mergerows, 2];

int row = 0;

do

{

if (row != CopyGroups - 1)

{

left = PointsSymbol[row, 0];

leftend = PointsSymbol[row, 1];

right = PointsSymbol[row + 1, 0];

rightend = PointsSymbol[row + 1, 1];

MergeThree(Array, TempArray, left, leftend, right, rightend);

MergePointSymbol(PointsSymbol, TempPointsSymbol, row);

}

else

{

默认剩下的单独一个子数组已经虚拟合并。然后Copy进TempArray。

int TempRow = PointsSymbol[row, 0];

int TempCol = PointsSymbol[row, 1];

while (TempRow <= TempCol)

TempArray[TempRow] = Array[TempRow++];

TempPointsSymbol[row / 2, 0] = PointsSymbol[row, 0];

TempPointsSymbol[row / 2, 1] = PointsSymbol[row, 1];

break;

}

row += 2;

if (TempPointsSymbol[0, 1] == Array.Length - 1)

break;

}

while (row <= CopyGroups - 1);

Copy(Array, TempArray);

UpdatePointSymbol(PointsSymbol, TempPointsSymbol, row);

mergerows = GNumber(mergerows);

CopyGroups = GNumberTwo(CopyGroups);

if (PointsSymbol[0, 1] == Array.Length - 1)

break;

}

}

public int GNumber(int Value)

{

if (Value % 2 == 0)

Value /= 2;

else

Value -= 1;

return Value;

}

public int GNumberTwo(int Value)

{

if (Value % 2 == 0)

mergerows = Value / 2;

else

mergerows = Value / 2 + 1;

return mergerows;

}

public void MergeThree(int[] Array, int[] Temp, int left, int leftend, int right, int rightend)

{

int index = left;

while (left <= leftend && right <= rightend)

Temp[index++] = Array[left] >= Array[right] ? Array[right++] : Array[left++];

while (left <= leftend)

Temp[index++] = Array[left++];

while (right <= rightend)

Temp[index++] = Array[right++];

}

public void MergePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int row)

{

int rowindex = row / 2;

TempPointsSymbol[rowindex, 0] = PointsSymbol[row, 0];

TempPointsSymbol[rowindex, 1] = PointsSymbol[row + 1, 1];

}

public void UpdatePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int rows)

{

int row = 0;

for (; row < TempPointsSymbol.GetLength(0); row++)

{

for (int col = 0; col < 2; col++)

PointsSymbol[row, col] = TempPointsSymbol[row, col];

}

for (; row < PointsSymbol.GetLength(0); row++)

{

for (int col2 = 0; col2 < 2; col2++)

PointsSymbol[row, col2] = 0;

}

补剩下的index组,

// int row3 = TempPointsSymbol.GetLength(0); // PointsSymbol[row3, 0] = PointsSymbol[rows, 0]; // PointsSymbol[row3, 1] = PointsSymbol[rows, 1]; // //后面的清零 // for (int row4 = row3 + 1; row4 < PointsSymbol.GetLength(0); row4++) // { // for (int col4 = 0; col4 < 2; col4++) // PointsSymbol[row4, col4] = 0; // } //} } public int[,] LinearPoints(int[] Array) { Groups = 1; int StartPoint = 0; int row = 0; int col = 0; //最糟糕的情况就是有Array.Length行。 int[,] PointsSet = new int[Array.Length, 2]; //线性扫描Array,划分数组 //初始前index=0 PointsSet[row, col] = 0; do { //推断升序子数组终于的index开关 bool Judge = false; //从Array第二个数推断是否要结束或者是否是升序子数组. while (++StartPoint < Array.Length && Array[StartPoint] < Array[StartPoint - 1]) { //打开第一个升序子数组结束的index开关 Judge = true; //又一次開始第二个升序子数组的前index PointsSet[row, col + 1] = StartPoint - 1; //计算子数组个数 Groups++; //换行记录自然子数组的index row++; break; //–StartPoint; } //升序子数组结束index if (Judge) PointsSet[row, col] = StartPoint; //else // –StartPoint; } while (StartPoint < Array.Length); //终于index=StartPoint - 1,可是糟糕情况下还有剩余若干行为: 0,0 … PointsSet[row, col + 1] = StartPoint - 1; //调用展示方法 DisplaySubarray(Array, PointsSet, Groups); return PointsSet; } public void DisplaySubarray(int[] Array, int[,] PointsSet, int Groups) { Console.WriteLine(“Subarray is {0}:”, Groups); //展示子数组的前后index for (int r = 0; r < Groups; r++) { for (int c = 0; c < PointsSet.GetLength(1); c++) { Console.Write(PointsSet[r, c]); if (c < PointsSet.GetLength(1) - 1) Console.Write(“,”); } Console.Write(“\t\t”); } Console.WriteLine(); //展示分出的子数组 for (int v = 0; v < Groups; v++) { int i = 1; for (int r = PointsSet[v, 0]; r <= PointsSet[v, 1]; r++) { Console.Write(Array[r] + “ “); i++; } if (i <= 3) Console.Write(“\t\t”); else Console.Write(“\t”); if (PointsSet[v, 1] == Array.Length) break; } } public void Copy(int[] Array, int[] merge) { //一部分排好序的元素替换掉原来Array中的元素 for (int i = 0; i < Array.Length; i++) { Array[i] = merge[i]; } } //输出 public override string ToString() { string temporary = string.Empty; foreach (var element in Array27) temporary += element + “ “; temporary += “\n”; return temporary; } } class Program { static void Main(string[] args) { while (true) { Console.WriteLine(“请选择:”); Console.WriteLine(“1.归并排序(非递归)”); Console.WriteLine(“2.归并排序(递归)”); Console.WriteLine(“3.归并排序(自然合并)”); Console.WriteLine(“4.退出”); int Arraynum = Convert.ToInt32(Console.ReadLine()); switch (Arraynum) { case 4: Environment.Exit(0); break; case 1: Console.WriteLine(“Please Input Array Length”); int Leng271 = Convert.ToInt32(Console.ReadLine()); Function obj1 = new Function(Leng271); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj1); Console.WriteLine(“‘MergeSort’ Finaly Sorting Result:”); obj1.ToMergeSort(); Console.WriteLine(obj1); break; case 2: Console.WriteLine(“Please Input Array Length”); int Leng272 = Convert.ToInt32(Console.ReadLine()); Function obj2 = new Function(Leng272); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj2); Console.WriteLine(“‘RecursiveMergeSort’ Finaly Sorting Result:”); obj2.ToRecursiveMergeSort(); Console.WriteLine(obj2); break; case 3: Console.WriteLine(“Please Input Array Length”); int Leng273 = Convert.ToInt32(Console.ReadLine()); Function obj3 = new Function(Leng273); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj3); obj3.ToNaturalMergeSort(); Console.WriteLine(); Console.WriteLine(); Console.WriteLine(“‘NaturalMergeSort’ Finaly Sorting Result:”); Console.WriteLine(obj3); break; } } } } }

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class RadixSorter

{

public int[] RadixSort(int[] ArrayToSort, int digit)

{

for (int k = 1; k <= digit; k++)

{

int[] tmpArray = new int[ArrayToSort.Length];

int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for (int i = 0; i < ArrayToSort.Length; i++)

{

int tmpSplitDigit = ArrayToSort[i] / (int)Math.Pow(10, k - 1) - (ArrayToSort[i] / (int)Math.Pow(10, k)) * 10;

tmpCountingSortArray[tmpSplitDigit] += 1;

}

for (int m = 1; m < 10; m++)

{

tmpCountingSortArray[m] += tmpCountingSortArray[m -

1];

}

for (int n = ArrayToSort.Length - 1; n >= 0; n--)

{

int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10, k - 1) -

(ArrayToSort[n] / (int)Math.Pow(10, k)) * 10;

tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort

[n];

tmpCountingSortArray[tmpSplitDigit] -= 1;

}

for (int p = 0; p < ArrayToSort.Length; p++)

{

ArrayToSort[p] = tmpArray[p];

}

}

return ArrayToSort;

}

}

class Program

{

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

int[] newIntArray = intArray;

RadixSorter rS=new RadixSorter();

newIntArray = rS.RadixSort(intArray, intArray.Length);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

/// 要求: /// arrayToSort的元素必须大于等于0。或者经过一定的转换使其元素在 /// 大于等于0范围内。比如有例如以下序列(-1,-8,10,11),那么依据最小值8, /// 将各个数字加8转化为(7,0,18,19),然后进行计数排序。结果为(0,7,18,19), /// 然后再将结果个数字减8即为(-8,-1,10,11) /// /// 要排序的数组 /// 数组的最大值加一 /// 计数排序后的结果 public static int[] CountingSort(int[] arrayToSort, int k) { // 排序后的结果存储 int[] sortedArray = new int[arrayToSort.Length]; // 计数数组 int[] countingArray = new int[k]; // 计数数组初始化 for (int i = 0; i < countingArray.Length; i++) { countingArray[i] = 0; } // 单个元素计数(经过该步骤countingArray[i]的含义为数字i的个数为countingArray[i]) for (int i = 0; i < arrayToSort.Length; i++) { countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] + 1; } // 计算小于等于某数的个数(经过该步骤countingArray[i]的含义为小于等于数字i的元素个数为countingArray[i]) for (int i = 1; i < countingArray.Length; i++) { countingArray[i] += countingArray[i - 1]; } // 得到排序后的结果 for (int i = 0; i < sortedArray.Length; i++) { int numIndex = countingArray[arrayToSort[i]] - 1; sortedArray[numIndex] = arrayToSort[i]; countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] - 1; } return sortedArray; } static void Main(string[] args) { int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 }; int[] intNewArray = intArray; intNewArray = CountingSort(intArray, intArray.Length); foreach (int i in intNewArray) { Console.Write(i + “ “); } Console.ReadKey(); } } }

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

private static void HeapSortFunction(int[] array)

{

try

{

BuildMaxHeap(array);

for (int i = array.Length - 1; i > 0; i--)

{

Swap(ref array[0], ref array[i]);

MaxHeapify(array, 0, i);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void BuildMaxHeap(int[] array)

{

try

{

for (int i = array.Length / 2 - 1; i >= 0; i--)

{

MaxHeapify(array, i, array.Length);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void MaxHeapify(int[] array, int currentIndex, int heapSize)

{

try

{

int left = 2 * currentIndex + 1;

int right = 2 * currentIndex + 2;

int large = currentIndex;

if (left < heapSize && array[left] > array[large])

{

large = left;

}

if (right < heapSize && array[right] > array[large])

{

large = right;

}

if (currentIndex != large)

{

Swap(ref array[currentIndex], ref array[large]);

MaxHeapify(array, large, heapSize);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void Swap(ref int a, ref int b)

{

int temp = 0;

temp = a;

a = b;

b = temp;

}

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

HeapSortFunction(intArray);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

排序的分类/稳定性/时间复杂度和空间复杂度总结

版权声明:本文博客原创文章。博客,未经同意,不得转载。

归并排序算法(C#实现)

Excerpt

自顶向下的归并排序:是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:1)划分子表 2)合并半子表


     归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式:1): 自底向上的方法 2):自顶向下的方法

 1、 自底向上的方法
(1) 自底向上的基本思想
     自底向上的基本思想是:第1趟归并排序时,将待排序的文件R[1..n]看作是n个长度为1的有序子文件,将这些子文件两两归并,若n为偶数,则得到n/2个长度为2的有序子文件;若n为奇数,则最后一个子文件轮空(不参与归并)。故本趟归并完成后,前n/2 - 1个有序子文件长度为2,但最后一个子文件长度仍为1;第2趟归并则是将第1趟归并所得到的n/2个有序的子文件两两归并,如此反复,直到最后得到一个长度为n的有序文件为止。
     上述的每次归并操作,均是将两个有序的子文件合并成一个有序的子文件,故称其为”二路归并排序”。类似地有k(k>2)路归并排序。   

2、自顶向下的方法(本文主要介绍此种方法,下面的文字都是对此种方法的解读)

(1) 自顶向下的基本思想
     采用分治法进行自顶向下的算法设计,形式更为简洁。
     自顶向下的归并排序:是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为:

      1)划分子表

      2)合并半子表

(1)分治法的三个步骤
     设归并排序的当前区间是R[low..high],分治法的三个步骤是:
①分解:将当前区间一分为二,即求分裂点
②求解:递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序;
③组合:将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件:子区间长度为1(一个记录自然有序)。

如下演示递归的整个过程:

递归便是深度遍历(如下由左至右进行遍历):假设有这样的一列数组{9,8,7,6,5,4,3,2,1}进行划分的顺序如下:

{9,8,7,6,5,4,3,2,1} –> {9,8,7,6,5},{4,3,2,1}

{9,8,7,6,5} –> {9,8,7},{6,5}

                        {9,8,7} –> {9,8},{7}

                                          {9,8} –> {9},{8}

                        {6,5} –>{6},{5}

{4,3,2,1} –> {4,3},{2,1}

                      {4,3} –>{4},{3}

                      {2,1} –>{2},{1}

当深度划分到左右数组都只剩1个元素的时候,进行上述逆序的合并:

{9},{8} –> {8,9} 然后和 {7} –> {7,8,9}

                                {6},{5} –> {5,6}    然后 {7,8,9}和{5,6} –> {5,6,7,8,9}

                                     {2},{1} –> {1,2}

                                     {4},{3} –> {3,4}   然后 {1,2}和 {3,4} –> {1,2,3,4}

                                                                                                                         最终{5,6,7,8,9}和{1,2,3,4} –> {1,2,3,4,5,6,7,8,9}

具体实现代码如下所示:

1
<span>//</span><span>归并排序(目标数组,子表的起始位置,子表的终止位置)</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortFunction(<span>int</span>[] array, <span>int</span> first, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>if</span> (first &lt; last)   <span>//</span><span>子表的长度大于1,则进入下面的递归处理</span><span><br></span>                {<br>                    <span>int</span> mid = (first + last) / <span>2</span>;   <span>//</span><span>子表划分的位置</span><span><br></span>                    MergeSortFunction(array, first, mid);   <span>//</span><span>对划分出来的左侧子表进行递归划分</span><span><br></span>                    MergeSortFunction(array, mid + <span>1</span>, last);    <span>//</span><span>对划分出来的右侧子表进行递归划分</span><span><br></span>                    MergeSortCore(array, first, mid, last); <span>//</span><span>对左右子表进行有序的整合(归并排序的核心部分)</span><span><br></span>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }<br><br>        <span>//</span><span>归并排序的核心部分:将两个有序的左右子表(以mid区分),合并成一个有序的表</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortCore(<span>int</span>[] array, <span>int</span> first, <span>int</span> mid, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>int</span> indexA = first; <span>//</span><span>左侧子表的起始位置</span><span><br></span>                <span>int</span> indexB = mid + <span>1</span>;   <span>//</span><span>右侧子表的起始位置</span><span><br></span>                <span>int</span>[] temp = <span>new</span> <span>int</span>[last + <span>1</span>]; <span>//</span><span>声明数组(暂存左右子表的所有有序数列):长度等于左右子表的长度之和。</span><span><br></span>                <span>int</span> tempIndex = <span>0</span>;<br>                <span>while</span> (indexA &lt;= mid &amp;&amp; indexB &lt;= last) <span>//</span><span>进行左右子表的遍历,如果其中有一个子表遍历完,则跳出循环</span><span><br></span>                {<br>                    <span>if</span> (array[indexA] &lt;= array[indexB]) <span>//</span><span>此时左子表的数 &lt;= 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexA++];    <span>//</span><span>将左子表的数放入暂存数组中,遍历左子表下标++</span><span><br></span>                    }<br>                    <span>else</span><span>//</span><span>此时左子表的数 &gt; 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexB++];    <span>//</span><span>将右子表的数放入暂存数组中,遍历右子表下标++</span><span><br></span>                    }<br>                }<br>                <span>//</span><span>有一侧子表遍历完后,跳出循环,将另外一侧子表剩下的数一次放入暂存数组中(有序)</span><span><br></span>                <span>while</span> (indexA &lt;= mid)<br>                {<br>                    temp[tempIndex++] = array[indexA++];<br>                }<br>                <span>while</span> (indexB &lt;= last)<br>                {<br>                    temp[tempIndex++] = array[indexB++];<br>                }<br><br>                <span>//</span><span>将暂存数组中有序的数列写入目标数组的制定位置,使进行归并的数组段有序</span><span><br></span>                tempIndex = <span>0</span>;<br>                <span>for</span> (<span>int</span> i = first; i &lt;= last; i++)<br>                {<br>                    array[i] = temp[tempIndex++];<br>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }

       对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.

插入排序算法C#实现

Excerpt

插入排序算法主要分为:直接插入算法,折半排序算法(二分插入算法),希尔排序算法,后两种是直接插入算法的改良。因此直接插入算法是基础,这里先进行直接插入算法的分析与编码。直接插入算法的排序思想:假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],


插入排序算法主要分为:直接插入算法,折半排序算法(二分插入算法),希尔排序算法,后两种是直接插入算法的改良。因此直接插入算法是基础,这里先进行直接插入算法的分析与编码。

直接插入算法的排序思想:假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],array[n-1],那么将待排数值array[n]与前面的有序数组从后向前依次比较,直到在有序数组中找到小于待排数值array[n]的位置,将array[n]插入到此位置,并入组合成新的有序数组。

直接插入算法--代码如下所示:

1
<span>     //</span><span>直接插入排序算法(传递待排数组名,即:数组的地址。故形参数组的各种操作反应到实参数组上)</span><span><br></span><span>     private </span><span>static </span><span>void</span><span> InsertSortionFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;   </span><span>//</span><span>临时变量,存储待排的数值</span><span><br></span><span>         for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>将无序的所有数值依次插入到有序数组中,注:下标从1开始,因为操作的是同一个数组</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];    </span><span>//</span><span>记录待插入前面有序数组的数值</span><span><br></span><span>            int</span><span> index </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;  </span><span>//</span><span>记录前方有序数组的末尾位置</span><span><br></span><span>            while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)   </span><span>//</span><span>循环遍历前面的有序数组,并且从大到小依次与待排数值进行比较</span><span><br></span><span>                    {<br>                        array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[index];    </span><span>//</span><span>如果index&gt;=0并且此时的值大于待排数值,将此处的值向后移动一位</span><span><br></span><span>                        index</span><span>--</span><span>;    </span><span>//</span><span>index--向前遍历有序数组</span><span><br></span><span>                    }<br>                    array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;    </span><span>//</span><span>由于前面的index--,所以temp插入的位置是index+1</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

折半排序算法是对直接插入算法的一种优化,优化的核心是:通过折半查看有序数组中间位置的数值(a)与待插入的数值(temp)的大小,如果a>=temp,则转向折半的左区间继续折半查找; 如果a<temp,则转向折半后的右区间继续折半查找。直到左右下标相同时,此时折半的下标也指向相同的位置,再做最后一次循环,最终的结果是:左右下标相差1,并且原来左侧的下标指向大于temp的位置,原来右侧的下标指向了小于temp的位置,即:array[biggerIndex] < temp < array[smallerIndex]。

折半排序算法--代码如下:

1
<span>  &nbsp;   </span><span>//</span><span>折半排序算法(传递待排数组名,即:数组的地址。故形参数组的各种操作反应到实参数组上)</span>
1
<span>        private </span><span>static </span><span>void</span><span> BinaryInsertionSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> smallerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的起始位置</span><span><br></span><span>          int</span><span> biggerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的终止位置</span><span><br></span><span>          int</span><span> midIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录获取有序数组的中间位置(折半法的关键:折半的位置)</span><span><br></span><span>          int</span><span> temp;  </span><span>//</span><span>记录带排的数值</span><span><br></span><span>          for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>循环向有序数组中插入数值(i从1开始,因为操作的是同一个数组)</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];   </span><span>//</span><span>记录待插入有序数组的数值</span><span><br></span><span>                    biggerIndex </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;<br>                    </span><span>//</span><span>当smallerIndex==biggerIndex时,进入最后一次循环:smallerIndex指向大于temp的数组位置,biggerIndex指向小于temp的数组位置</span><span><br></span><span>            while</span><span> (smallerIndex </span><span>&lt;=</span><span> biggerIndex)   <br>                    {<br>                        midIndex </span><span>=</span><span> (smallerIndex </span><span>+</span><span> biggerIndex) </span><span>/</span><span>2</span><span>; </span><span>//</span><span>确定折半的位置</span><span><br></span><span>              if</span><span>(array[midIndex] </span><span>&gt;=</span><span> temp)  </span><span>//</span><span>折半位置的数值 &gt;= temp</span><span><br></span><span>                        {<br>                            biggerIndex </span><span>=</span><span> midIndex </span><span>-</span><span>1</span><span>;    </span><span>//</span><span>biggerIndex以midIndex为基础向前移动一位</span><span><br></span><span>                        }<br>                        </span><span>else</span><span><br>                        {<br>                            smallerIndex </span><span>=</span><span> midIndex </span><span>+</span><span>1</span><span>;  </span><span>//</span><span>smallerIndex以midIndex为基础向后移动一位</span><span><br></span><span>                        }<br>                    }<br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i </span><span>-</span><span>1</span><span>; j </span><span>&gt;</span><span>biggerIndex; j</span><span>--</span><span>) </span><span>//</span><span>将有序数组中大于temp的数值分别向后移动一位</span><span><br></span><span>                    {<br>                        array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[j];  </span><span>//<br></span><span>                    }<br>                    array[biggerIndex </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;   </span><span>//</span><span>将temp插入biggerIndex + 1,因为此时array[biggerIndex]&lt;temp&lt;array[smallerIndex]</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

希尔排序同样是直接插入排序算法的一种改进,基本思想是:将无序的数列划分为若干小的子序列,然后对子序列进行直接插入排序。
时间性能优于直接插入排序算法,但是一种不稳定的排序,时间复杂度为O(nlogn)。
希尔排序算法主要分为3重循环:
第一重循环–>按照gap的大小进行分组,初始化从array.Length/2开始,依次递减到1
第二重循环–>对所有分组进行排序
第三重循环–>组内进行直接插入排序

希尔排序算法--代码如下:

1
<span>      private </span><span>static </span><span>void</span><span> ShellSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>                </span><span>for</span><span> (</span><span>int</span><span> gap </span><span>=</span><span> length </span><span>/</span><span>2</span><span>; gap </span><span>&gt;</span><span>0</span><span>; gap</span><span>--</span><span>)  </span><span>//</span><span>第一重循环,按照gap的大小进行分组</span><span><br></span><span>                {<br>                    </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> gap; i</span><span>++</span><span>)   </span><span>//</span><span>第二重循环,对所有分组进行排序</span><span><br></span><span>                    {<br>                        </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i; j </span><span>&lt;</span><span> length; j </span><span>=</span><span> j </span><span>+</span><span> gap)    </span><span>//</span><span>第三重循环,组内进行直接插入排序</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            </span><span>int</span><span> index </span><span>=</span><span> j </span><span>-</span><span> gap;<br>                            </span><span>while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)<br>                            {<br>                                array[index </span><span>+</span><span> gap] </span><span>=</span><span> array[index];<br>                                index </span><span>=</span><span> index </span><span>-</span><span> gap;<br>                            }<br>                            array[index </span><span>+</span><span> gap] </span><span>=</span><span> temp;<br>                        }<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

。。。。

Qt配置onnx_runtime

首先,onnx_runtime官方也给编译好的release版本,下载即可。但是在qt中配置有一个坑。
在这里插入图片描述
在Qt Creator中正常添加外部库,但是你会发现构建会找不到onnxruntime.lib,这是如果你替换成全路径,即把注释的部分换成下面的lib路径,直接指明onnxruntime.lib。这时构建成功,可以include <onnxruntime_cxx_api.h>,但是在运行你会遇到应用程序无法启动。
在这里插入图片描述
根据百度把onnxruntime.dll复制到.exe目录下。

OK,启动成功。

opencv读取视频流

居中显示,随意拉伸。
在这里插入图片描述
在这里插入图片描述
实现居中的逻辑:

1
// 调整QImage的大小以匹配QLabel的大小 QPixmap scaledPixmap = QPixmap::fromImage(qimg).scaled(ui->Origin_Video->size(), Qt::KeepAspectRatio, Qt::FastTransformation);

而在界面当中需要对窗口随意拉伸,这是就需要界面允许缩放。修改QLabel的属性:
在这里插入图片描述
修改成minimum,并给定最小宽度和高度。(还不知道原因,等有空学习一下)

最后opencv读取视频流并拉取每一帧显示在QLabel中,这里采用的是用一个Qtimer,定时去获取视频帧。

1
// 创建定时器,每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::showNextFrame); timer->start(33); // 设置帧率为30FPS,即每隔33毫秒显示一帧

完整代码如下:

1
// 在槽函数中处理视频的加载和显示 void MainWindow::on_actionvideo_triggered() { camera->stop(); viewfinder->close(); QString curPath = QDir::homePath(); QString dlgTitle = "选择视频文件"; QString filter = "视频文件(*.wmv *.mp4);;所有文件(*.*)"; QString aFile = QFileDialog::getOpenFileName(this, dlgTitle, curPath, filter); if (aFile.isEmpty()) { return; } ui->dir_Edit->setText(aFile); currentSource = File; // 更新当前视频源为视频文件 displayVideo(); // 显示视频 } // 根据当前视频源显示视频的函数 void MainWindow::displayVideo() { if (currentSource == File) { std::string video_path = ui->dir_Edit->text().toLocal8Bit().constData(); cap.open(video_path); if (!cap.isOpened()) { qDebug() << "Error: Unable to open the video file"; return; } // 创建定时器,每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::showNextFrame); timer->start(33); // 设置帧率为30FPS,即每隔33毫秒显示一帧 } else if (currentSource == Camera) { // 创建定时器,每隔一定时间显示下一帧 timer = new QTimer(this); connect(timer, &QTimer::timeout, this, &MainWindow::viewfinderchange); timer->start(33); // 设置帧率为30FPS,即每隔33毫秒显示一帧 // cameras = QCameraInfo::availableCameras(); //获取所有相机的列表 // camera = new QCamera(cameras[0]); //camera指向指定的摄像头 camera->setCaptureMode(QCamera::CaptureStillImage); //设定捕获模式 camera->setViewfinder(viewfinder); //设置取景器 camera->start(); } } // 显示下一帧的槽函数 void MainWindow::showNextFrame() { cv::Mat frame; cap >> frame; // 从视频流中获取一帧 if (frame.empty()) { cap.set(cv::CAP_PROP_POS_FRAMES, 0); // 如果视频结束,重新开始播放 cap >> frame; } currentFrame = frame; // 保存当前帧 displayCurrentFrame(); // 显示当前帧 } void MainWindow::displayCurrentFrame() { // 将OpenCV帧转换为QImage QImage qimg(currentFrame.data, currentFrame.cols, currentFrame.rows, currentFrame.step, QImage::Format_RGB888); qimg = qimg.rgbSwapped(); // 将格式从BGR转换为RGB // 调整QImage的大小以匹配QLabel的大小 QPixmap scaledPixmap = QPixmap::fromImage(qimg).scaled(ui->Origin_Video->size(), Qt::KeepAspectRatio, Qt::FastTransformation); // 将调整大小后的图像居中显示在QLabel中 centerImageInLabel(ui->Origin_Video, scaledPixmap); }

QCamra

居中显示,随意拉伸
在这里插入图片描述
QCamera其实同理,中间拉伸也用了一个QTimer定时获取QLabel的size。
QCamera的使用包括初始化一个camera和设置取景器viewfinder,viewfinder的作用就是控制图像在空间中的展示。

1
void MainWindow::on_actioncamera_triggered() { cameras = QCameraInfo::availableCameras(); //获取所有相机的列表 //qDebug() << "this is camera: "; if (cameras.count() > 0) { for(const QCameraInfo &cameraInfo:cameras) { qDebug() << cameraInfo.description(); } camera = new QCamera(cameras.at(0)); //初始化实例化一个相机对象 } //设置取景器 viewfinder = new QCameraViewfinder(ui->Origin_Video); camera->setViewfinder(viewfinder); centerCameraViewfinderInLabel(viewfinder, ui->Origin_Video); camera->start(); //开启相机 //设置默认摄像头参数 QCameraViewfinderSettings set; // set.setResolution(640, 480); //设置显示分辨率 set.setMaximumFrameRate(30); //设置帧率 camera->setViewfinderSettings(set); stopVideo(); ui->Origin_Video->setPixmap(QPixmap("")); currentSource = Camera; // 更新当前视频源为摄像头 viewfinder->show(); displayVideo(); // 显示视频 }

yolov8 onnx 推理

1
void MainWindow::on_actionTest_triggered() { // std::string projectBasePath = "./"; // Set your ultralytics base path QString qs = QCoreApplication::applicationDirPath(); std::string projectBasePath = qs.toLocal8Bit().constData(); bool runOnGPU = false; // Note that in this example the classes are hard-coded and 'classes.txt' is a place holder. Inference inf(projectBasePath + "/moust_best.onnx", cv::Size(640, 640), "mouse.txt", runOnGPU); std::string video_path = ui->dir_Edit->text().toLocal8Bit().constData(); // 读取视频文件 // cv::VideoCapture cap(projectBasePath + "/video/video.mp4"); cv::VideoCapture cap(video_path); if (!cap.isOpened()) { std::cout << "Error opening video file" << std::endl; return ; } cv::Mat frame; while (cap.read(frame)) { // 推断开始... std::vector<Detection> output = inf.runInference(frame); int detections = output.size(); std::cout << "Number of detections:" << detections << std::endl; for (int i = 0; i < detections; ++i) { Detection detection = output[i]; cv::Rect box = detection.box; cv::Scalar color = detection.color; // Detection box cv::rectangle(frame, box, color, 2); // Detection box text std::string classString = detection.className + ' ' + std::to_string(detection.confidence).substr(0, 4); cv::Size textSize = cv::getTextSize(classString, cv::FONT_HERSHEY_DUPLEX, 1, 2, 0); cv::Rect textBox(box.x, box.y - 40, textSize.width + 10, textSize.height + 20); cv::rectangle(frame, textBox, color, cv::FILLED); cv::putText(frame, classString, cv::Point(box.x + 5, box.y - 10), cv::FONT_HERSHEY_DUPLEX, 1, cv::Scalar(0, 0, 0), 2, 0); } // 推断结束... // 仅用于预览 float scale = 0.8; cv::resize(frame, frame, cv::Size(frame.cols*scale, frame.rows*scale)); cv::imshow("Inference", frame); if (cv::waitKey(1) == 27) { break; } } cap.release(); cv::destroyAllWindows(); }

多线程(onnx推理线程和界面主线程)

在这里插入图片描述
摄像头与onnx互不干扰,说明主界面线程与onnx推理是分开线程进行的,ok!

######################### 2024 05 09 更新 ##############################################

1.环境准备

在这之前,需要先准备主机的环境,环境如下:

Ubuntu18.04
cuda11.3
pytorch:1.11.0
torchvision:0.12.0
在服务器上执行以下命令,

创建yolov8虚拟环境

1
conda create -n yolov8 python=3.8

进入虚拟环境

1
conda activate yolov8

安装pytorch v1.11.0

pytorch v1.11.0(torch1.11.0+cu1113 ,torchvision0.12.0+cu113)

1
# CUDA 11.3 pip install torch==1.11.0+cu113 torchvision==0.12.0+cu113 torchaudio==0.11.0 --extra-index-url https://download.pytorch.org/whl/cu113

下载yolov8的代码

先创建yolov8文件夹,存放等会要下载的yolov8代码mkdir yolov8
进入yolov8文件夹,cd yolov8
下载yolov8代码git clone https://github.com/ultralytics/ultralytics.git

其他配置

1
pip install ultralytics

2.VisDrone数据集准备

数据集下载

github链接上下载:官方链接
下载Task1:Object Detectino in Images下面的四个VisDrone-DET dataset数据集

下载好zip文件后,使用winscp将zip文件传输到远程服务器上。
在服务器上进入到zip文件所在的文件夹中使用unzip命令解压zip文件。
如: unzip VisDrone2019-DET-val.zip

数据集处理

和yolov5所需要的格式一致。参考yolov5数据处理方法。
主要是labels的生成,可以在yolov8下面新建一个visdrone2yolov.py文件。

1
from utils.general import download, os, Path def visdrone2yolo(dir): from PIL import Image from tqdm import tqdm def convert_box(size, box): # Convert VisDrone box to YOLO xywh box dw = 1. / size[0] dh = 1. / size[1] return (box[0] + box[2] / 2) * dw, (box[1] + box[3] / 2) * dh, box[2] * dw, box[3] * dh (dir / 'labels').mkdir(parents=True, exist_ok=True) # make labels directory pbar = tqdm((dir / 'annotations').glob('*.txt'), desc=f'Converting {dir}') for f in pbar: img_size = Image.open((dir / 'images' / f.name).with_suffix('.jpg')).size lines = [] with open(f, 'r') as file: # read annotation.txt for row in [x.split(',') for x in file.read().strip().splitlines()]: if row[4] == '0': # VisDrone 'ignored regions' class 0 continue cls = int(row[5]) - 1 # 类别号-1 box = convert_box(img_size, tuple(map(int, row[:4]))) lines.append(f"{cls} {' '.join(f'{x:.6f}' for x in box)}\n") with open(str(f).replace(os.sep + 'annotations' + os.sep, os.sep + 'labels' + os.sep), 'w') as fl: fl.writelines(lines) # write label.txt dir = Path('/home/yolov5/datasets/VisDrone2019') # datasets文件夹下Visdrone2019文件夹目录 # Convert for d in 'VisDrone2019-DET-train', 'VisDrone2019-DET-val', 'VisDrone2019-DET-test-dev': visdrone2yolo(dir / d) # convert VisDrone annotations to YOLO labels

正确执行代码后,会在’VisDrone2019-DET-train’, ‘VisDrone2019-DET-val’, ‘VisDrone2019-DET-test-dev三个文件夹内新生成labels文件夹,用以存放将VisDrone数据集处理成YoloV8格式后的数据标

修改数据配置文件

记事本或notepad++打开ultralytics-main\ultralytics\datasets\文件夹下的VisDrone.yaml文件,将其中path参数修改为VisDrone2019文件夹所在的路径。

3.训练/验证/导出

训练

打开终端(或者pycharm等IDE),进入虚拟环境,随后进入yolov8文件夹,在终端中输入下面命令,即可开始训练。

1
yolo task=detect mode=train model=yolov8s.pt data=datasets/VisDrone.yaml batch=16 epochs=100 imgsz=640 workers=0 device=0

验证

  1. val数据集上验证
    激活yolov8虚拟环境conda activate yolov8
    进入yolov8文件夹cd pyCode/yolov8/ultralytics/ultralytics/
    使用如下命令,即可完成对验证数据的评估。
    开始验证
1
yolo task=detect mode=val model=runs/detect/train4/weights/best.pt data=datasets/VisDrone.yaml device=0

验证结果如下。

  1. 在test数据集上验证
    将datasets/VisDrone.yaml文件中的val路径修改为:VisDrone2019-DET-test-dev/images
1
# Train/val/test sets as 1) dir: path/to/imgs, 2) file: path/to/imgs.txt, or 3) list: [path/to/imgs1, path/to/imgs2, ..] # path: ../datasets/VisDrone # dataset root dir path: /home/xxx/yolov5/datasets/VisDrone # dataset root dir train: VisDrone2019-DET-train/images # train images (relative to 'path') 6471 images val: VisDrone2019-DET-test-dev/images # val images (relative to 'path') 548 images VisDrone2019-DET-val/images test: VisDrone2019-DET-test-dev/images # test images (optional) 1610 images

使用如下命令,即可完成在VisDrone2019-DET-test-dev数据集上的评估。
开始验证

1
yolo task=detect mode=val model=runs/detect/train4/weights/best.pt data=datasets/VisDrone.yaml device=0

结果如下

导出

使用如下命令即可导出

1
yolo task=detect mode=export model=runs/detect/train4/weights/best.pt

点击这里,观看项目说明视频讲解

本案例 使用 YOLOv8 结合 Python Qt ,开发一个图形界面的 AI实时物品监测程序。

注意

如果你使用其它版本YOLO(比如YOLOv5)训练的模型,请修改相应的导入和检测代码。

您需要高效学习,找工作? 点击咨询 报名实战班

点击查看学员就业情况

示例代码

下面示例代码实现了摄像头实时视频流的YOLO检测。

如果还需要 包含 视频文件实时检测 的功能代码, 请将这个YOLO+Qt视频分享到朋友圈(点击打开),截屏发微给 byhy44

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
<span></span><code><span id="__span-0-1"><span>from</span> <span>PySide6</span> <span>import</span> <span>QtWidgets</span><span>,</span> <span>QtCore</span><span>,</span> <span>QtGui</span>
</span><span id="__span-0-2"><span>import</span> <span>cv2</span><span>,</span> <span>os</span><span>,</span> <span>time</span>
</span><span id="__span-0-3"><span>from</span> <span>threading</span> <span>import</span> <span>Thread</span>
</span><span id="__span-0-4">
</span><span id="__span-0-5"><span># 不然每次YOLO处理都会输出调试信息</span>
</span><span id="__span-0-6"><span>os</span><span>.</span><span>environ</span><span>[</span><span>'YOLO_VERBOSE'</span><span>]</span> <span>=</span> <span>'False'</span>
</span><span id="__span-0-7"><span>from</span> <span>ultralytics</span> <span>import</span> <span>YOLO</span>
</span><span id="__span-0-8">
</span><span id="__span-0-9"><span>class</span> <span>MWindow</span><span>(</span><span>QtWidgets</span><span>.</span><span>QMainWindow</span><span>):</span>
</span><span id="__span-0-10">
</span><span id="__span-0-11"> <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-12">
</span><span id="__span-0-13"> <span>super</span><span>()</span><span>.</span><span>__init__</span><span>()</span>
</span><span id="__span-0-14">
</span><span id="__span-0-15"> <span># 设置界面</span>
</span><span id="__span-0-16"> <span>self</span><span>.</span><span>setupUI</span><span>()</span>
</span><span id="__span-0-17">
</span><span id="__span-0-18"> <span>self</span><span>.</span><span>camBtn</span><span>.</span><span>clicked</span><span>.</span><span>connect</span><span>(</span><span>self</span><span>.</span><span>startCamera</span><span>)</span>
</span><span id="__span-0-19"> <span>self</span><span>.</span><span>stopBtn</span><span>.</span><span>clicked</span><span>.</span><span>connect</span><span>(</span><span>self</span><span>.</span><span>stop</span><span>)</span>
</span><span id="__span-0-20">
</span><span id="__span-0-21"> <span># 定义定时器,用于控制显示视频的帧率</span>
</span><span id="__span-0-22"> <span>self</span><span>.</span><span>timer_camera</span> <span>=</span> <span>QtCore</span><span>.</span><span>QTimer</span><span>()</span>
</span><span id="__span-0-23"> <span># 定时到了,回调 self.show_camera</span>
</span><span id="__span-0-24"> <span>self</span><span>.</span><span>timer_camera</span><span>.</span><span>timeout</span><span>.</span><span>connect</span><span>(</span><span>self</span><span>.</span><span>show_camera</span><span>)</span>
</span><span id="__span-0-25">
</span><span id="__span-0-26"> <span># 加载 YOLO nano 模型,第一次比较耗时,要20秒左右</span>
</span><span id="__span-0-27"> <span>self</span><span>.</span><span>model</span> <span>=</span> <span>YOLO</span><span>(</span><span>'yolov8n.pt'</span><span>)</span>
</span><span id="__span-0-28">
</span><span id="__span-0-29"> <span># 要处理的视频帧图片队列,目前就放1帧图片</span>
</span><span id="__span-0-30"> <span>self</span><span>.</span><span>frameToAnalyze</span> <span>=</span> <span>[]</span>
</span><span id="__span-0-31">
</span><span id="__span-0-32"> <span># 启动处理视频帧独立线程</span>
</span><span id="__span-0-33"> <span>Thread</span><span>(</span><span>target</span><span>=</span><span>self</span><span>.</span><span>frameAnalyzeThreadFunc</span><span>,</span><span>daemon</span><span>=</span><span>True</span><span>)</span><span>.</span><span>start</span><span>()</span>
</span><span id="__span-0-34">
</span><span id="__span-0-35"> <span>def</span> <span>setupUI</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-36">
</span><span id="__span-0-37"> <span>self</span><span>.</span><span>resize</span><span>(</span><span>1200</span><span>,</span> <span>800</span><span>)</span>
</span><span id="__span-0-38">
</span><span id="__span-0-39"> <span>self</span><span>.</span><span>setWindowTitle</span><span>(</span><span>'白月黑羽 YOLO-Qt 演示'</span><span>)</span>
</span><span id="__span-0-40">
</span><span id="__span-0-41"> <span># central Widget</span>
</span><span id="__span-0-42"> <span>centralWidget</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QWidget</span><span>(</span><span>self</span><span>)</span>
</span><span id="__span-0-43"> <span>self</span><span>.</span><span>setCentralWidget</span><span>(</span><span>centralWidget</span><span>)</span>
</span><span id="__span-0-44">
</span><span id="__span-0-45"> <span># central Widget 里面的 主 layout</span>
</span><span id="__span-0-46"> <span>mainLayout</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QVBoxLayout</span><span>(</span><span>centralWidget</span><span>)</span>
</span><span id="__span-0-47">
</span><span id="__span-0-48"> <span># 界面的上半部分 : 图形展示部分</span>
</span><span id="__span-0-49"> <span>topLayout</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QHBoxLayout</span><span>()</span>
</span><span id="__span-0-50"> <span>self</span><span>.</span><span>label_ori_video</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QLabel</span><span>(</span><span>self</span><span>)</span>
</span><span id="__span-0-51"> <span>self</span><span>.</span><span>label_treated</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QLabel</span><span>(</span><span>self</span><span>)</span>
</span><span id="__span-0-52"> <span>self</span><span>.</span><span>label_ori_video</span><span>.</span><span>setMinimumSize</span><span>(</span><span>520</span><span>,</span><span>400</span><span>)</span>
</span><span id="__span-0-53"> <span>self</span><span>.</span><span>label_treated</span><span>.</span><span>setMinimumSize</span><span>(</span><span>520</span><span>,</span><span>400</span><span>)</span>
</span><span id="__span-0-54"> <span>self</span><span>.</span><span>label_ori_video</span><span>.</span><span>setStyleSheet</span><span>(</span><span>'border:1px solid #D7E2F9;'</span><span>)</span>
</span><span id="__span-0-55"> <span>self</span><span>.</span><span>label_treated</span><span>.</span><span>setStyleSheet</span><span>(</span><span>'border:1px solid #D7E2F9;'</span><span>)</span>
</span><span id="__span-0-56">
</span><span id="__span-0-57"> <span>topLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>label_ori_video</span><span>)</span>
</span><span id="__span-0-58"> <span>topLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>label_treated</span><span>)</span>
</span><span id="__span-0-59">
</span><span id="__span-0-60"> <span>mainLayout</span><span>.</span><span>addLayout</span><span>(</span><span>topLayout</span><span>)</span>
</span><span id="__span-0-61">
</span><span id="__span-0-62"> <span># 界面下半部分: 输出框 和 按钮</span>
</span><span id="__span-0-63"> <span>groupBox</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QGroupBox</span><span>(</span><span>self</span><span>)</span>
</span><span id="__span-0-64">
</span><span id="__span-0-65"> <span>bottomLayout</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QHBoxLayout</span><span>(</span><span>groupBox</span><span>)</span>
</span><span id="__span-0-66"> <span>self</span><span>.</span><span>textLog</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QTextBrowser</span><span>()</span>
</span><span id="__span-0-67"> <span>bottomLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>textLog</span><span>)</span>
</span><span id="__span-0-68">
</span><span id="__span-0-69"> <span>mainLayout</span><span>.</span><span>addWidget</span><span>(</span><span>groupBox</span><span>)</span>
</span><span id="__span-0-70">
</span><span id="__span-0-71"> <span>btnLayout</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QVBoxLayout</span><span>()</span>
</span><span id="__span-0-72"> <span>self</span><span>.</span><span>videoBtn</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QPushButton</span><span>(</span><span>'🎞️视频文件'</span><span>)</span>
</span><span id="__span-0-73"> <span>self</span><span>.</span><span>camBtn</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QPushButton</span><span>(</span><span>'📹摄像头'</span><span>)</span>
</span><span id="__span-0-74"> <span>self</span><span>.</span><span>stopBtn</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QPushButton</span><span>(</span><span>'🛑停止'</span><span>)</span>
</span><span id="__span-0-75"> <span>btnLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>videoBtn</span><span>)</span>
</span><span id="__span-0-76"> <span>btnLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>camBtn</span><span>)</span>
</span><span id="__span-0-77"> <span>btnLayout</span><span>.</span><span>addWidget</span><span>(</span><span>self</span><span>.</span><span>stopBtn</span><span>)</span>
</span><span id="__span-0-78"> <span>bottomLayout</span><span>.</span><span>addLayout</span><span>(</span><span>btnLayout</span><span>)</span>
</span><span id="__span-0-79">
</span><span id="__span-0-80">
</span><span id="__span-0-81"> <span>def</span> <span>startCamera</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-82">
</span><span id="__span-0-83"> <span># 参考 https://docs.opencv.org/3.4/dd/d43/tutorial_py_video_display.html</span>
</span><span id="__span-0-84">
</span><span id="__span-0-85"> <span># 在 windows上指定使用 cv2.CAP_DSHOW 会让打开摄像头快很多, </span>
</span><span id="__span-0-86"> <span># 在 Linux/Mac上 指定 V4L, FFMPEG 或者 GSTREAMER</span>
</span><span id="__span-0-87"> <span>self</span><span>.</span><span>cap</span> <span>=</span> <span>cv2</span><span>.</span><span>VideoCapture</span><span>(</span><span>0</span><span>,</span> <span>cv2</span><span>.</span><span>CAP_DSHOW</span><span>)</span>
</span><span id="__span-0-88"> <span>if</span> <span>not</span> <span>self</span><span>.</span><span>cap</span><span>.</span><span>isOpened</span><span>():</span>
</span><span id="__span-0-89"> <span>print</span><span>(</span><span>"1号摄像头不能打开"</span><span>)</span>
</span><span id="__span-0-90"> <span>return</span><span>()</span>
</span><span id="__span-0-91">
</span><span id="__span-0-92"> <span>if</span> <span>self</span><span>.</span><span>timer_camera</span><span>.</span><span>isActive</span><span>()</span> <span>==</span> <span>False</span><span>:</span> <span># 若定时器未启动</span>
</span><span id="__span-0-93"> <span>self</span><span>.</span><span>timer_camera</span><span>.</span><span>start</span><span>(</span><span>50</span><span>)</span>
</span><span id="__span-0-94">
</span><span id="__span-0-95">
</span><span id="__span-0-96"> <span>def</span> <span>show_camera</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-97">
</span><span id="__span-0-98"> <span>ret</span><span>,</span> <span>frame</span> <span>=</span> <span>self</span><span>.</span><span>cap</span><span>.</span><span>read</span><span>()</span> <span># 从视频流中读取</span>
</span><span id="__span-0-99"> <span>if</span> <span>not</span> <span>ret</span><span>:</span>
</span><span id="__span-0-100"> <span>return</span>
</span><span id="__span-0-101">
</span><span id="__span-0-102"> <span># 把读到的16:10帧的大小重新设置 </span>
</span><span id="__span-0-103"> <span>frame</span> <span>=</span> <span>cv2</span><span>.</span><span>resize</span><span>(</span><span>frame</span><span>,</span> <span>(</span><span>520</span><span>,</span> <span>400</span><span>))</span>
</span><span id="__span-0-104"> <span># 视频色彩转换回RGB,OpenCV images as BGR</span>
</span><span id="__span-0-105"> <span>frame</span> <span>=</span> <span>cv2</span><span>.</span><span>cvtColor</span><span>(</span><span>frame</span><span>,</span> <span>cv2</span><span>.</span><span>COLOR_BGR2RGB</span><span>)</span>
</span><span id="__span-0-106"> <span>qImage</span> <span>=</span> <span>QtGui</span><span>.</span><span>QImage</span><span>(</span><span>frame</span><span>.</span><span>data</span><span>,</span> <span>frame</span><span>.</span><span>shape</span><span>[</span><span>1</span><span>],</span> <span>frame</span><span>.</span><span>shape</span><span>[</span><span>0</span><span>],</span>
</span><span id="__span-0-107"> <span>QtGui</span><span>.</span><span>QImage</span><span>.</span><span>Format_RGB888</span><span>)</span> <span># 变成QImage形式</span>
</span><span id="__span-0-108"> <span># 往显示视频的Label里 显示QImage</span>
</span><span id="__span-0-109"> <span>self</span><span>.</span><span>label_ori_video</span><span>.</span><span>setPixmap</span><span>(</span><span>QtGui</span><span>.</span><span>QPixmap</span><span>.</span><span>fromImage</span><span>(</span><span>qImage</span><span>))</span>
</span><span id="__span-0-110">
</span><span id="__span-0-111"> <span># 如果当前没有处理任务</span>
</span><span id="__span-0-112"> <span>if</span> <span>not</span> <span>self</span><span>.</span><span>frameToAnalyze</span><span>:</span>
</span><span id="__span-0-113"> <span>self</span><span>.</span><span>frameToAnalyze</span><span>.</span><span>append</span><span>(</span><span>frame</span><span>)</span>
</span><span id="__span-0-114">
</span><span id="__span-0-115"> <span>def</span> <span>frameAnalyzeThreadFunc</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-116">
</span><span id="__span-0-117"> <span>while</span> <span>True</span><span>:</span>
</span><span id="__span-0-118"> <span>if</span> <span>not</span> <span>self</span><span>.</span><span>frameToAnalyze</span><span>:</span>
</span><span id="__span-0-119"> <span>time</span><span>.</span><span>sleep</span><span>(</span><span>0.01</span><span>)</span>
</span><span id="__span-0-120"> <span>continue</span>
</span><span id="__span-0-121">
</span><span id="__span-0-122"> <span>frame</span> <span>=</span> <span>self</span><span>.</span><span>frameToAnalyze</span><span>.</span><span>pop</span><span>(</span><span>0</span><span>)</span>
</span><span id="__span-0-123">
</span><span id="__span-0-124"> <span>results</span> <span>=</span> <span>self</span><span>.</span><span>model</span><span>(</span><span>frame</span><span>)[</span><span>0</span><span>]</span>
</span><span id="__span-0-125">
</span><span id="__span-0-126"> <span>img</span> <span>=</span> <span>results</span><span>.</span><span>plot</span><span>(</span><span>line_width</span><span>=</span><span>1</span><span>)</span>
</span><span id="__span-0-127">
</span><span id="__span-0-128"> <span>qImage</span> <span>=</span> <span>QtGui</span><span>.</span><span>QImage</span><span>(</span><span>img</span><span>.</span><span>data</span><span>,</span> <span>img</span><span>.</span><span>shape</span><span>[</span><span>1</span><span>],</span> <span>img</span><span>.</span><span>shape</span><span>[</span><span>0</span><span>],</span>
</span><span id="__span-0-129"> <span>QtGui</span><span>.</span><span>QImage</span><span>.</span><span>Format_RGB888</span><span>)</span> <span># 变成QImage形式</span>
</span><span id="__span-0-130">
</span><span id="__span-0-131"> <span>self</span><span>.</span><span>label_treated</span><span>.</span><span>setPixmap</span><span>(</span><span>QtGui</span><span>.</span><span>QPixmap</span><span>.</span><span>fromImage</span><span>(</span><span>qImage</span><span>))</span> <span># 往显示Label里 显示QImage</span>
</span><span id="__span-0-132">
</span><span id="__span-0-133"> <span>time</span><span>.</span><span>sleep</span><span>(</span><span>0.5</span><span>)</span>
</span><span id="__span-0-134">
</span><span id="__span-0-135"> <span>def</span> <span>stop</span><span>(</span><span>self</span><span>):</span>
</span><span id="__span-0-136"> <span>self</span><span>.</span><span>timer_camera</span><span>.</span><span>stop</span><span>()</span> <span># 关闭定时器</span>
</span><span id="__span-0-137"> <span>self</span><span>.</span><span>cap</span><span>.</span><span>release</span><span>()</span> <span># 释放视频流</span>
</span><span id="__span-0-138"> <span>self</span><span>.</span><span>label_ori_video</span><span>.</span><span>clear</span><span>()</span> <span># 清空视频显示区域 </span>
</span><span id="__span-0-139"> <span>self</span><span>.</span><span>label_treated</span><span>.</span><span>clear</span><span>()</span> <span># 清空视频显示区域</span>
</span><span id="__span-0-140">
</span><span id="__span-0-141">
</span><span id="__span-0-142"><span>app</span> <span>=</span> <span>QtWidgets</span><span>.</span><span>QApplication</span><span>()</span>
</span><span id="__span-0-143"><span>window</span> <span>=</span> <span>MWindow</span><span>()</span>
</span><span id="__span-0-144"><span>window</span><span>.</span><span>show</span><span>()</span>
</span><span id="__span-0-145"><span>app</span><span>.</span><span>exec</span><span>()</span>
</span></code>

一、Yolov8简介

1、yolov8 源码地址:

工程链接:https://github.com/ultralytics/ultralytics

2、官方文档:

CLI - Ultralytics YOLOv8 Docs

3、预训练模型百度网盘地址:

训练时需要用到,下载的网址较慢:

如果模型下载不了,加QQ:187100248.

链接: https://pan.baidu.com/s/1YfMxRPGk8LF75a4cbgYxGg 提取码: rd7b

二、模型训练

1、标定红绿灯数据:

         类别为23类,分别为:

红绿灯类别
red_lightgreen_lightyellow_lightoff_lightpart_ry_lightpart_rg_light
part_yg_lightryg_lightcountdown_off_lightcountdown_on_lightshade_lightzero
onetwothreefourfivesix
seveneightninebrokeNumberbrokenLight

        标注工具地址:AI标注工具Labelme和LabelImage Labelme和LabelImage集成工具_labelimage与labelme-CSDN博客

标注后图像格式

2、训练环境:

1)、Ubuntu18.04;

2)、Cuda11.7 + CUDNN8.0.6;

3)、opencv4.5.5;

4)、PyTorch1.8.1-GPU;

5)、python3.9

3、数据转化:

 1)、需要把上面标定的数据集中的.xml文件转换为.txt,转换代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
import os

import shutil

import xml.etree.ElementTree as ET

from xml.etree.ElementTree import Element, SubElement

from PIL import Image

import cv2

classes = ['red_light', 'green_light', 'yellow_light', 'off_light', 'part_ry_light', 'part_rg_light', 'part_yg_light', 'ryg_light',

'countdown_off_light', 'countdown_on_light','shade_light','zero','one','two','three','four','five','six','seven',

'eight','nine','brokeNumber','brokenLight']

class Xml_make(object):

def __init__(self):

super().__init__()

def __indent(self, elem, level=0):

i = "\n" + level * "\t"

if len(elem):

if not elem.text or not elem.text.strip():

elem.text = i + "\t"

if not elem.tail or not elem.tail.strip():

elem.tail = i

for elem in elem:

self.__indent(elem, level + 1)

if not elem.tail or not elem.tail.strip():

elem.tail = i

else:

if level and (not elem.tail or not elem.tail.strip()):

elem.tail = i

def _imageinfo(self, list_top):

annotation_root = ET.Element('annotation')

annotation_root.set('verified', 'no')

tree = ET.ElementTree(annotation_root)

'''

0:xml_savepath 1:folder,2:filename,3:path

4:checked,5:width,6:height,7:depth

'''

folder_element = ET.Element('folder')

folder_element.text = list_top[1]

annotation_root.append(folder_element)

filename_element = ET.Element('filename')

filename_element.text = list_top[2]

annotation_root.append(filename_element)

path_element = ET.Element('path')

path_element.text = list_top[3]

annotation_root.append(path_element)

# checked_element = ET.Element('checked')

# checked_element.text = list_top[4]

# annotation_root.append(checked_element)

source_element = ET.Element('source')

database_element = SubElement(source_element, 'database')

database_element.text = 'Unknown'

annotation_root.append(source_element)

size_element = ET.Element('size')

width_element = SubElement(size_element, 'width')

width_element.text = str(list_top[5])

height_element = SubElement(size_element, 'height')

height_element.text = str(list_top[6])

depth_element = SubElement(size_element, 'depth')

depth_element.text = str(list_top[7])

annotation_root.append(size_element)

segmented_person_element = ET.Element('segmented')

segmented_person_element.text = '0'

annotation_root.append(segmented_person_element)

return tree, annotation_root

def _bndbox(self, annotation_root, list_bndbox):

for i in range(0, len(list_bndbox), 9):

object_element = ET.Element('object')

name_element = SubElement(object_element, 'name')

name_element.text = list_bndbox[i]

# flag_element = SubElement(object_element, 'flag')

# flag_element.text = list_bndbox[i + 1]

pose_element = SubElement(object_element, 'pose')

pose_element.text = list_bndbox[i + 2]

truncated_element = SubElement(object_element, 'truncated')

truncated_element.text = list_bndbox[i + 3]

difficult_element = SubElement(object_element, 'difficult')

difficult_element.text = list_bndbox[i + 4]

bndbox_element = SubElement(object_element, 'bndbox')

xmin_element = SubElement(bndbox_element, 'xmin')

xmin_element.text = str(list_bndbox[i + 5])

ymin_element = SubElement(bndbox_element, 'ymin')

ymin_element.text = str(list_bndbox[i + 6])

xmax_element = SubElement(bndbox_element, 'xmax')

xmax_element.text = str(list_bndbox[i + 7])

ymax_element = SubElement(bndbox_element, 'ymax')

ymax_element.text = str(list_bndbox[i + 8])

annotation_root.append(object_element)

return annotation_root

def txt_to_xml(self, list_top, list_bndbox):

tree, annotation_root = self._imageinfo(list_top)

annotation_root = self._bndbox(annotation_root, list_bndbox)

self.__indent(annotation_root)

tree.write(list_top[0], encoding='utf-8', xml_declaration=True)

def txt_2_xml(source_path, xml_save_dir, jpg_save_dir,txt_dir):

COUNT = 0

for folder_path_tuple, folder_name_list, file_name_list in os.walk(source_path):

for file_name in file_name_list:

file_suffix = os.path.splitext(file_name)[-1]

if file_suffix != '.jpg':

continue

list_top = []

list_bndbox = []

path = os.path.join(folder_path_tuple, file_name)

xml_save_path = os.path.join(xml_save_dir, file_name.replace(file_suffix, '.xml'))

txt_path = os.path.join(txt_dir, file_name.replace(file_suffix, '.txt'))

filename = file_name#os.path.splitext(file_name)[0]

checked = 'NO'

#print(file_name)

im = Image.open(path)

im_w = im.size[0]

im_h = im.size[1]

shutil.copy(path, jpg_save_dir)

if im_w*im_h > 34434015:

print(file_name)

if im_w < 100:

print(file_name)

width = str(im_w)

height = str(im_h)

depth = '3'

flag = 'rectangle'

pose = 'Unspecified'

truncated = '0'

difficult = '0'

list_top.extend([xml_save_path, folder_path_tuple, filename, path, checked, width, height, depth])

for line in open(txt_path, 'r'):

line = line.strip()

info = line.split(' ')

name = classes[int(info[0])]

x_cen = float(info[1]) * im_w

y_cen = float(info[2]) * im_h

w = float(info[3]) * im_w

h = float(info[4]) * im_h

xmin = int(x_cen - w / 2) - 1

ymin = int(y_cen - h / 2) - 1

xmax = int(x_cen + w / 2) + 3

ymax = int(y_cen + h / 2) + 3

if xmin < 0:

xmin = 0

if ymin < 0:

ymin = 0

if xmax > im_w - 1:

xmax = im_w - 1

if ymax > im_h - 1:

ymax = im_h - 1

if w > 5 and h > 5:

list_bndbox.extend([name, flag, pose, truncated, difficult,str(xmin), str(ymin), str(xmax), str(ymax)])

if xmin < 0 or xmax > im_w - 1 or ymin < 0 or ymax > im_h - 1:

print(xml_save_path)

Xml_make().txt_to_xml(list_top, list_bndbox)

COUNT += 1

#print(COUNT, xml_save_path)

if __name__ == "__main__":

out_xml_path = "/home/TL_TrainData/" # .xml输出文件存放地址

out_jpg_path = "/home/TL_TrainData/" # .jpg输出文件存放地址

txt_path = "/home/Data/TrafficLight/trainData" # yolov3标注.txt和图片文件夹

images_path = "/home/TrafficLight/trainData" # image文件存放地址

txt_2_xml(images_path, out_xml_path, out_jpg_path, txt_path)

4、构造训练数据:

2)、训练样本数据构造,需要把分成images和labels,images下面放入图片,labels下面放入.txt文件:

分成images和labels

images

labels

5、训练样本:

 1)、首先安装训练包:

1
pip install ultralytics

2)、修改训练数据参数coco128_light.yaml文件,这个是自己修改的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# Ultralytics YOLO 🚀, AGPL-3.0 license

# COCO128 dataset https://www.kaggle.com/ultralytics/coco128 (first 128 images from COCO train2017) by Ultralytics

# Example usage: yolo train data=coco128.yaml

# parent

# ├── ultralytics

# └── datasets

# └── coco128 ← downloads here (7 MB)

# Train/val/test sets as 1) dir: path/to/imgs, 2) file: path/to/imgs.txt, or 3) list: [path/to/imgs1, path/to/imgs2, ..]

path: /home/Data/TrafficLight/datasets # dataset root dir

train: images # train images (relative to 'path') 128 images

val: images # val images (relative to 'path') 128 images

test: # test images (optional)

# Parameters

nc: 23 # number of classes

# Classes

names:

0: red_light

1: green_light

2: yellow_light

3: off_light

4: part_ry_light

5: part_rg_light

6: part_yg_light

7: ryg_light

8: countdown_off_light

9: countdown_on_light

10: shade_light

11: zero

12: one

13: two

14: three

15: four

16: five

17: six

18: seven

19: eight

20: nine

21: brokeNumber

22: brokenLight

# Download script/URL (optional)

#download: https://ultralytics.com/assets/coco128.zip

3)、执行 train_yolov8x_light.sh,内容为:

1
yolo detect train data=coco128_light.yaml model=./runs/last.pt epochs=100 imgsz=640 workers=16 batch=32

        开始启动训练:

模型训练启动

三、验证模型:

1、图像测试:

1
2
3
4
5
6
7
8
9
from ultralytics import YOLO

model = YOLO('best.pt')

results = model('bus.jpg')

for r in results:

print(r.boxes)

2、视频测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import cv2

from ultralytics import YOLO

# Load the YOLOv8 model

model = YOLO('best.pt')

# Open the video file

video_path = "test_car_person_1080P.mp4"

cap = cv2.VideoCapture(video_path)

# Loop through the video frames

while cap.isOpened():

# Read a frame from the video

success, frame = cap.read()

if success:

# Run YOLOv8 inference on the frame

results = model(frame)

# Visualize the results on the frame

annotated_frame = results[0].plot()

# Display the annotated frame

cv2.imshow("YOLOv8 Inference", annotated_frame)

cv2.waitKey(10)

四、导出ONNX

1、训练输出,经过上面的训练后,得到训练生成文件,weights下生成了best.pt和last.pt:

训练数据生成文件

2、等训练完毕后,利用best.pt生成best.onnx,执行命令如下:

1
yolo export model=best.pt imgsz=640 format=onnx opset=12

五、Opencv实现Yolov8 C++ 识别

1、开发环境:

1)、win7/win10;

2)、vs2019;

3)、opencv4.7.0;

2、main函数代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>

#include <vector>

#include "opencv2/opencv.hpp"

#include "inference.h"

#include <io.h>

#include <thread>

#define socklen_t int

#pragma comment (lib, "ws2_32.lib")

using namespace std;

using namespace cv;

int getFiles(std::string path, std::vector<std::string>& files, std::vector<std::string>& names)

{

int i = 0;

intptr_t hFile = 0;

struct _finddata_t c_file;

std::string imageFile = path + "*.*";

if ((hFile = _findfirst(imageFile.c_str(), &c_file)) == -1L)

{

_findclose(hFile);

return -1;

}

else

{

while (true)

{

std::string strname(c_file.name);

if (std::string::npos != strname.find(".jpg") || std::string::npos != strname.find(".png") || std::string::npos != strname.find(".bmp"))

{

std::string fullName = path + c_file.name;

files.push_back(fullName);

std::string cutname = strname.substr(0, strname.rfind("."));

names.push_back(cutname);

}

if (_findnext(hFile, &c_file) != 0)

{

_findclose(hFile);

break;

}

}

}

return 0;

}

int main()

{

std::string projectBasePath = "./"; // Set your ultralytics base path

bool runOnGPU = true;

//

// Pass in either:

//

// "yolov8s.onnx" or "yolov5s.onnx"

//

// To run Inference with yolov8/yolov5 (ONNX)

//

// Note that in this example the classes are hard-coded and 'classes.txt' is a place holder.

Inference inf(projectBasePath + "/best.onnx", cv::Size(640, 640), "classes.txt", runOnGPU);

std::vector<std::string> files;

std::vector<std::string> names;

getFiles("./test/", files, names);

//std::vector<std::string> imageNames;

//imageNames.push_back(projectBasePath + "/test/20221104_8336.jpg");

//imageNames.push_back(projectBasePath + "/test/20221104_8339.jpg");

for (int i = 0; i < files.size(); ++i)

{

cv::Mat frame = cv::imread(files[i]);

// Inference starts here...

clock_t start, end;

float time;

start = clock();

std::vector<Detection> output = inf.runInference(frame);

end = clock();

time = (float)(end - start);//CLOCKS_PER_SEC;

printf("timeCount = %f\n", time);

int detections = output.size();

std::cout << "Number of detections:" << detections << std::endl;

for (int i = 0; i < detections; ++i)

{

Detection detection = output[i];

cv::Rect box = detection.box;

cv::Scalar color = detection.color;

// Detection box

cv::rectangle(frame, box, color, 2);

// Detection box text

std::string classString = detection.className + ' ' + std::to_string(detection.confidence).substr(0, 4);

cv::Size textSize = cv::getTextSize(classString, cv::FONT_HERSHEY_DUPLEX, 1, 2, 0);

cv::Rect textBox(box.x, box.y - 40, textSize.width + 10, textSize.height + 20);

cv::rectangle(frame, textBox, color, cv::FILLED);

cv::putText(frame, classString, cv::Point(box.x + 5, box.y - 10), cv::FONT_HERSHEY_DUPLEX, 1, cv::Scalar(0, 0, 0), 2, 0);

}

// Inference ends here...

// This is only for preview purposes

float scale = 0.8;

cv::resize(frame, frame, cv::Size(frame.cols * scale, frame.rows * scale));

cv::imshow("Inference", frame);

cv::waitKey(10);

}

}

3、yolov8 头文件inference.h代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#ifndef INFERENCE_H

#define INFERENCE_H

// Cpp native

#include <fstream>

#include <vector>

#include <string>

#include <random>

// OpenCV / DNN / Inference

#include <opencv2/imgproc.hpp>

#include <opencv2/opencv.hpp>

#include <opencv2/dnn.hpp>

struct Detection

{

int class_id{0};

std::string className{};

float confidence{0.0};

cv::Scalar color{};

cv::Rect box{};

};

class Inference

{

public:

Inference(const std::string &onnxModelPath, const cv::Size &modelInputShape = {640, 640}, const std::string &classesTxtFile = "", const bool &runWithCuda = true);

std::vector<Detection> runInference(const cv::Mat &input);

private:

void loadClassesFromFile();

void loadOnnxNetwork();

cv::Mat formatToSquare(const cv::Mat &source);

std::string modelPath{};

std::string classesPath{};

bool cudaEnabled{};

std::vector<std::string> classes{ "red_light", "green_light", "yellow_light", "off_light", "part_ry_light", "part_rg_light", "part_yg_light", "ryg_light","countdown_off_light", "countdown_on_light","shade_light","zero","one","two","three","four","five","six","seven","eight","nine","brokeNumber","brokenLight" };

cv::Size2f modelShape{};

float modelConfidenceThreshold {0.25};

float modelScoreThreshold {0.45};

float modelNMSThreshold {0.50};

bool letterBoxForSquare = true;

cv::dnn::Net net;

};

#endif // INFERENCE_H

4、yolov8 cpp文件inference.cpp代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
#include "inference.h"

Inference::Inference(const std::string &onnxModelPath, const cv::Size &modelInputShape, const std::string &classesTxtFile, const bool &runWithCuda)

{

modelPath = onnxModelPath;

modelShape = modelInputShape;

classesPath = classesTxtFile;

cudaEnabled = runWithCuda;

loadOnnxNetwork();

// loadClassesFromFile(); The classes are hard-coded for this example

}

std::vector<Detection> Inference::runInference(const cv::Mat &input)

{

cv::Mat modelInput = input;

if (letterBoxForSquare && modelShape.width == modelShape.height)

modelInput = formatToSquare(modelInput);

cv::Mat blob;

cv::dnn::blobFromImage(modelInput, blob, 1.0/255.0, modelShape, cv::Scalar(), true, false);

net.setInput(blob);

std::vector<cv::Mat> outputs;

net.forward(outputs, net.getUnconnectedOutLayersNames());

int rows = outputs[0].size[1];

int dimensions = outputs[0].size[2];

bool yolov8 = false;

// yolov5 has an output of shape (batchSize, 25200, 85) (Num classes + box[x,y,w,h] + confidence[c])

// yolov8 has an output of shape (batchSize, 84, 8400) (Num classes + box[x,y,w,h])

if (dimensions > rows) // Check if the shape[2] is more than shape[1] (yolov8)

{

yolov8 = true;

rows = outputs[0].size[2];

dimensions = outputs[0].size[1];

outputs[0] = outputs[0].reshape(1, dimensions);

cv::transpose(outputs[0], outputs[0]);

}

float *data = (float *)outputs[0].data;

float x_factor = modelInput.cols / modelShape.width;

float y_factor = modelInput.rows / modelShape.height;

std::vector<int> class_ids;

std::vector<float> confidences;

std::vector<cv::Rect> boxes;

for (int i = 0; i < rows; ++i)

{

if (yolov8)

{

float *classes_scores = data+4;

cv::Mat scores(1, classes.size(), CV_32FC1, classes_scores);

cv::Point class_id;

double maxClassScore;

minMaxLoc(scores, 0, &maxClassScore, 0, &class_id);

if (maxClassScore > modelScoreThreshold)

{

confidences.push_back(maxClassScore);

class_ids.push_back(class_id.x);

float x = data[0];

float y = data[1];

float w = data[2];

float h = data[3];

int left = int((x - 0.5 * w) * x_factor);

int top = int((y - 0.5 * h) * y_factor);

int width = int(w * x_factor);

int height = int(h * y_factor);

boxes.push_back(cv::Rect(left, top, width, height));

}

}

else // yolov5

{

float confidence = data[4];

if (confidence >= modelConfidenceThreshold)

{

float *classes_scores = data+5;

cv::Mat scores(1, classes.size(), CV_32FC1, classes_scores);

cv::Point class_id;

double max_class_score;

minMaxLoc(scores, 0, &max_class_score, 0, &class_id);

if (max_class_score > modelScoreThreshold)

{

confidences.push_back(confidence);

class_ids.push_back(class_id.x);

float x = data[0];

float y = data[1];

float w = data[2];

float h = data[3];

int left = int((x - 0.5 * w) * x_factor);

int top = int((y - 0.5 * h) * y_factor);

int width = int(w * x_factor);

int height = int(h * y_factor);

boxes.push_back(cv::Rect(left, top, width, height));

}

}

}

data += dimensions;

}

std::vector<int> nms_result;

cv::dnn::NMSBoxes(boxes, confidences, modelScoreThreshold, modelNMSThreshold, nms_result);

std::vector<Detection> detections{};

for (unsigned long i = 0; i < nms_result.size(); ++i)

{

int idx = nms_result[i];

Detection result;

result.class_id = class_ids[idx];

result.confidence = confidences[idx];

std::random_device rd;

std::mt19937 gen(rd());

std::uniform_int_distribution<int> dis(100, 255);

result.color = cv::Scalar(dis(gen),

dis(gen),

dis(gen));

result.className = classes[result.class_id];

result.box = boxes[idx];

detections.push_back(result);

}

return detections;

}

void Inference::loadClassesFromFile()

{

std::ifstream inputFile(classesPath);

if (inputFile.is_open())

{

std::string classLine;

while (std::getline(inputFile, classLine))

classes.push_back(classLine);

inputFile.close();

}

}

void Inference::loadOnnxNetwork()

{

net = cv::dnn::readNetFromONNX(modelPath);

if (cudaEnabled)

{

std::cout << "\nRunning on CUDA" << std::endl;

net.setPreferableBackend(cv::dnn::DNN_BACKEND_CUDA);

net.setPreferableTarget(cv::dnn::DNN_TARGET_CUDA);

}

else

{

std::cout << "\nRunning on CPU" << std::endl;

net.setPreferableBackend(cv::dnn::DNN_BACKEND_OPENCV);

net.setPreferableTarget(cv::dnn::DNN_TARGET_CPU);

}

}

cv::Mat Inference::formatToSquare(const cv::Mat &source)

{

int col = source.cols;

int row = source.rows;

int _max = MAX(col, row);

cv::Mat result = cv::Mat::zeros(_max, _max, CV_8UC3);

source.copyTo(result(cv::Rect(0, 0, col, row)));

return result;

}

4、效果图:

vs2019工程运行结果

红绿灯识别结果

安装

1
2
3
4
5
6
7
8
9

sudo apt install lm-sensors curl hddtemp # 安装工具

sensors-detect # 检测传感器

sudo apt install conky # 安装

conky & # 运行conky

传感器数据样例

1
2
3
4
5
6
7
8
9
acpitz-virtual-0-
Adapter: Virtual device
temp1: +49.5°C (crit = +99.0°C)

coretemp-isa-0000
Adapter: ISA adapter
Physical id 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 1: +49.0°C (high = +100.0°C, crit = +100.0°C)

:TODO conky 默认运行效果截图

conky默认以一个弹窗的形式运行,并使用位于/etc/conky/conky.conf的基础配置文件

集成到桌面

1
2
cp /etc/conky/conky.conf /home/$USER/.conkyrc # 复制默认配置文件

0%