• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号
登陆 注册
描述文字

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
作者：胖鸟低飞

简介

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

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

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

     归并排序（o(nlogn)），快速排序（o(nlogn)）， 希尔排序（o(n1.25)），基数排序（o(n)）

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

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

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

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

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

List<int>有ToArray()，哈哈！)。

选择排序

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

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

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

实现如下：

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

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

冒泡排序

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

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

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

冒到最后。  维基入口

实现如下：

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

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

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

通过标识提升冒泡排序

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

实现如下：

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

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

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

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

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

鸡尾酒排序（来回排序）

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

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

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

实现如下：

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

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

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

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

插入排序

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

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

第一个数当作有序数列。

实现如下：

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

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

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

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

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

二分查找法优化插入排序

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

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

实现如下：

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

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

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

快速排序

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

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

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

实现如下：

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

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

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

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

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

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

另一个版本

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

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

实现如下：

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

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

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

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

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

实现如下：

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

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

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

归并排序

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

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

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

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

实现如下：

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

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

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

IList<int>版本

实现如下：

 1         public static IList<int> MergeSort(IList<int> data)
 2         {
 3             data = MergeSort(data, 0, data.Count - 1);
 4             return data;
 5         }
 6 
 7         public static IList<int> MergeSort(IList<int> data, int low, int high)
 8         {
 9             int length = high - low + 1;
10             IList<int> mergeData = NewInstance(data, length);
11             if

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
用C++对C++语法格式进行分析发布时间：2022-07-13
下一篇：
C语言程序设计第四次作业——选择结构（2）发布时间：2022-07-13
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap