C# 中的比较排序算法详解
4.69/5 (24投票s)
以 C# 编写的各种基于比较的排序算法的简化视图，包含每次迭代和传递的详细说明。
引言
在计算机科学和数学中，排序算法是一种用于将列表中的元素按特定顺序排列的算法。这些算法大致分为两大类：基于比较的排序算法，包括冒泡排序 (BubbleSort)、选择排序 (SelectionSort)、插入排序 (InsertionSort)、希尔排序 (ShellSort)、归并排序 (MergeSort)、堆排序 (HeapSort) 和快速排序 (QuickSort)，它们是最常用的；以及非基于比较的排序算法，例如基数排序 (RadixSort)、桶排序 (BucketSort) 等。本文的重点是以简化的方式提供各种基于比较的排序算法，并附带优化、清理、易于理解的代码（附有注释和说明）。
背景
在深入研究各种基于比较的排序算法的过程中，我意识到大多数算法都是使用 C/C++ 中的指针来说明的，并且由于明显的原因，很少用 C# 编写。然而，作为一名 C# 开发者，我知道如果想用自己的编程语言将算法与其规范关联起来，并以简单有效的方式进行编程，需要经历多少痛苦。
本文是我在这些排序算法的编码实践中的一个汇编列表。我不会以图形或图像的方式来说明这些算法的工作原理，因为维基百科是最佳来源，事实上，我的知识也继承自那里。然而，我的重点将是纯粹从程序员的角度出发，实现这些算法在 C# 中的应用，以及在考虑最佳情况、最坏情况和平均情况复杂度时需要注意的事项。
使用代码
在“基于比较的排序算法”这个大类下，我们有几个子类，例如交换排序 (Exchange sorts)、选择排序 (Selection sorts)、插入排序 (Insertion sorts)、归并排序 (Merge sorts) 等，我们将在稍后通过实现来逐一了解。
第一步是创建样本数据集（在本例中是数组）。还要创建两种交换算法，一种使用临时变量，一种不使用临时变量，以供我们的排序机制使用。
long[] inputArray = new long[1000];
Random rnd = new Random();
for (int i = 0; i < inputArray.Length; i++)
{
inputArray[i] = rnd.Next();
}
private void Swap(ref long valOne, ref long valTwo)
{
valOne = valOne + valTwo;
valTwo = valOne - valTwo;
valOne = valOne - valTwo;
}
private void SwapWithTemp(ref long valOne, ref long valTwo)
{
long temp = valOne;
valOne = valTwo;
valTwo = temp;
}
这是样本数据（随机）以及我们将要用于排序算法的交换机制。
交换排序
现在让我们从“基于交换的排序”类别开始。这里有两个最常用的算法。一个是简单且平凡的“冒泡排序”，另一个是该组中最快的“快速排序”。
冒泡排序
这是一种直接且简单的对数据进行排序的方法。该算法从数据集的开头开始。它比较前两个元素，如果第一个大于第二个，则交换它们。它继续对数据集末尾的每一对相邻元素执行此操作。然后它再次从前两个元素开始，重复进行，直到在最后一趟中没有发生交换。此算法效率极低，很少使用。
- 最佳情况 - O(n)
- 平均情况 - O(n^2)
- 最坏情况 - O(n^2)
- 稳定性 - 稳定
private void BubbleSort(long[] inputArray)
{
for (int iterator = 0; iterator < inputArray.Length; iterator++)
{
for (int index = 0; index < inputArray.Length - 1; index++)
{
if (inputArray[index] > inputArray[index + 1])
{
Swap(ref inputArray[index], ref inputArray[index+1]);
}
}
}
}
快速排序
这是一种分治算法，依赖于分区操作，即，要对数组进行分区，请选择一个称为枢轴的元素，将所有小于枢轴的元素移到它前面，将所有大于枢轴的元素移到它后面。这可以在线性时间和原地完成。然后，递归地对子列表进行排序。
- 最佳情况 - O(n log n)
- 平均情况 - O(n log n)
- 最坏情况 - O(n^2)
- 稳定性 - 取决于枢轴的处理方式
private void QuickSort(long[] inputArray)
{
int left = 0;
int right = inputArray.Length - 1;
InternalQuickSort(inputArray, left, right);
}
<summary>
// Internal recursive sort algorithm for quick sort
// using divide and conquer. Sorting is done based on pivot
</summary>
<param name="inputArray"></param>
<param name="left"></param>
<param name="right"></param>
private void InternalQuickSort(long[] inputArray, int left, int right)
{
int pivotNewIndex = Partition(inputArray, left, right);
long pivot = inputArray[(left + right) / 2];
if (left < pivotNewIndex-1)
InternalQuickSort(inputArray, left, pivotNewIndex - 1);
if (pivotNewIndex < right)
InternalQuickSort(inputArray, pivotNewIndex, right);
}
//This operation returns a new pivot everytime it is called recursively
//and swaps the array elements based on pivot value comparison
private int Partition(long[] inputArray, int left, int right)
{
int i = left, j = right;
long pivot = inputArray[(left + right) / 2];
while (i <= j)
{
while (inputArray[i] < pivot)
i++;
while (inputArray[j] < pivot)
j--;
if (i <= j)
{
SwapWithTemp(ref inputArray[i], ref inputArray[j]);
i++; j--;
}
}
return i;
}
选择排序
在“选择排序”类别中，我们又有两个熟悉的算法。一个是“选择排序”本身，另一个是“堆排序”。
选择排序
它本质上是一种原地比较排序。它的复杂度为 O(n^2)，在处理大型列表时效率低下，并且通常比类似的插入排序表现更差。选择排序以其简单性而闻名，并且在某些情况下比更复杂的算法具有性能优势。它几乎在所有情况下都比冒泡排序表现更好。
- 最佳情况 - O(n^2)
- 平均情况 - O(n^2)
- 最坏情况 - O(n^2)
- 稳定性 - 取决于实现
private void SelectionSort(long[] inputArray)
{
long index_of_min = 0;
for (int iterator = 0; iterator < inputArray.Length - 1; iterator++)
{
index_of_min = iterator;
for (int index = iterator+1; index < inputArray.Length; index++)
{
if (inputArray[index] < inputArray[index_of_min])
index_of_min = index;
}
Swap(ref inputArray[iterator], ref inputArray[index_of_min]);
}
}
堆排序
这是一种基于比较的排序算法，属于选择排序家族。尽管在大多数机器上，其在实践中的速度比精心实现的快速排序要慢一些，但它具有更有利的 O(n log n) 的最坏情况运行时间优势。堆排序是一种原地算法，但它不是稳定的排序。堆排序的工作原理正如其名称所示。它首先将数据集构建成一个堆，然后提取最大项并将其放置在已排序数组的末尾。在移除最大项后，它会重建堆，移除剩余的最大项，并将其放置在已排序数组末尾的下一个可用位置。重复此过程，直到堆中没有剩余项且已排序数组已满。基本实现需要两个数组——一个用于存放堆，另一个用于存放已排序元素。
堆排序将输入列表的元素插入到堆数据结构中。直到没有剩余项为止，提取最大值（在最大堆中），提取的值按排序顺序排列。每次提取后，堆的不变量都会得到保持，因此唯一的成本就是提取的成本。
- 最佳情况 - O(n log n)
- 平均情况 - O(n log n)
- 最坏情况 - O(n log n)
- 稳定性 - 不稳定
private void HeapSort(long[] inputArray)
{
for (int index = (inputArray.Length / 2) - 1; index >= 0; index--)
Heapify(inputArray, index, inputArray.Length);
for (int index = inputArray.Length - 1; index >= 1; index--)
{
SwapWithTemp(ref inputArray[0], ref inputArray[index]);
Heapify(inputArray, 0, index - 1);
}
}
此函数内部调用上面显示的 `Heapify()` 函数，该函数使用堆的特殊属性之一来构建数组内容的堆数据结构，该属性规定如果 B 是 A 的子节点，则 key(A) ≥ key(B)。这意味着具有最大键的元素始终是根节点（最大堆）。
private void Heapify(long[] inputArray, int root, int bottom)
{
bool completed = false;
int maxChild;
while((root*2 <= bottom) && (!completed))
{
if (root * 2 == bottom)
maxChild = root * 2;
else if (inputArray[root * 2] > inputArray[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (inputArray[root] < inputArray[maxChild])
{
SwapWithTemp(ref inputArray[root], ref inputArray[maxChild]);
root = maxChild;
}
else
{
completed = true;
}
}
}
插入排序
我们的下一类别是插入排序，我们将介绍两种算法：“插入排序”本身和“希尔排序”。我们来看一下。
插入排序
这是一种简单的排序算法，对于小型列表和大部分已排序的列表相对有效，并且通常用作更复杂算法的一部分。它通过逐个从列表中取出元素，并将它们插入到新的已排序列表中正确的位置来工作。希尔排序是插入排序的变体，对于大型列表更有效，因为在数组中，插入成本很高，需要将所有元素向右移动一位。
- 最佳情况 - O(n)
- 平均情况 - O(n^2)
- 最坏情况 - O(n^2)
- 稳定性 - 稳定
private void InsertionSort(long[] inputArray)
{
long j = 0 ;
long temp = 0 ;
for (int index = 1; index < inputArray.Length; index++)
{
j = index;
temp = inputArray[index];
while ((j > 0) && (inputArray[j - 1] > temp))
{
inputArray[j] = inputArray[j - 1];
j = j - 1;
}
inputArray[j] = temp;
}
}
希尔排序
它通过一次将错位元素移动多个位置来改进冒泡排序和插入排序。它比较相隔若干位置的元素。这使得元素可以朝着其预期位置“迈出更大的步伐”。通过越来越小的间隔大小多次遍历数据。希尔排序的最后一步是简单的插入排序，但到那时，数据数组已保证几乎有序。
- 最佳情况 - O(n)
- 平均情况 - 取决于间隔序列
- 最坏情况 - O(n^2) 或 O(nlog^2 n) 取决于间隔序列
- 稳定性 - 不稳定
private void ShellSort(long[] inputArray)
{
long j, temp = 0;
int increment = (inputArray.Length) / 2;
while (increment > 0)
{
for (int index = 0; index < inputArray.Length; index++)
{
j = index;
temp = inputArray[index];
while ((j >= increment) && inputArray[j - increment] > temp)
{
inputArray[j] = inputArray[j - increment];
j = j - increment;
}
inputArray[j] = temp;
}
if (increment / 2 != 0)
increment = increment / 2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
归并排序
在此类别中，我只介绍了一种常见的排序，那就是归并排序。
归并排序
它利用了将已排序列表合并到新排序列表中的便利性。它首先比较每两个元素（例如，1 与 2，然后是 3 与 4...），如果第一个元素应该排在第二个之后，则交换它们。然后它将每对两个元素的列表合并成四个元素的列表，然后合并这些四个元素的列表，依此类推；直到最后将两个列表合并成最终的已排序列表。在大多数实现中，它是稳定的，这意味着它在已排序的输出中保持相等键元素的输入顺序。它是分治算法范例的一个例子。
- 最佳情况 - O(n) 或 O(n log n)
- 平均情况 - O(n log n)
- 最坏情况 - O(n log n)
- 稳定性 - 取决于实现（如果原地合并可以稳定，那么这个也将是稳定的）
private void MergeSort(long[] inputArray)
{
int left = 0;
int right = inputArray.Length - 1;
InternalMergeSort(inputArray, left, right);
}
InternalMergeSort 是一个递归函数，它递归地排序左侧和右侧的内容，其代码非常直观，如下所示。
private void InternalMergeSort(long[] inputArray, int left, int right)
{
int mid = 0;
if (left < right)
{
mid = (left + right) / 2;
InternalMergeSort(inputArray, left, mid);
InternalMergeSort(inputArray,(mid + 1), right);
MergeSortedArray(inputArray, left, mid, right);
}
}
归并排序的最后一步是将两个已排序的数组合并（在上一步中）。MergeSortedArray 函数每次都执行完全相同的操作，并且是递归的。
private void MergeSortedArray(long[] inputArray, int left, int mid, int right)
{
int index = 0;
int total_elements = right-left+1; //BODMAS rule
int right_start = mid + 1;
int temp_location = left;
long[] tempArray = new long[total_elements];
while ((left <= mid) && right_start <= right)
{
if (inputArray[left] <= inputArray[right_start])
{
tempArray[index++] = inputArray[left++];
}
else
{
tempArray[index++] = inputArray[right_start++];
}
}
if (left > mid)
{
for(int j = right_start; j <= right; j++)
tempArray[index++] = inputArray[right_start++];
}
else
{
for(int j = left; j <= mid; j++)
tempArray[index++] = inputArray[left++];
}
//Array.Copy(tempArray, 0, inputArray, temp_location, total_elements);
// just another way of accomplishing things (in-built copy)
for (int i = 0, j = temp_location; i < total_elements; i++, j++)
{
inputArray[j] = tempArray[i];
}
}
排序算法的稳定性
如果排序算法保持具有相等键的记录的相对顺序，则该排序算法是稳定的。也就是说，如果存在相等的键（假设键是 K），并且存在与该相同键关联的两个不同记录（K->A）和（K->B），并且在原始未排序列表中，A 出现在 B 之前，那么在应用排序算法后，如果它们的顺序得到保留，即 A 仅出现在 B 之前，则该算法是稳定的。如果所有键都不同，则不需要区分。此外，在整数等无法区分的类型，或整个元素都是键的情况下，稳定性不适用。
例如，假设我们有集合 {6,8}, {2,4}, {6,5}, {4,7}，并且我们想按第一个分量进行排序，那么可以得到两种不同的结果，如下所示：
- {2,4}, {4,7}, {6,8}, {6,5} 和
- {2,4}, {4,7}, {6,5}, {6,8}
在这种情况下，a 指的是排序算法的稳定性，其中保留了相等键元素的原始顺序，而 b 指的是不稳定的算法，其中顺序“可能”会改变。
然而，请注意，不稳定的排序算法可以特别实现为稳定的。一种方法是人为地扩展键比较，以便对具有相同键的两个对象之间的比较，使用原始数据顺序中的条目顺序作为平局的决定因素。然而，记住这个顺序通常需要额外的计算成本。
在上述排序算法中，冒泡排序、插入排序和归并排序是稳定的，而堆排序和希尔排序是不稳定的。对于选择排序、归并排序和快速排序，这些算法的稳定性通常取决于它们的实现方式。
结论
附带的代码已简化，包含一个硬编码的数据集和多个打印语句，用于遍历每个传递和每次迭代。通过本文，我只触及了非常常见的基于比较的排序，但请放心，一旦发布完成，我将深入介绍基数排序和桶排序。