C#排序算法 - 董川民

排序也称排序算法（Sort Algorithm）,排序是将一组数据，依制定顺序进行排列的过程。

排序分类：

（1）内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。

（2）外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。.

（3）常见排序算法分类（见下图）

C#排序算法

算法的时间复杂度

度量一个程序（算法）时间的两种方法

（1）事后统计的方法

这种方法可行，但是有两个问题：意识想要对设计的算法的运行性能进行评测，需要实际运行该程序；而是所得时间的统计量以来计算机的硬件、软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

（2）事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优。

时间频度

一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，他花费时间就多。一个算法中的语句执行次数成为语句频度。记为T（n）。

举例说明-基本案例

比如计算1-100所有数字之和，我们设计两种算法

int total = 0;
int end = 100;
//使用for循环计算 T(n) = n + 1;
for (int i = 0; i < end; i++)
{
   total += i;
}

//直接计算 T(n) = 1;
total = (1 + end) * end / 2;

举例说明-忽略常数项

C#排序算法

结论：

（1）2n+20和2n随着n变大，执行曲线无限接近，20可以忽略

（2）3n+10和3n随着n变大，执行曲线无限接近，10可以忽略

举例说明-忽略低次项

C#排序算法

结论：

（1）2n^2+3n+10和2n^2随着n变大，执行曲线无限接近，可以忽略3n+10

（2）n^2+5n+20和n^2随着n变大，执行曲线无限接近，可以忽略5n+20

举例说明-忽略系数

C#排序算法

结论：

（1）随着n值变大，5n^2+7n和3n^2+2n，执行曲线重合，说明这种情况下，5和3可以忽略。

（2）而n^3+5n和6n^3+4n，执行曲线分离，说明多少次方是关键。

时间复杂度

（1）一般情况下，算法中基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于0的常数，则成f(n)时T(n)的同数量级函数。记作T（n）=O(f(n))，成O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。

（2）T(n)不同，但时间复杂度可能相同。如：T(n)=n²+7n+6与T(n)=3n²+2n+2它们的T(n)不同，但时间复杂度相同，都为O(n²)。

（3）计算时间复杂度的方法：

常数1代替运行时间中的所有加法常数 T(n)=n²+7n+6与T(n)=3n²+2n+2
修改的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1=>T(n)=n²
去除最高阶的系数T(n)=n²=>T(n)=n²=>O(n²)

常见时间复杂度

（1）常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就是O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i+j;

上述代码在执行的时候，它小号的时候并不随着某个变量的增长而增长，那么无论这类代码有多少，即使有几万几十万行，可以用O(1)来表示它的时间复杂度。

（2）对数阶O(log2n)

int i = 1;
while(i<n)
{
   i = i*2;
}

说明：在while循环里面，每次都讲i乘以2，乘完之后，i距离n就越来越近了。假设循环x次之后，i就大于2，此时这个循环就推出了，也就是说2的次方等于n，那么x=O(log2n)。x=O(log2n)的这个2时间上是根据代码变化，i=i*3,则是x=O(log3n)。

C#排序算法

如果N＝a的x方（a＞0，a≠1），即a的x次方等于N（a＞0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作x＝log，N。其中，a叫做对数的底数，N叫做真数，x叫做以a为底N的对数”。

（3）线性阶O(n)

for(i=1;1<=n;++i)
{
  j=i;
  j++;
}

说明：这段代码，for循环里面的代码会执行n遍，因此它小号的时间是随着n的变化而变化的，因此这类代码可以用O(n)来表示它的时间复杂度。

（4）线性对数阶O(nlogN)

for(m=1;m<n;m++)
{
  j=1;
  while(i<n)
  {
     i = i*2;
  }
}

说明：线性对数阶O(nlogN)其实非常容易理解，将时间复杂度为O(nlogN)的代码循环N遍的话，那么它的时间复杂度就是n*O(nlogN)，也就是O(nlogN)

（5）平方阶O(n^2)

for(x=1;i<n;x++)
{
  for(i=1;i<=n;i++)
  {
    j=i;
    j++;
  }
}

说明：平方阶O（n）就更容易理解了，如果把O（n）的代码再嵌套循环一遍，它的时间复杂度就是O（n），这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O（n＊n），即O（n）如果将其中一层循环的n改成m，那它的时间复杂度就变成了O（m＊n）

（6）立方阶O(n^3)

说明：参考上面的O（n）去理解就好了，O（n）相当于三层n循环，其它的类似。

（7）k次方阶O(n^k)

（8）指数阶O(2^n)

C#排序算法

说明：

常见算法时间复杂度由小到大依次为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
从图中可见，我们应该尽可能避免使用指数阶的算法。

平均时间复杂度和最坏时间复杂度

1）平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该具法的运行时间。

2)最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最环情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

3)平均时间复杂度和最坏时间复杂度是否一致，和算法有关（如图：）。

基本介绍

（1）类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity）定义为该算法所耗费的存储空间，它也是问题规模n的函数。

（2）空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用的存储单元，例如快速排序和归并排序算法就属于这种情况。

（3）在做算法分析师，主要讨论是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品（redis，memcache）和算法（技术排序）本质就是用空间换时间。

C#排序算法

基本介绍

（1）类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity）定义为该算法所耗费的存储空间，它也是问题规模n的函数。