C#.NET 中的排序算法代码
4.67/5 (45投票s)
本文包含快速排序、归并排序、冒泡排序、堆排序的代码
引言
我将一些排序算法放在一个文件中，初学者可以在其中找到不同排序技术的工作原理。
背景
当我需要实现这些排序算法时，我发现很难在一个地方找到所有技术。这就是我发布这个小应用程序的原因，它将帮助学生和初学者。
Using the Code
只需解压 zip 文件并在 Visual Studio 中打开它。运行项目。未排序的列表是预定义的，您可以自行更改它，也可以使其更具交互性。
快速排序
快速排序采用分而治之的工作方式。它将未排序的列表分成子列表，然后对各个列表进行排序。
快速排序的步骤是
- 从列表中选择一个元素，称为“枢轴”（Pivot）。
- 重新排列列表，使所有值小于枢轴的元素都位于枢轴之前，而所有值大于枢轴的元素都位于枢轴之后（相等的值可以放在任意一边）。分区后，枢轴位于其最终位置。这称为分区操作。
- 递归地对较小元素的子列表和较大元素的子列表进行排序。
在代码中，我们有一个类型为“整数列表”的 unsorted 列表，它将使用不同的算法进行排序。
我们通过启动 C# 新项目，选择 WindowsForm 类型并在您的 PC 硬盘上的某个位置创建它来开始编码。
或者，如果您正在使用上面提供的项目文件，只需下载它并将其解压到硬盘上的某个位置。然后打开 Visual Studio，打开项目，浏览到您解压下载文件的位置并打开项目文件。
查看源代码。在这里您将找到默认的 using 指令。在这个项目中，我没有包含任何其他命名空间。
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
我们通过启动名为 quicksort 的新命名空间来开始编写代码。
namespace quicksort
{
public partial class Form1 : Form{public Form1()
{
InitializeComponent();
}
}
在这里，我们将定义未排序的列表，它将用于我们所有的排序算法。
List<int> unsorted = new List<int> { 9, 8, 7, 6 };
在我们的 button1_Click 事件中，我们调用 quicksort 函数，该函数然后将排序后的列表返回到 result 列表中。然后 showsort 函数将显示排序后的列表。
private void button1_Click(object sender, EventArgs e)
{
List<int> result = new List<int>(quicksort(unsorted));
showsort(result);
}
List<int> unsorted = new List<int> { 9, 8, 7, 6 };
quicksort 函数通过从未排序列表中选择一个随机值开始工作，此值称为枢轴值。然后我们从未排序列表中删除枢轴值。现在，未排序列表中的每个元素 x 都与此 pivot 进行比较。我们还有另外两个列表 less 和 greater。如果任何元素小于枢轴，则将其放入 less 列表中；如果大于枢轴值，则将其放入 greater 列表中。然后我们调用包含三个参数的 concat 函数。
- 列表名称
less - 变量
pivot - 列表名称
greater
public List<int> quicksort( List<int> a)
{
Random r = new Random();
List<int> less = new List<int>();
List<int> greater = new List<int>();
if (a.Count <= 1)
return a;
int pos =r.Next(a.Count);
int pivot = a[pos];
a.RemoveAt(pos);
foreach (int x in a)
{
if (x <= pivot)
{
less.Add(x);
}
else
{
greater.Add(x);
}
}
return concat(quicksort(less), pivot, quicksort(greater));
}
这里的 concat 函数扮演着非常重要的角色，quicksort 算法通过 concat 函数使用递归方法。
这里 concat 函数接收三个参数，两个列表和 pivot 值。我们在这里定义了一个新的整数列表，名为 sorted。它将 less、pivot 和 greater 全部连接到 sorted 列表中，然后将此 sorted 列表返回给 quicksort 方法。quicksort 方法接收此 sorted 列表，然后将 sorted 列表返回给将 unsorted 列表发送到 quicksort 方法的函数。
concat 的列表是
public List<int> concat(List<int> less, int pivot, List<int> greater)
{
List<int> sorted = new List<int>(less);
sorted.Add(pivot);
foreach (int i in greater)
{
sorted.Add(i);
}
return sorted;
}
归并排序
归并排序是分而治之范式的一个例子。它是一种基于比较的排序算法。它接受一个列表，并将该列表分成两个长度几乎相等的列表。然后它通过递归地应用归并排序来对列表进行排序，这会将分好的列表分成两个子列表，并对它们也应用归并排序。
归并排序的工作方式如下：
- 如果列表长度为 0 或 1，则它已经排序。否则
- 将未排序的列表分成大小约为一半的两个子列表。
- 通过重新应用归并排序递归地对每个子列表进行排序。
- 将两个子列表合并回一个已排序的列表。
在上图中，我们有一个列表，它展示了归并排序的工作原理。
在 mergesort 函数中，我们向项目中的 mergesort 函数提供名为 m 的整数列表。我们在函数中定义了另外两个列表，名为 right 和 left。结果列表将包含已排序的列表，该列表将由该函数返回。
我们首先查看 m 列表的长度。如果 m 的长度等于或小于 1，则表示列表已排序，我们将此列表返回给调用函数。如果不是，我们将通过将给定 m 列表的长度除以 2 来获得 middle。例如，如果长度为 5 个元素，则 m 将具有 2 的值。同样，如果 m 列表的元素数量为 4，则 middle 也将具有 2 的值。实际上，长度/2 的整数部分将赋给 middle。5/2 = 2.5，因此 2 将分配给 middle。
我们将列表从这个 middle 分成两个子列表。将位于 m 中点左侧的项分配给 left，并将位于 m 中点右侧的项分配给 right。
left = mergesort(left);
right = mergesort(right);
此时，我们通过使用递归，将 left 和 right 列表传递给 mergesort 方法，并将排序后的列表重新获取到这些列表中。
一旦我们在 left 和 right 中收到了排序后的列表，我们就会比较这些列表，以确定哪个列表应该位于 result 的左侧，哪个列表应该位于 result 的右侧。如果排序后的列表已经有序，我们就调用 append 函数。
if (left[left.Count - 1] <= right[0])
return append(left, right);
mergesort 的列表是
public List<int> mergesort(List<int> m)
{
List<int> result = new List<int>();
List<int> left=new List<int>();
List<int> right = new List<int>();
if (m.Count <= 1)
return m;
int middle = m.Count / 2;
for(int i=0;i<middle; i ++)
left.Add(m[i]);
for (int i = middle; i < m.Count; i++)
right.Add(m[i]);
left = mergesort(left);
right = mergesort(right);
if (left[left.Count - 1] <= right[0])
return append(left, right);
result = merge(left, right);
return result;
}
append 函数除了按照给定的顺序连接参数中给定的列表外，没有其他作用。
public List<int> append(List<int> a, List<int> b)
{
List<int> result = new List<int>(a);
foreach (int x in b)
result.Add(x);
return result;
}
如果细分的列表没有顺序，那么我们在这里调用 merge 函数。Merge 函数接受两个列表作为参数，在代码中是列表 a 和列表 b。定义了另一个列表 s，它将保存排序后的列表。它比较两个列表的第一个元素。我们将最短的元素添加到 s 列表中，并从列表中删除该元素。
s.Add(a[0]);
a.RemoveAt(0);
当比较结束后，我们将把列表中剩余的元素（其中元素更多）放入 s 列表中，并将此列表返回给 mergesort 方法。
merge 方法的代码
public List<int> merge(List<int> a,List<int> b)
{
List<int> s = new List<int>();
while (a.Count > 0 && b.Count > 0)
{
if (a[0] < b[0])
{
s.Add(a[0]);
a.RemoveAt(0);
}
else
{
s.Add(b[0]);
b.RemoveAt(0);
}
while (a.Count >0)
{s.Add(a[0]);
a.RemoveAt(0);
}
堆排序
堆排序属于选择排序算法范式，是一种基于比较的算法。
Heapsort 以递归方式工作。它根据给定数据构建堆，然后对这些堆进行排序。
在堆排序的代码中，我们有一个 heapsort 方法，它接收一个数组 numbers 和一个变量 array_size，该变量包含该数组的长度。
int [] heapSort(int [] numbers, int array_size)
{
int i, temp;
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
return numbers;
}
有一个函数 shifDown 是这个 heapsort 的核心。这个函数创建堆并对它们进行排序。
shiftDown 确保堆的根包含比其前身大的元素。如果是，则正常，否则交换元素以使其排序，然后将结果发送给 heapsort 函数。
void siftDown(int [] numbers, int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (done==0 ))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;}
else
done = 1;
}}
冒泡排序
冒泡排序是初学者非常常用的技术。它易于实现和理解。在冒泡排序中，未排序列表中的每个元素都与下一个元素进行比较，如果第一个元素的值大于第二个元素的值，则它们交换位置。
重复此操作，直到每个元素都与整个列表进行比较。
结果可能具有升序或降序排列的元素。
冒泡排序包含若干趟。趟数取决于列表中的元素数量。元素越多意味着趟数越多。
冒泡排序的代码非常容易编写和理解。它由两个循环组成——一个主循环和一个嵌套循环。主循环描述了趟数，嵌套循环定义了比较次数。列表如下：
public List<int> bubblesort(List<int> a)
{
int temp;
// foreach(int i in a)
for(int i=1; i<=a.Count; i++)
for(int j=0; j<a.Count-i; j++)
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
return a;
}
冒泡排序易于实现，但它是一种缓慢的排序算法。它在每种情况下都会遍历未排序列表中的每个元素。这就是为什么它的最坏情况和平均情况复杂度为0(n2)。
关注点
来源：本文中使用的图片均取自 en.wikipedia.com。
希望这能对初学者和信息寻求者有所帮助。您可以通过 jibran82@hotmail.com 与我联系。