C#时间戳

发表于 2020-04-28 更新于 2025-08-04 Valine：

来源：https://blog.guoqianfan.com/2019/11/24/timestamp-in-csharp/

什么是时间戳

时间戳默认是Unix时间戳。

首先要清楚JavaScript与Unix的时间戳的区别：

JavaScript时间戳：是指格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总毫秒数。

Unix时间戳：是指格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总秒数。

可以看出JavaScript时间戳是总毫秒数，Unix时间戳是总秒数。

比如同样是的 2016/11/03 12:30:00 ，转换为JavaScript时间戳为 1478147400000；转换为Unix时间戳为 1478147400。

从上面也可以看出时间戳与时区无关。

Unix时间戳相互转换

C# DateTime转换为Unix时间戳

.NET 4.6新方法

只能在 .NET 4.6及更高版本里才能使用。

1 2	long timeStamp = DateTimeOffset.Now.ToUnixTimeSeconds(); Console.WriteLine(timeStamp);

通用的老方法

1
2
3

System.DateTime startTime = TimeZone.CurrentTimeZone.ToLocalTime(new System.DateTime(1970, 1, 1)); 
long timeStamp = (long)(DateTime.Now - startTime).TotalSeconds; 
System.Console.WriteLine(timeStamp);

Unix时间戳转换为C# DateTime

.NET 4.6新方法

由时间戳转换的DateTimeOffset的时区默认是+00:00，此时我们需要转为本地时区，否则后续使用可能会有问题。

转为本地时区：DateTimeOffset.LocalDateTime。

示例代码如下：


DateTimeOffset dto = DateTimeOffset.FromUnixTimeMilliseconds(1573696406184);

DateTime dt01 = dto.DateTime;

DateTime dt02 = dto.LocalDateTime;

通用的老方法

long unixTimeStamp = 1478162177;
System.DateTime startTime = TimeZone.CurrentTimeZone.ToLocalTime(new System.DateTime(1970, 1, 1)); 
DateTime dt = startTime.AddSeconds(unixTimeStamp);
System.Console.WriteLine(dt.ToString("yyyy/MM/dd HH:mm:ss:ffff"));

备注

DateTimeOffset使用Now还是UtcNow

对于DateTimeOffset，发现有2个获取当前时间的属性：DateTimeOffset.Now和DateTimeOffset.UtcNow。

如果只是获取时间戳，这2个使用哪个都可以，得到的值是一样的。

因为DateTimeOffset里面有时区信息，获取时间戳时会使用时区进行转换的，所以获得的时间戳一样。

而也是因为时区的原因，DateTimeOffset的其他操作可能会不一样。例如DateTimeOffset.DateTime就不一样，此时推荐使用DateTimeOffset.LocalDateTime来获得本地时区的时间。

测试代码如下：


Console.WriteLine("none：{0}", DateTimeOffset.Now);

Console.WriteLine("utc：{0}", DateTimeOffset.UtcNow);


Console.WriteLine("none：{0}", DateTimeOffset.Now.ToUnixTimeSeconds());

Console.WriteLine("utc：{0}", DateTimeOffset.UtcNow.ToUnixTimeSeconds());

DateTime转换为DateTimeOffset

可以直接把DateTime赋值给DateTimeOffset，内部会自动进行隐式转换。这里涉及到时区，请往下看。

DateTime的时区信息(Kind属性)

DateTime的时区信息存放在Kind属性里。Kind属性的数据类型是DateTimeKind枚举，只有3个值：

Unspecified：未指定/未规定
Utc：UTC时间
Local：本地时区

不同情况下得到的DateTime的Kind是不同的，具体如下：

DateTime.Now：DateTime.Kind是 **Local(本地时区)**。
DateTime.UtcNow：DateTime.Kind是 **Utc**。
DateTime.Parse()：
- 【默认】在未指定时区时，DateTime.Kind是 Unspecified
- 指定时区：指定时区后DateTime.Kind就是相对应的值。
  
  指定时区有2种方式：
  - 【默认+优先】待转换的字符串里有时区信息。例如：2019/11/24 17:40:32 +08:00
  - 使用DateTimeStyles参数来指定时区。DateTimeStyles是枚举类型，更多信息自己查看定义，这里不再多说。

Local和Utc都会把相应的时区传递过去。对于 Unspecified(未指定)，会被当做本地时区来处理（结果已验证，源码没看懂）。

测试代码


DateTime dtNow = DateTime.Now;

DateTime dtUtcNow = DateTime.UtcNow;

DateTime dtParse = DateTime.Parse("2019-11-24 17:40:13");


DateTimeOffset dtoNow = dtNow;

DateTimeOffset dtoUtcNow = dtUtcNow;

DateTimeOffset dtoParse = dtParse;

Console.WriteLine("DateTime：");
Console.WriteLine("dtNow：{0}(Kind：{1})", dtNow, dtNow.Kind);
Console.WriteLine("dtUtcNow：{0}(Kind：{1})", dtUtcNow, dtUtcNow.Kind);
Console.WriteLine("dtParse：{0}(Kind：{1})", dtParse, dtParse.Kind);

Console.WriteLine();

Console.WriteLine("DateTimeOffset：");
Console.WriteLine("dtoNow：{0}", dtoNow);
Console.WriteLine("dtoUtcNow：{0}", dtoUtcNow);
Console.WriteLine("dtoParse：{0}", dtoParse);

输出结果如下：

DateTime：
dtNow：2019/11/24 17:40:32(Kind：Local)
dtUtcNow：2019/11/24 9:40:32(Kind：Utc)
dtParse：2019/11/24 17:40:13(Kind：Unspecified)

DateTimeOffset：
dtoNow：2019/11/24 17:40:32 +08:00
dtoUtcNow：2019/11/24 9:40:32 +00:00
dtoParse：2019/11/24 17:40:13 +08:00

DateTimeOffset.Parse的默认时区

DateTimeOffset.Parse的默认时区是当前时区。

1 2	Console.WriteLine("parse：{0}", DateTimeOffset.Parse("2019-6-14 15:38:49"));

参考

C# DateTime与时间戳转换：https://www.cnblogs.com/polk6/p/6024892.html
如何将Unix时间戳转换为DateTime，反之亦然？：https://stackoverflow.com/questions/249760/how-can-i-convert-a-unix-timestamp-to-datetime-and-vice-versa
DateTimeOffset源码：https://source.dot.net/#System.Private.CoreLib/DateTimeOffset.cs

8种主要排序算法的CSharp实现

发表于 2019-11-30 更新于 2025-08-04 分类于学习笔记，排序算法 Valine：

8种主要排序算法的C#实现

Excerpt
8种主要排序算法的实现及优化，包含选择排序，冒泡排序，插入排序，快速排序，归并排序，堆排序，希尔排序，基数排序。文末实际测试并比较。

新的一年到了，很多园友都辞职要去追求更好的工作环境，我也是其中一个，呵呵！

最近闲暇的时候我开始重温一些常用的算法。老早就买了《算法导论》，一直都没啃下去。

这本书确实很好，只是太难读了，总是读了几章就又读不下去了！工作上也几乎用不到。

我这段时间发现看这些排序算法比以前容易了很多，就借此机会将它们整理总结起来。

一是方便以后重温，二是可以应对笔试面试。同时也希望这篇博文可以帮助各位刚辞职和正在学习排序算法的园友。

PS：有可能实现的代码并不是最优的，如果有什么错误或者值得改进的地方，还请大家帮忙指出。

简介

排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。

平均时间复杂度从高到低依次是：

冒泡排序（o(n²)），选择排序（o(n²)），插入排序（o(n²)），堆排序（o(nlogn)），

归并排序（o(nlogn)），快速排序（o(nlogn)），希尔排序（o(n^1.25)），基数排序（o(n)）

这些平均时间复杂度是参照维基百科排序算法罗列的。

是计算的理论平均值，并不意味着你的代码实现能达到这样的程度。

例如希尔排序，时间复杂度是由选择的步长决定的。基数排序时间复杂度最小，

但我实现的基数排序的速度并不是最快的，后面的结果测试图可以看到。

本文代码实现使用的数据源类型为IList，这样可以兼容int[]和List(虽然int[]有ToList()，

List有ToArray()，哈哈！)。

选择排序

选择排序是我觉得最简单暴力的排序方式了。

以前刚接触排序算法的时候，感觉算法太多搞不清，唯独记得选择排序的做法及实现。

原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头）维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> SelectSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>int</span> min =<span> i;
</span><span> 6</span>                 <span>int</span> temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i + <span>1</span>; j &lt; data.Count; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &lt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         min =<span> j;
</span><span>12</span>                         temp =<span> data[j];
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (min !=<span> i)
</span><span>16</span> <span>                    Swap(data, min, i);
</span><span>17</span> <span>            }
</span><span>18</span>         }

过程解析：将剩余数组的最小数交换到开头。

冒泡排序

冒泡排序是笔试面试经常考的内容，虽然它是这些算法里排序速度最慢的（汗），后面有测试为证。

原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。

这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值

冒到最后。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 6</span> <span>                {
</span><span> 7</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span> 8</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span> 9</span> <span>                }
</span><span>10</span> <span>            }
</span><span>11</span>         }

过程解析：中需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。

很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1，这样会增加比较次数。

通过标识提升冒泡排序

在维基上看到，可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思，可以试试。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSortImprovedWithFlag(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 flag = <span>true</span><span>;
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>10</span> <span>                    {
</span><span>11</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span>12</span>                         flag = <span>false</span><span>;
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (flag) <span>break</span><span>;
</span><span>16</span> <span>            }
</span><span>17</span>         }

过程解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。

我起初也以为这个方法是应该有不错效果的，可是实际测试结果并不如想的那样。和未优化耗费时间一样（对于随机数列）。

由果推因，那么应该是冒泡排序对于随机数列，当剩余数列有序的时候，也没几个数要排列了！？

不过如果已经是有序数列或者部分有序的话，这个冒泡方法将会提升很大速度。

鸡尾酒排序（来回排序）

对冒泡排序进行更大的优化

冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。

原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleCocktailSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>int</span> m = <span>0</span>, n = <span>0</span><span>;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 flag = <span>true</span><span>;
</span><span> 8</span>                 <span>if</span> (i % <span>2</span> == <span>0</span><span>)
</span><span> 9</span> <span>                {
</span><span>10</span>                     <span>for</span> (<span>int</span> j = n; j &lt; data.Count - <span>1</span> - m; j++<span>)
</span><span>11</span> <span>                    {
</span><span>12</span>                         <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>13</span> <span>                        {
</span><span>14</span>                             Swap(data, j, j + <span>1</span><span>);
</span><span>15</span>                             flag = <span>false</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>19</span>                     m++<span>;
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span>                     <span>for</span> (<span>int</span> k = data.Count - <span>1</span> - m; k &gt; n; k--<span>)
</span><span>24</span> <span>                    {
</span><span>25</span>                         <span>if</span> (data[k] &lt; data[k - <span>1</span><span>])
</span><span>26</span> <span>                        {
</span><span>27</span>                             Swap(data, k, k - <span>1</span><span>);
</span><span>28</span>                             flag = <span>false</span><span>;
</span><span>29</span> <span>                        }
</span><span>30</span> <span>                    }
</span><span>31</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>32</span>                     n++<span>;
</span><span>33</span> <span>                }
</span><span>34</span> <span>            }
</span><span>35</span>         }

过程解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值

向左冒泡至开头。对于剩余数列，n为始，data.Count-1-m为末。

来回冒泡比单向冒泡：对于随机数列，更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。

插入排序

插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。

原理：通过构建有序数列，将未排序的数从后向前比较，找到合适位置并插入。维基入口

第一个数当作有序数列。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= <span>0</span>; j--<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         data[j + <span>1</span>] =<span> data[j];
</span><span>12</span>                         <span>if</span> (j == <span>0</span><span>)
</span><span>13</span> <span>                        {
</span><span>14</span>                             data[<span>0</span>] =<span> temp;
</span><span>15</span>                             <span>break</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>else</span>
<span>19</span> <span>                    {
</span><span>20</span>                         data[j + <span>1</span>] =<span> temp;
</span><span>21</span>                         <span>break</span><span>;
</span><span>22</span> <span>                    }
</span><span>23</span> <span>                }
</span><span>24</span> <span>            }
</span><span>25</span>         }

过程解析：将要排序的数（索引为i）存储起来，向前查找合适位置j+1，将i-1到j+1的元素依次向后

移动一位，空出j+1，然后将之前存储的值放在这个位置。

这个方法写的不如维基上的简洁清晰，由于合适位置是j+1所以多出了对j==0的判断，但实际效率影响无差别。

建议比照维基和我写的排序，自行选择。

二分查找法优化插入排序

插入排序主要工作是在有序的数列中对要排序的数查找合适的位置，而查找里面经典的二分查找法正可以适用。

原理：通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时，大于前一个数，小于后一个数。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSortImprovedWithBinarySearch(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>int</span><span> tempIndex;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 temp =<span> data[i];
</span><span> 8</span>                 tempIndex = BinarySearchForInsertSort(data, <span>0</span><span>, i, i);
</span><span> 9</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= tempIndex; j--<span>)
</span><span>10</span> <span>                {
</span><span>11</span>                     data[j + <span>1</span>] =<span> data[j];
</span><span>12</span> <span>                }
</span><span>13</span>                 data[tempIndex] =<span> temp;
</span><span>14</span> <span>            }
</span><span>15</span> <span>        }
</span><span>16</span> 
<span>17</span>         <span>public</span> <span>static</span> <span>int</span> BinarySearchForInsertSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span> high, <span>int</span><span> key)
</span><span>18</span> <span>        {
</span><span>19</span>             <span>if</span> (low &gt;= data.Count - <span>1</span><span>)
</span><span>20</span>                 <span>return</span> data.Count - <span>1</span><span>;
</span><span>21</span>             <span>if</span> (high &lt;= <span>0</span><span>)
</span><span>22</span>                 <span>return</span> <span>0</span><span>;
</span><span>23</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>24</span>             <span>if</span> (mid == key) <span>return</span><span> mid;
</span><span>25</span>             <span>if</span> (data[key] &gt;<span> data[mid])
</span><span>26</span> <span>            {
</span><span>27</span>                 <span>if</span> (data[key] &lt; data[mid + <span>1</span><span>])
</span><span>28</span>                     <span>return</span> mid + <span>1</span><span>;
</span><span>29</span>                 <span>return</span> BinarySearchForInsertSort(data, mid + <span>1</span><span>, high, key);
</span><span>30</span> <span>            }
</span><span>31</span>             <span>else  <span>// data[key] &lt;= data[mid]</span></span>
<span>32</span> <span>            {
</span><span>33</span>                 <span>if</span> (mid - <span>1</span> &lt; <span>0</span>) <span>return</span> <span>0</span><span>;
</span><span>34</span>                 <span>if</span> (data[key] &gt; data[mid - <span>1</span><span>])
</span><span>35</span>                     <span>return</span><span> mid;
</span><span>36</span>                 <span>return</span> BinarySearchForInsertSort(data, low, mid - <span>1</span><span>, key);
</span><span>37</span> <span>            }
</span><span>38</span>         }

过程解析：需要注意的是二分查找方法实现中high-low==1的时候mid==low，所以需要33行

mid-1<0即mid==0的判断，否则下行会索引越界。

快速排序

快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。

原理：从数列中挑选一个数作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。将要排序是数列递归地分割到

最小数列，每次都让分割出的数列符合“哨兵”的规则，自然就将数列变得有序。维基入口

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortStrict(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp =<span> data[low];
</span><span>10</span>             <span>int</span> i = low + <span>1</span>, j =<span> high;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[j] &gt; temp) j--<span>;
</span><span>14</span>                 <span>while</span> (data[i] &lt; temp &amp;&amp; i &lt; j) i++<span>;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span>                 i++; j--<span>;
</span><span>18</span> <span>            }
</span><span>19</span>             <span>if</span> (j !=<span> low)
</span><span>20</span> <span>                Swap(data, low, j);
</span><span>21</span>             QuickSortStrict(data, j + <span>1</span><span>, high);
</span><span>22</span>             QuickSortStrict(data, low, j - <span>1</span><span>);
</span><span>23</span>         }

过程解析：取的哨兵是数列的第一个值，然后从第二个和末尾同时查找，左侧要显示的是小于哨兵的值，

所以要找到不小于的i，右侧要显示的是大于哨兵的值，所以要找到不大于的j。将找到的i和j的数交换，

这样可以减少交换次数。i>=j时，数列全部查找了一遍，而不符合条件j必然是在小的那一边，而哨兵

是第一个数，位置本应是小于自己的数。所以将哨兵与j交换，使符合“哨兵”的规则。

这个版本的缺点在于如果是有序数列排序的话，递归次数会很可怕的。

另一个版本

这是维基上的一个C#版本，我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”

以及“哨兵”思想融入其中，代码简洁。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelax(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>14</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span> <span>            }
</span><span>18</span>             QuickSortRelax(data, j + <span>1</span><span>, high);
</span><span>19</span>             QuickSortRelax(data, low, i - <span>1</span><span>);
</span><span>20</span>         }

过程解析：取的哨兵是数列中间的数。将数列分成两波，左侧小于等于哨兵，右侧大于等于哨兵。

也就是说，哨兵不一定处于两波数的中间。虽然哨兵不在中间，但不妨碍“哨兵”的思想的实现。所以

这个实现也可以达到快速排序的效果。但却造成了每次递归完成，要排序的数列数总和没有减少（除非i==j）。

针对这个版本的缺点，我进行了优化

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelaxImproved(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>int</span> index = (low + high) / <span>2</span><span>;
</span><span>12</span>             <span>while</span> (<span>true</span><span>)
</span><span>13</span> <span>            {
</span><span>14</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>15</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>16</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>17</span> <span>                Swap(data, i, j);
</span><span>18</span>                 <span>if</span> (i == index) index =<span> j;
</span><span>19</span>                 <span>else</span> <span>if</span> (j == index) index =<span> i;
</span><span>20</span> <span>            }
</span><span>21</span>             <span>if</span> (j ==<span> i)
</span><span>22</span> <span>            {
</span><span>23</span>                 QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>24</span>                 QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>25</span> <span>            }
</span><span>26</span>             <span>else</span> <span>//</span><span>i-j==1</span>
<span>27</span> <span>            {
</span><span>28</span>                 <span>if</span> (index &gt;=<span> i)
</span><span>29</span> <span>                {
</span><span>30</span>                     <span>if</span> (index !=<span> i)
</span><span>31</span> <span>                        Swap(data, index, i);
</span><span>32</span>                     QuickSortRelaxImproved(data, i + <span>1</span><span>, high);
</span><span>33</span>                     QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else <span>//</span><span>index &lt; i</span></span>
<span>36</span> <span>                {
</span><span>37</span>                     <span>if</span> (index !=<span> j)
</span><span>38</span> <span>                        Swap(data, index, j);
</span><span>39</span>                     QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>40</span>                     QuickSortRelaxImproved(data, low, j - <span>1</span><span>);
</span><span>41</span> <span>                }
</span><span>42</span> <span>            }
</span><span>43</span>         }

过程解析：定义了一个变量Index，来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆，

那就与j交换，否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。

归并排序

归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式，我还一直以为是一种需要意会的思想呢。

不好意思了，孤陋寡闻了，哈哈！

原理：将两个有序的数列，通过比较，合并为一个有序数列。维基入口

为方便理解，此处实现用了List的一些方法，随后有IList版本。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>if</span> (low ==<span> high)
</span><span> 4</span>                 <span>return</span> <span>new</span> List&lt;<span>int</span>&gt;<span> { data[low] };
</span><span> 5</span>             List&lt;<span>int</span>&gt; mergeData = <span>new</span> List&lt;<span>int</span>&gt;<span>();
</span><span> 6</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span> 7</span>             List&lt;<span>int</span>&gt; leftData =<span> MergeSortOnlyList(data, low, mid);
</span><span> 8</span>             List&lt;<span>int</span>&gt; rightData = MergeSortOnlyList(data, mid + <span>1</span><span>, high);
</span><span> 9</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>10</span>             <span>while</span> (<span>true</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>13</span> <span>                {
</span><span>14</span> <span>                    mergeData.Add(leftData[i]);
</span><span>15</span>                     <span>if</span> (++i ==<span> leftData.Count)
</span><span>16</span> <span>                    {
</span><span>17</span>                         mergeData.AddRange(rightData.GetRange(j, rightData.Count -<span> j));
</span><span>18</span>                         <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span> <span>                    mergeData.Add(rightData[j]);
</span><span>24</span>                     <span>if</span> (++j ==<span> rightData.Count)
</span><span>25</span> <span>                    {
</span><span>26</span>                         mergeData.AddRange(leftData.GetRange(i, leftData.Count -<span> i));
</span><span>27</span>                         <span>break</span><span>;
</span><span>28</span> <span>                    }
</span><span>29</span> <span>                }
</span><span>30</span> <span>            }
</span><span>31</span>             <span>return</span><span> mergeData;
</span><span>32</span> <span>        }
</span><span>33</span> 
<span>34</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt;<span> data)
</span><span>35</span> <span>        {
</span><span>36</span>             data = MergeSortOnlyList(data, <span>0</span>, data.Count - <span>1</span><span>);  <span>//不会改变外部引用 参照<a href="http://www.cnblogs.com/fatbird/p/parametersInCsharp.html" target="_blank">C#参数传递
</a></span></span><span>37</span>             <span>return</span><span> data;
</span><span>38</span>         }

过程解析：将数列分为两部分，分别得到两部分数列的有序版本，然后逐个比较，将比较出的小数逐个放进

新的空数列中。当一个数列放完后，将另一个数列剩余数全部放进去。

IList版本

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             data = MergeSort(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span>             <span>return</span><span> data;
</span><span> 5</span> <span>        }
</span><span> 6</span> 
<span> 7</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 8</span> <span>        {
</span><span> 9</span>             <span>int</span> length = high - low + <span>1</span><span>;
</span><span>10</span>             IList&lt;<span>int</span>&gt; mergeData =<span> NewInstance(data, length);
</span><span>11</span>             <span>if</span> (low ==<span> high)
</span><span>12</span> <span>            {
</span><span>13</span>                 mergeData[<span>0</span>] =<span> data[low];
</span><span>14</span>                 <span>return</span><span> mergeData;
</span><span>15</span> <span>            }
</span><span>16</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>17</span>             IList&lt;<span>int</span>&gt; leftData =<span> MergeSort(data, low, mid);
</span><span>18</span>             IList&lt;<span>int</span>&gt; rightData = MergeSort(data, mid + <span>1</span><span>, high);
</span><span>19</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>20</span>             <span>while</span> (<span>true</span><span>)
</span><span>21</span> <span>            {
</span><span>22</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>23</span> <span>                {
</span><span>24</span>                     mergeData[i + j] = leftData[i++]; <span>//</span><span>不能使用Add,Array Length不可变</span>
<span>25</span>                     <span>if</span> (i ==<span> leftData.Count)
</span><span>26</span> <span>                    {
</span><span>27</span>                         <span>int</span> rightLeft = rightData.Count -<span> j;
</span><span>28</span>                         <span>for</span> (<span>int</span> m = <span>0</span>; m &lt; rightLeft; m++<span>)
</span><span>29</span> <span>                        {
</span><span>30</span>                             mergeData[i + j] = rightData[j++<span>];
</span><span>31</span> <span>                        }
</span><span>32</span>                         <span>break</span><span>;
</span><span>33</span> <span>                    }
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else</span>
<span>36</span> <span>                {
</span><span>37</span>                     mergeData[i + j] = rightData[j++<span>];
</span><span>38</span>                     <span>if</span> (j ==<span> rightData.Count)
</span><span>39</span> <span>                    {
</span><span>40</span>                         <span>int</span> leftleft = leftData.Count -<span> i;
</span><span>41</span>                         <span>for</span> (<span>int</span> n = <span>0</span>; n &lt; leftleft; n++<span>)
</span><span>42</span> <span>                        {
</span><span>43</span>                             mergeData[i + j] = leftData[i++<span>];
</span><span>44</span> <span>                        }
</span><span>45</span>                         <span>break</span><span>;
</span><span>46</span> <span>                    }
</span><span>47</span> <span>                }
</span><span>48</span> <span>            }
</span><span>49</span>             <span>return</span><span> mergeData;
</span><span>50</span> 
<span>51</span>         }

过程原理与上个一样，此处就不赘述了。

堆排序

堆排序是根据堆这种数据结构设计的一种算法。堆的特性：父节点的值总是小于（或大于）它的子节点。近似二叉树。

原理：将数列构建为最大堆数列（即父节点总是最大值），将最大值（即根节点）交换到数列末尾。这样要排序的数列数总和减少，

同时根节点不再是最大值，调整最大堆数列。如此重复，最后得到有序数列。维基入口有趣的演示

实现准备：如何将数列构造为堆——父节点i的左子节点为2i+1，右子节点为2i+2。节点i的父节点为floor((i-1)/2)。

实现如下（这个实现判断和临时变量使用太多，导致效率低，评论中@小城故事提出了更好的实现）：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> HeapSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span> <span>            BuildMaxHeapify(data);
</span><span> 4</span>             <span>int</span> j =<span> data.Count;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt;<span> j; )
</span><span> 6</span> <span>            {
</span><span> 7</span>                 Swap(data, i, --<span>j);
</span><span> 8</span>                 <span>if</span> (j - <span>2</span> &lt; <span>0</span><span>)  <span>//只剩下1个数 j代表余下要排列的数的个数
</span></span><span> 9</span>                     <span>break</span><span>;
</span><span>10</span>                 <span>int</span> k = <span>0</span><span>;
</span><span>11</span>                 <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>                {
</span><span>13</span>                     <span>if</span> (k &gt; (j - <span>2</span>) / <span>2</span>) <span>break</span><span>;  <span>//即：k &gt; ((j-1)-1)/2</span> <span>超出最后一个父节点的位置  
</span></span><span>14</span>                     <span>else</span>
<span>15</span> <span>                    {
</span><span>16</span>                         <span>int</span> temp =<span> k;
</span><span>17</span>                         k = ReSortMaxBranch(data, k, <span>2</span> * k + <span>1</span>, <span>2</span> * k + <span>2</span>, j - <span>1</span><span>);
</span><span>18</span>                         <span>if</span> (temp == k) <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span> <span>            }
</span><span>22</span> <span>        }
</span><span>23</span> 
<span>24</span>         <span>public</span> <span>static</span> <span>void</span> BuildMaxHeapify(IList&lt;<span>int</span>&gt;<span> data)
</span><span>25</span> <span>        {
</span><span>26</span>             <span>for</span> (<span>int</span> i = data.Count / <span>2</span> - <span>1</span>; i &gt;= <span>0</span>; i--<span>)  <span>//(data.Count-1)-1)/2为数列最大父节点索引
</span></span><span>27</span> <span>            {
</span><span>28</span>                 <span>int</span> temp =<span> i;
</span><span>29</span>                 temp = ReSortMaxBranch(data, i, <span>2</span> * i + <span>1</span>, <span>2</span> * i + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>30</span>                 <span>if</span> (temp !=<span> i)
</span><span>31</span> <span>                {
</span><span>32</span>                     <span>int</span> k =<span> i;
</span><span>33</span>                     <span>while</span> (k != temp &amp;&amp; temp &lt;= data.Count / <span>2</span> - <span>1</span><span>)
</span><span>34</span> <span>                    {
</span><span>35</span>                         k =<span> temp;
</span><span>36</span>                         temp = ReSortMaxBranch(data, temp, <span>2</span> * temp + <span>1</span>, <span>2</span> * temp + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>37</span> <span>                    }
</span><span>38</span> <span>                }
</span><span>39</span> <span>            }
</span><span>40</span> <span>        }
</span><span>41</span> 
<span>42</span>         <span>public</span> <span>static</span> <span>int</span> ReSortMaxBranch(IList&lt;<span>int</span>&gt; data, <span>int</span> maxIndex, <span>int</span> left, <span>int</span> right, <span>int</span><span> lastIndex)
</span><span>43</span> <span>        {
</span><span>44</span>             <span>int</span><span> temp;
</span><span>45</span>             <span>if</span> (right &gt;<span> lastIndex)  <span>//父节点只有一个子节点
</span></span><span>46</span>                 temp =<span> left;
</span><span>47</span>             <span>else</span>
<span>48</span> <span>            {
</span><span>49</span>                 <span>if</span> (data[left] &gt;<span> data[right])
</span><span>50</span>                     temp =<span> left;
</span><span>51</span>                 <span>else</span> temp =<span> right;
</span><span>52</span> <span>            }
</span><span>53</span> 
<span>54</span>             <span>if</span> (data[maxIndex] &lt;<span> data[temp])
</span><span>55</span> <span>                Swap(data, maxIndex, temp);
</span><span>56</span>             <span>else</span> temp =<span> maxIndex;
</span><span>57</span>             <span>return</span><span> temp;
</span><span>58</span>         }

过程解析：BuildMaxHeapify为排序前构建的最大堆数列方法，主要内容为从最后一个父节点开始往前将每个三角组合

（即父节点与它的两个子节点）符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大，

并返回该值之前的索引，用来判断是否进行了交换，以及原来的父节点值交换到了什么位置。在HeapSort里首先

构建了最大堆数列，然后将根节点交换到末尾，根节点不是最大值了，在while语句中对最大堆数列进行调整。

插曲：自从看了Martin Fowler大师《重构》第三版，我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切，

即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊！？上面的代码注释都是写博客的时候现加的（源代码很干净的。汗!）。

希尔排序

希尔排序是插入排序的一种更高效的改进版本。

在前面介绍的插入排序，我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。

希尔排序正是利用第一点，改善第二点，达到更理想的效果。

原理：通过奇妙的步长，插入排序间隔步长的元素，随后逐渐缩短步长至1，实现数列的插入排序。维基入口

疑问：可以想象到排序间隔步长的数，会逐渐让数列变得有序，提升最后步长为1时标准插入排序的效率。在维基上看到这么

一句话“可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是

这是个正确的命题吗？如何证明呢？看维基上也是由果推因，说是如果不是这样，就不会排序那么快了。可这我感觉还是太牵强了，

哪位大哥发现相关资料，希望能分享出来，不胜感激。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; i +=<span> gap)
</span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

过程解析：采用的步长是N/2，每次取半，直至1。循环内部就是标准的插入排序。

——————

修正：修正后希尔排序才是真正牛叉的希尔啊！感谢@390218462的提出

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSortCorrect(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; <span>i++</span><span>)      // <span>i+ = gap 改为了 i++
</span></span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

——————

这里实现的貌似是最差的希尔排序。主要源于步长的选择。维基上有各种牛叉的“凌波微步”，极限在哪里，

喜欢挑战的同学可以去学习学习。看维基排序算法里六种排序的测试，希尔最快，比快速排序还快！！我没实现啊！

只是对于神奇的步长更充满了敬畏。

基数排序

基数排序是一种非比较型整数排序。

“非比较型”是什么意思呢？因为它内部使用的是桶排序，而桶排序是非比较型排序。

这里就要说说桶排序了。一个非常有意思的排序。

桶排序

原理：取一定数量（数列中的最大值）的编好序号的桶，将数列每个数放进编号为它的桶里，然后将不是空的桶依次倒出来，

就组成有序数列了。维基入口

好吧！聪明的人一眼就看出桶排序的破绽了。假设只有两个数1,10000，岂不是要一万个桶！？这确实是个问题啊！我也

没想出解决办法。我起初也以为桶排序就是一个通过牺牲空间来换取时间的排序算法，它不需要比较，所以是非比较型算法。

但看了有趣的演示的桶排序后，发现世界之大，你没有解决，不代表别人没解决，睿智的人总是很多。

1，9999的桶排序实现：new Int[2];总共有两个数，得出最大数9999的位数4，取10的4次幂即10000作为分母，

要排序的数（1或9999）作为分子，并乘以数列总数2，即1*2/10000,9999*2/10000得到各自的位置0,1，完成排序。

如果是1,10000进行排序的话，上面的做法就需要稍微加一些处理——发现最大数是10的n次幂，就将它作为分母，并

放在数列末尾就好了。

如果是9999,10000进行排序的话，那就需要二维数组了，两个都在位置1，位置0没数。这个时候就需要在放

入每个位置时采用其它排序（比如插入排序）办法对这个位置的多个数排序了。

为基数排序做个过渡，我这里实现了一个个位数桶排序

涉及到了当重复的数出现的处理。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BucketSortOnlyUnitDigit(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 indexCounter[data[i]]++<span>;
</span><span> 7</span> <span>            }
</span><span> 8</span>             <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 9</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; <span>10</span>; i++<span>)
</span><span>10</span> <span>            {
</span><span>11</span>                 indexBegin[i] = indexBegin[i-1]+<span> indexCounter[i-1];
</span><span>15</span> <span>            }
</span><span>16</span>             IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>17</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span>18</span> <span>            {
</span><span>19</span>                 <span>int</span> number =<span> data[i];
</span><span>20</span>                 tempList[indexBegin[number]++] =<span> data[i];
</span><span>21</span> <span>            }
</span><span>22</span>             data =<span> tempList;
</span><span>23</span>         }

过程解析：indexCounter进行对每个数出现的频率的统计。indexBegin存储每个数的起始索引。

比如 1 1 2，indexCounter统计到0个0,2个1,1个2。indexBegin计算出0,1,2的起始索引分别为

0,0,2。当1个1已取出排序，那索引将+1,变为0,1,2。这样就通过提前给重复的数空出位置，解决了

重复的数出现的问题。当然，你也可以考虑用二维数组来解决重复。

下面继续基数排序。

基数排序原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。

取得最大数的位数，从低位开始，每个位上进行桶排序。

实现如下：

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; RadixSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span> max = data[<span>0</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>if</span> (data[i] &gt;<span> max)
</span><span> 7</span>                     max =<span> data[i];
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>int</span> digit = <span>1</span><span>;
</span><span>10</span>             <span>while</span> (max / <span>10</span> != <span>0</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 digit++<span>;
</span><span>13</span>                 max /= <span>10</span><span>;
</span><span>14</span> <span>            }
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; digit; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>18</span>                 IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>19</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; data.Count; j++<span>)
</span><span>20</span> <span>                {
</span><span>21</span>                     <span>int</span> number = (data[j] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span>, i));  <span>//</span><span>得出i+1位上的数</span>
<span>22</span>                     indexCounter[number]++<span>;
</span><span>23</span> <span>                }
</span><span>24</span>                 <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>25</span>                 <span>for</span> (<span>int</span> k = <span>1</span>; k &lt; <span>10</span>; k++<span>)
</span><span>26</span> <span>                {
</span><span>27</span>                     indexBegin[k] = indexBegin[k - <span>1</span>] + indexCounter[k - <span>1</span><span>];
</span><span>28</span> <span>                }
</span><span>29</span>                 <span>for</span> (<span>int</span> k = <span>0</span>; k &lt; data.Count; k++<span>)
</span><span>30</span> <span>                {
</span><span>31</span>                     <span>int</span> number = (data[k] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span><span>, i));
</span><span>32</span>                     tempList[indexBegin[number]++] =<span> data[k];
</span><span>33</span> <span>                }
</span><span>34</span>                 data =<span> tempList;
</span><span>35</span> <span>            }
</span><span>36</span>             <span>return</span><span> data;
</span><span>37</span>         }

过程解析：得出最大数的位数，从低位开始桶排序。我写的这个实现代码并不简洁，但逻辑更清晰。

后面测试的时候我们就会发现，按理来说这个实现也还行吧！但并不如想象的那么快！

循环的次数太多？（统计频率n次+9次计算+n次放到新的数组）*位数。

创建的新实例太多？(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数

测试比较

添加随机数组，数组有序校验，微软Linq排序

代码如下：

<span> 1</span>         <span>public</span> <span>static</span> <span>int</span>[] RandomSet(<span>int</span> length, <span>int</span><span> max)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] result = <span>new</span> <span>int</span><span>[length];
</span><span> 4</span>             Random rand = <span>new</span><span> Random();
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; result.Length; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 result[i] =<span> rand.Next(max);
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>return</span><span> result;
</span><span>10</span> <span>        }
</span><span>11</span> 
<span>12</span>         <span>public</span> <span>static</span> <span>bool</span> IsAscOrdered(IList&lt;<span>int</span>&gt;<span> data)
</span><span>13</span> <span>        {
</span><span>14</span>             <span>bool</span> flag = <span>true</span><span>;
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>if</span> (data[i] &gt; data[i + <span>1</span><span>])
</span><span>18</span>                     flag = <span>false</span><span>;
</span><span>19</span> <span>            }
</span><span>20</span>             <span>return</span><span> flag;
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> TestMicrosoft(IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             List&lt;<span>int</span>&gt; result = data.OrderBy(a =&gt;<span> a).ToList();
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName = <span>"</span><span>TestMicrosoft</span><span>"</span><span>;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> 
<span>38</span>         }

测试主体如下：

<span> 1</span>         <span>static</span> <span>void</span> Main(<span>string</span><span>[] args)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] aa = RandomSet(<span>50000</span>, <span>99999</span><span>);
</span><span> 4</span>             <span>//</span><span>int[] aa = OrderedSet(5000);</span>
<span> 5</span>             Console.WriteLine(<span>"</span><span>Array Length:</span><span>"</span> +<span> aa.Length);
</span><span> 6</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)SelectSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 7</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 8</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSortImprovedWithFlag, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 9</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleCocktailSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>10</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>11</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSortImprovedWithBinarySearch, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>12</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortStrict, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>13</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelax, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>14</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelaxImproved, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>15</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)MergeSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>16</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)ShellSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>17</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)RadixSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>18</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)HeapSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>19</span>             TestMicrosoft(aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>20</span> <span>            Console.Read();
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             IList&lt;<span>int</span>&gt; result =<span> method(data);
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> <span>        }
</span><span>38</span> 
<span>39</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Action&lt;IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>40</span> <span>        {
</span><span>41</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>42</span> <span>            stopwatch.Start();
</span><span>43</span> <span>            method(data);
</span><span>44</span> <span>            stopwatch.Stop();
</span><span>45</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>46</span>             <span>int</span> length =<span> methodName.Length;
</span><span>47</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>48</span> <span>            {
</span><span>49</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>50</span> <span>            }
</span><span>51</span>             Console.WriteLine(methodName +
<span>52</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(data) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>53</span>         }

剩余代码折叠在此处

View Code

测试设备：win8(64位)，i7-3630QM,8G内存，vs2012

测试结果：

100000,50000,10000,5000,1000,100依次是：

结果分析：可以看出在大数组的时候，微软自带排序更接近快速排序。而当数组变小时，速度却没有明显提升，甚至变得更慢，

比如1000和100。可以推断出在数组足够小的时候，比较已经不是影响这个方法主要因素。而根据它对大数组的表现。我们可以

推断出它应该用的是快速排序。反编译验证下：

在System.Linq.EnumerableSorter下。有兴趣的同学可以去看下详细实现。

维基上也有个测试。硬件没我的好。时间是我测试结果时间的几百倍。有兴趣的同学可以比较下。

在上面的测试中，我们可以看到快速最快，归并其次，冒泡最慢（维基上是希尔最快，估计使用的是某种神奇的步长）。

在我这里，以前实现的希尔还不如二分查找优化版的快，修正后希尔快了相当多，上面测试的希尔排序是以前错误的实现。

修正后的实现测试效果请点击右侧导航到希尔排序查看。希尔排序是一种神奇又有潜力的算法。步长不好会很挫！

而基数排序却是比平均时间复杂度为o(nlogn)的堆排序，归并排序，快速排序还要慢的，虽然它的平均时间复杂度为o(n)。

冒泡标识优化版对随机数列结果优化不明显，鸡尾酒版优化可以看到，但也不是很厉害。

插入排序二分查找优化版优化比较明显。我优化的快速排序QuickSortRelaxImproved优化也不明显。

以上是随机数列的测试结果，最大值为99999。

而对于有序数列，这些方法表现又会如何呢？

我这里就不演示了。本文末尾会附上demo，大家可以自行测试。

有意思的是:

我在测试有序数列的时候，QuickSortStrict方法栈溢出了（stack overflow exception）。这个异常

是让我去stackoverflow搜寻答案吗？哈哈！我确信我的方法不是无限循环。跳过一堆链接。。。我是

在测试10000个数排序的时候发生的错误。我跟踪后发现大约在9400多次递归的时候，栈溢出。找啊找

终于找见了一个类似的问题。上面说如果一个递归9000多次而没有返回值，也会报栈溢出的。而这个方法

对于10000个有序数列，确实每次减少一个数地递归，次数会超过限制。

我的算法理论不怎么好，对于时间复杂度和空间复杂度，还有稳定度，搞得也不怎么清楚，只知道个大致的

意思。各位要笔试面试的朋友可以去维基百科这个表来了解学习。

总结

我觉得使用IList更贴近数列，更能展现基本的操作。所以我的实现中都没有将它强制转化为List

或者int[]来调用微软封装的方法。这样说来，题目说C#实现倒快有点名不副实了。不过这样却也方便了其它语言

朋友。比如将我这篇博文里的实现随便改改，就可以说是另一个语言版本的8种排序算法了。哈哈！在这里，

我想说下这次学习排序对我的意义：老久不怎么动脑了，突然动起来，磨磨唧唧地得出结果，最后倒也有点成就感！

在学习过程中，经常会脑子转不过弯，想不通的，只是走在路上或者睡觉前突然灵感一现，有点小惊喜的感觉！

这大概就是进步的特征吧！哈哈！这次写demo+写博客花费了不少时间，倒也收获颇多，尤其在我将8种

排序都实现之前，没进行过一次测试，全部实现完成后，测试时各种索引越界+无限循环+各种问题，没几个

能跑通的，到后来的几乎都没有问题，也算是锻炼了思维，找出错原因的能力。本篇是自我学习的一个总结，

要学习及锻炼的园友，还望一定自己实现一下，可以和我的比较一下，解除疑惑或者提出改进。

Demo源码

PS:我打算三月份去广州发展，主要会Asp.net mvc+jquery（不介意学习新的技术[除了webform]及语言[除了java]）。

CSharp排序算法小结

发表于 2019-11-30 更新于 2025-07-11 分类于学习笔记，排序算法 Valine：

前言

算法这个东西其实在开发中很少用到，特别是web开发中，但是算法也很重要，因为任何的程序，任何的软件，都是由很多的算法和数据结构组成的。但是这不意味着算法对于每个软件设计人员的实际工作都是很重要的。每个项目特点和需求特殊也导致算法运用场景上不同。但是个人觉得算法运用的好的话会给自己在程序设计的时候提供比较好的思路。下面就对一些排序算法小结一下，就当做自己的一个笔记吧。

插入排序

1.简介

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2.算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

3.使用插入排序为一列数字进行排序的过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

    /// <summary>
    /// 插入排序 /// </summary>
    public class InsertionSorter
    { public void Sort(int\[\] list)
        { for (int i = 1; i < list.Length; ++i)
            { int t = list\[i\]; int j = i; while ((j > 0) && (list\[j - 1\] > t))
                {
                    list\[j\] \= list\[j - 1\]; \--j;
                }
                list\[j\] \= t;
            }

        }
    }

数组

int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

希尔排序

1.简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

2.算法实现

原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1] 对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

3.排序过程

最差时间复杂度根据步长串行的不同而不同。 $O(n\log^2 n)$

最优时间复杂度 O(n)

平均时间复杂度根据步长串行的不同而不同。

4.C#实现

    /// <summary>
    /// 希尔排序 /// </summary>
    public class ShellSorter
    { public void Sort(int\[\] list)
        { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 \* inc + 1) ; for (; inc > 0; inc /= 3)
            { for (int i = inc + 1; i <= list.Length; i += inc)
                { int t = list\[i - 1\]; int j = i; while ((j > inc) && (list\[j - inc - 1\] > t))
                    {
                        list\[j \- 1\] = list\[j - inc - 1\];
                        j \-= inc;
                    }
                    list\[j \- 1\] = t;
                }
            }
        }
    }

选择排序

1.简介

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

2.实现过程

最差时间复杂度 О(n²)

最优时间复杂度 О(n²)

平均时间复杂度 О(n²)

3.C#实现

    /// <summary>
    /// 选择排序 /// </summary>
    public class SelectionSorter
    { // public enum comp {COMP\_LESS,COMP\_EQUAL,COMP\_GRTR};
        private int min; // private int m=0;
        public void Sort(int\[\] list)
        { for (int i = 0; i < list.Length - 1; ++i)
            {
                min \= i; for (int j = i + 1; j < list.Length; ++j)
                { if (list\[j\] < list\[min\])
                        min \= j;
                } int t = list\[min\];
                list\[min\] \= list\[i\];
                list\[i\] \= t; // Console.WriteLine("{0}",list\[i\]);

}

        }
    }

冒泡排序

1.简介

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n^{2})），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。

2.算法实现
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.实现过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

   /// <summary>
    /// 冒泡排序 /// </summary>
    public class bubblesort
    { public void BubbleSort(int\[\] R)
        { int i, j, temp; //交换标志 
            bool exchange; for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序

{
exchange = false; //本趟排序开始前，交换标志应为假
for (j = R.Length - 2; j >= i; j–)
{ if (R[j + 1] < R[j])　//交换条件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //发生了交换，故将交换标志置为真
}
} if (!exchange) //本趟排序未发生交换，提前终止算法
{ break;
}
}
}
}

设计模式系列导航

发表于 2019-11-30 更新于 2025-08-04 分类于学习笔记，设计模式 Valine：

面向对象的设计原则

什么是时间戳

Unix时间戳相互转换

C# DateTime转换为Unix时间戳

.NET 4.6新方法

通用的老方法

Unix时间戳转换为C# DateTime

.NET 4.6新方法

通用的老方法

备注

DateTimeOffset使用Now还是UtcNow

DateTime转换为DateTimeOffset

DateTime的时区信息(Kind属性)

测试代码

DateTimeOffset.Parse的默认时区

参考

8种主要排序算法的C#实现

Excerpt

简介

选择排序

冒泡排序

通过标识提升冒泡排序

鸡尾酒排序（来回排序）

对冒泡排序进行更大的优化

插入排序

二分查找法优化插入排序

快速排序

另一个版本

针对这个版本的缺点，我进行了优化

归并排序

IList版本

堆排序

希尔排序

基数排序

桶排序

为基数排序做个过渡，我这里实现了一个个位数桶排序

测试比较

总结

主要参考：维基百科，有趣的演示

创建型

结构型

行为型