一、常見排序算法一覽：
時(shí)間復(fù)雜度：? 是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。
空間復(fù)雜度：一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。
穩(wěn)定性：保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同就穩(wěn)定，反之不穩(wěn)定。
二、算法C#實(shí)現(xiàn)：
1、直接插入排序：
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespace csharpconsole{? ? class Program? ? {/*
具體算法描述如下：
1.從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復(fù)步驟2~5
*/publicstaticvoidInsertSort(int[] List)? ? ? ? {inttmp =0;intlen = List.Length;inti =0;intj =0;for(i =1; i < len; i++)? ? ? ? ? ? {? ? ? ? ? ? ? ? tmp = List[i];for(j = i -1; j >=0; j--)? ? ? ? ? ? ? ? {if(tmp < List[j])? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? List[j +1] = List[j];? ? ? ? ? ? ? ? ? ? }elseif(tmp > List[j])? ? ? ? ? ? ? ? ? ? {break;? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? List[j +1] = tmp;? ? ? ? ? ? }return;? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? InsertSort(intArr);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
2、希爾排序：
實(shí)際上是分組的插入排序?？s小增量排序。先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把表的全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中,在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1。
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespace csharpconsole{? ? class Program? ? {publicstaticvoidShellSort(int[] List)? ? ? ? {inttmp =0;intlen = List.Length;inti =0;intj =0;intd = len /2;/* 初始步長(zhǎng)取數(shù)組長(zhǎng)度的一半 *//* 觀察看如果d=1的話，即是普通的插入排序算法 */while(d >=1)? ? ? ? ? ? {/* 把距離為 d 的元素編為一個(gè)組，掃描所有組 */for(i = d; i < len; i++)? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? tmp = List[i];for(j = i - d; j >=0; j = j - d)? ? ? ? ? ? ? ? ? ? {if(tmp < List[j])? ? ? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? ? ? List[j + d] = List[j];? ? ? ? ? ? ? ? ? ? ? ? }elseif(tmp > List[j])? ? ? ? ? ? ? ? ? ? ? ? {break;? ? ? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? ? ? List[j + d] = tmp;? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? d = d /2;? ? ? ? ? ? }return;? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? ShellSort(intArr);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
3、冒泡排序（交換排序）：
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespacecsharpconsole{classProgram{publicstaticvoidBubbleSort(int[] List)? ? ? ? {inti =0;intj =0;intlen = List.Length;intswap =0;/*
第一趟排序：通過兩兩比較，找到第一小的數(shù)值 1 ，將其放在序列的第一位。
第二趟排序：通過兩兩比較，找到第二小的數(shù)值 2 ，將其放在序列的第二位。
第三趟排序：通過兩兩比較，找到第三小的數(shù)值 3 ，將其放在序列的第三位。
至此，所有元素已經(jīng)有序，排序結(jié)束。
*/for(i = len -1; i >=0; i--)? ? ? ? ? ? {for(j = len -1; j >= len - i; j--)? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? if (List[j] < List[j -1])? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? swap = List[j];? ? ? ? ? ? ? ? ? ? ? ? List[j] = List[j -1];? ? ? ? ? ? ? ? ? ? ? ? List[j -1] = swap;? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }? ? ? ? ? ? }return;? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? BubbleSort(intArr);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
4、快速排序(交換排序)：
步驟：
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespacecsharpconsole{classProgram{publicstaticvoidQuickSort(int[] List,intleft,intright)? ? ? ? {intbaseNum =0;intlow =0;inthigh =0;? ? ? ? ? ? if (left < right)? ? ? ? ? ? {? ? ? ? ? ? ? ? baseNum = List[left];? ? ? ? ? ? ? ? low = left;? ? ? ? ? ? ? ? high = right;while(low < high)? ? ? ? ? ? ? ? {/* 從右往左掃描 */while((high > low) && (baseNum < List[high]))? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? high--;? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? ? ? List[low] = List[high];/* 從左往右掃描 */while((low < high) && (baseNum > List[high]))? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? low++;? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? ? ? List[high] = List[low];? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? List[low] = baseNum;? ? ? ? ? ? ? ? QuickSort(List, left, low -1);? ? ? ? ? ? ? ? QuickSort(List, low +1, right);? ? ? ? ? ? }return;? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? QuickSort(intArr,0, intArr.Length -1);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
(1) 從待排序序列中，找到關(guān)鍵字最小的元素；
(2) 如果最小元素不是待排序序列的第一個(gè)元素，將其和第一個(gè)元素互換；
(3) 從余下的 N - 1 個(gè)元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)、(2)步，直到排序結(jié)束。
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace csharpconsole{classProgram{publicstaticvoidSelectionSort(int[] List)? ? ? ? {intindex=0;intswap =0;intlen = List.Length;inti =0;intj =0;for(; i < len; i++)? ? ? ? ? ? {/* 找到這一趟循環(huán)最小的值，記錄下標(biāo)，默認(rèn)下標(biāo)為i */index= i;for(j = i +1; j < len; j++)? ? ? ? ? ? ? ? {if(List[j] < List[index])? ? ? ? ? ? ? ? ? ? {index= j;? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? }/* 如果下標(biāo)有改變，就交換數(shù)值 */if(index!= i)? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? swap = List[i];? ? ? ? ? ? ? ? ? ? List[i] = List[index];? ? ? ? ? ? ? ? ? ? List[index] = swap;? ? ? ? ? ? ? ? }? ? ? ? ? ? }return;? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? SelectionSort(intArr);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
6、堆排序：
步驟：
（1）根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個(gè)完全二叉樹，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）。
（2）每次交換第一個(gè)和最后一個(gè)元素，輸出最后一個(gè)元素（最大值），然后把剩下元素重新調(diào)整為大根堆。
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespacecsharpconsole{classProgram? ? {publicstaticvoidHeapAdjust(int[]array,intparent,intlength)? ? ? ? {inttemp =array[parent];// temp保存當(dāng)前父節(jié)點(diǎn)intchild =2* parent +1;// 先獲得左孩子while(child < length)? ? ? ? ? ? {// 如果有右孩子結(jié)點(diǎn)，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)，則選取右孩子結(jié)點(diǎn)if(child +1< length &&array[child] =array[child])? ? ? ? ? ? ? ? {break;? ? ? ? ? ? ? ? }// 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)array[parent] =array[child];// 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選parent = child;? ? ? ? ? ? ? ? child =2* child +1;? ? ? ? ? ? }array[parent] = temp;? ? ? ? }publicstaticvoidHeapSort(int[]list)? ? ? ? {// 循環(huán)建立初始堆for(inti =list.Length /2; i >=0; i--)? ? ? ? ? ? {? ? ? ? ? ? ? ? HeapAdjust(list, i,list.Length -1);? ? ? ? ? ? }// 進(jìn)行n-1次循環(huán)，完成排序for(inti =list.Length -1; i >0; i--)? ? ? ? ? ? {// 最后一個(gè)元素和第一元素進(jìn)行交換inttemp =list[i];list[i] =list[0];list[0] = temp;// 篩選 R[0] 結(jié)點(diǎn)，得到i-1個(gè)結(jié)點(diǎn)的堆HeapAdjust(list,0, i);? ? ? ? ? ? }? ? ? ? }staticvoidMain(string[] args)? ? ? ? {int[] intArr = {10,2,56,12,6,78,34,23,9,18,7};? ? ? ? ? ? HeapSort(intArr);for(intk =0; k < intArr.Length; k++)? ? ? ? ? ? Console.WriteLine(intArr[k]);? ? ? ? ? ? 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
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
7、歸并排序：
步驟：
（1）“分解”——將序列每次折半劃分。
（2）“合并”——將劃分后的序列段兩兩合并后排序。
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;namespacecsharpconsole{classProgram? ? {publicstaticvoidMerge(int[]array,intlow,intmid,inthigh)? ? ? ? {inti = low;// i是第一段序列的下標(biāo)intj = mid +1;// j是第二段序列的下標(biāo)intk =0;// k是臨時(shí)存放合并序列的下標(biāo)int[] array2 =newint[high - low +1];// array2是臨時(shí)合并序列// 掃描第一段和第二段序列，直到有一個(gè)掃描結(jié)束while(i <= mid && j <= high)? ? ? ? ? ? {// 判斷第一段和第二段取出的數(shù)哪個(gè)更小，將其存入合并序列，并繼續(xù)向下掃描if(array[i] <=array[j])? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? array2[k] =array[i];? ? ? ? ? ? ? ? ? ? i++;? ? ? ? ? ? ? ? ? ? k++;? ? ? ? ? ? ? ? }else{? ? ? ? ? ? ? ? ? ? array2[k] =array[j];? ? ? ? ? ? ? ? ? ? j++;? ? ? ? ? ? ? ? ? ? k++;? ? ? ? ? ? ? ? }? ? ? ? ? ? }// 若第一段序列還沒掃描完，將其全部復(fù)制到合并序列while(i <= mid)? ? ? ? ? ? {? ? ? ? ? ? ? ? array2[k] =array[i];? ? ? ? ? ? ? ? i++;? ? ? ? ? ? ? ? k++;? ? ? ? ? ? }// 若第二段序列還沒掃描完，將其全部復(fù)制到合并序列while(j <= high)? ? ? ? ? ? {? ? ? ? ? ? ? ? array2[k] =array[j];? ? ? ? ? ? ? ? j++;? ? ? ? ? ? ? ? k++;? ? ? ? ? ? }// 將合并序列復(fù)制到原始序列中for(k =0, i = low; i <= high; i++, k++)? ? ? ? ? ? {array[i] = array2[k];? ? ? ? ? ? }? ? ? ? }publicstaticvoidMergePass(int[]array,intgap,intlength)? ? ? ? {inti =0;// 歸并gap長(zhǎng)度的兩個(gè)相鄰子表for(i =0; i +2* gap -1< length; i = i +2* gap)? ? ? ? ? ? {? ? ? ? ? ? ? ? Merge(array, i, i + gap -1, i +2* gap -1);? ? ? ? ? ? }// 余下兩個(gè)子表，后者長(zhǎng)度小于gapif(i + gap -1< length)? ? ? ? ? ? {? ? ? ? ? ? ? ? Merge(array, i, i + gap -1, length -1);? ? ? ? ? ? }? ? ? ? }publicstaticint[] MergeSort(int[]list)? ? ? ? {for(intgap =1; gap
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
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
頂
0
踩
0
