Chemmy's Blog

chengming0916@outlook.com

发表于 更新于 分类于 ，

堆排序算法（C#实现）

Excerpt

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储区，是软件系统可以编程的内存区域。本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例堆排序的时间复杂度是O(nlog2n),与快速

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：

一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。

另一种是垃圾收集存储区，是软件系统可以编程的内存区域。

本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例

堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.

**堆排序
**堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。

基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆

堆与数组的关系

堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ， 右节点在数组中的位置（数组下标）为 i * 2 + 2 。

以上是基本的知识点，具体代码如下所示：

复制代码

1
<span>        //</span><span>堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> HeapSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                BuildMaxHeap(array);    </span><span>//</span><span>创建大顶推（初始状态看做：整体无序）</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>-</span><span>1</span><span>; i </span><span>&gt;</span><span>0</span><span>; i</span><span>--</span><span>)<br>                {<br>                    Swap(</span><span>ref</span><span> array[</span><span>0</span><span>], </span><span>ref</span><span> array[i]); </span><span>//</span><span>将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）</span><span><br></span><span>                    MaxHeapify(array, </span><span>0</span><span>, i); </span><span>//</span><span>重新将无序区调整为大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 创建大顶推（根节点大于左右子节点）<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待排数组</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> BuildMaxHeap(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>//</span><span>根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>/</span><span>2</span><span>-</span><span>1</span><span>; i </span><span>&gt;=</span><span>0</span><span>; i</span><span>--</span><span>) </span><span>//</span><span>从最底层的最后一个根节点开始进行大顶推的调整</span><span><br></span><span>                {<br>                    MaxHeapify(array, i, array.Length); </span><span>//</span><span>调整大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 大顶推的调整过程<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待调整的数组</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="currentIndex"&gt;</span><span>待调整元素在数组中的位置（即：根节点）</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="heapSize"&gt;</span><span>堆中所有元素的个数</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> MaxHeapify(</span><span>int</span><span>[] array, </span><span>int</span><span> currentIndex, </span><span>int</span><span> heapSize)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> left </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>1</span><span>;    </span><span>//</span><span>左子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> right </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>2</span><span>;   </span><span>//</span><span>右子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> large </span><span>=</span><span> currentIndex;   </span><span>//</span><span>记录此根节点、左子节点、右子节点 三者中最大值的位置</span><span><br></span><span><br>                </span><span>if</span><span> (left </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[left] </span><span>&gt;</span><span> array[large])  </span><span>//</span><span>与左子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> left;<br>                }<br>                </span><span>if</span><span> (right </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[right] </span><span>&gt;</span><span> array[large])    </span><span>//</span><span>与右子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> right;<br>                }<br>                </span><span>if</span><span> (currentIndex </span><span>!=</span><span> large)  </span><span>//</span><span>如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）</span><span><br></span><span>                {<br>                    Swap(</span><span>ref</span><span> array[currentIndex], </span><span>ref</span><span> array[large]);    </span><span>//</span><span>将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）</span><span><br></span><span>                    MaxHeapify(array, large, heapSize); </span><span>//</span><span>以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 交换函数<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="a"&gt;</span><span>元素a</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="b"&gt;</span><span>元素b</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　　private </span><span>static </span><span>void</span><span> Swap(</span><span>ref</span><span>int</span><span> a, </span><span>ref</span><span>int</span><span> b)<br>        {<br>            </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>            temp </span><span>=</span><span> a;<br>            a </span><span>=</span><span> b;<br>            b </span><span>=</span><span> temp;<br>        }</span>

复制代码

发表于 更新于 分类于 ，

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# 经典排序算法大全

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#实现） - 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

自顶向下的归并排序：是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：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>

复制代码

。。。。

发表于 更新于 分类于

安装

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%