常见排序算法一般资源：排序的稳定性、就地与非就地、冒泡排序、选择排序、插入排序、希尔排序、快速排序、合并排序、堆排序、奖励排序 AWS 安全 LIVE！

2025-06-09

常见的排序算法

一般资源：

排序稳定性

就地 vs 非就地

冒泡排序

选择排序

插入排序

希尔排序

快速排序

归并排序

堆排序

奖金种类

AWS 安全上线！

一般资源：

  1. 排序算法概述 + 复杂性
  2. 另一个有用的排序复杂性表格

排序稳定性

  • 稳定的排序算法将在按给定的键排序后保留项目的原始顺序。
  • 例如，仅按首字母对以下数组进行排序：[fence, fan, apple, boat, fun]，稳定排序将产生：[apple, boat, fence, fan, fun]。不稳定算法可能会产生：[apple, boat, fun, fan, fence]。
  • 注意fence, fan, fun所有元素都以字母 开头f。稳定排序在对整个数组进行排序后，会保留元素的原始顺序。不稳定排序不一定能保留原始顺序。
  • 这是一篇解释排序稳定性的好文章。

就地 vs 非就地

  • 许多排序算法都是就地的。
  • 就地算法只需要很少的额外内存即可对输入执行转换。
  • 如果需要额外的数据结构来执行转换，则该算法被视为非就地算法。
  • 就地算法允许使用变量，例如指针或索引。这些变量占用的内存非常小。
  • 就地算法通常通过覆盖/重新排列/替换输入中的元素来修改输入。
  • 非就地算法通常会创建额外的数据结构或输入的副本，以执行其工作。
  • 本文中提到的种类几乎全部都已存在。
  • 一个很好的非原地算法的例子是归并排序。你会注意到，在我的实现中，除了输入本身之外，它还需要输入的副本来执行排序。它还使用了递归，这会增加内存需求。
  • 归并排序的额外内存开销意味着它需要O(n) 额外的空间——也就是说，所需的内存与输入的大小成正比。你会注意到，列出的所有其他排序的空间复杂度都小于 O(n)——因为它们都是原地排序。
  • 如果你想要更多信息，维基百科有一篇关于就地算法的好文章

冒泡排序

资源

  1. 冒泡排序概述

总结

  • 冒泡排序实现起来非常简单，但通常很慢。
  • 它通过不断比较相邻的项目对并交换它们（将较大的项目向右移动）直到整个列表排序来实现对列表的排序。
  • 它很稳定。
  • 它是就地的。
  • 空间复杂度是，O(1)但在最坏和平均情况下的时间复杂度是O(n^2)（二次的）。
  • 由于其性能较差，通常会避免使用它。

选择排序

资源

  1. 选择排序概述

总结

  • 选择排序的实现也非常简单，但是像冒泡排序一样速度很慢。
  • 它通过迭代列表来排序，每次迭代都会将最小的元素移到列表的最前面（因此，在第一次迭代中，找到的最小元素会被移动到列表的最前面）。这个过程重复进行，直到列表排序完成。
  • 时间复杂度为O(n^2)，空间为O(1)。
  • 它是不稳定的。
  • 它已就位。

插入排序

资源

  1. 插入排序概述+实现。
  2. 插入排序概述。

总结

  • 对于非常小的列表/数组，插入排序相对较快。如果列表包含 5-15 个元素，插入排序可能是最快的排序算法。事实上，Sedgewick 在《算法》一书中建议，在快速/归并排序的实现中，对于小数组，应舍弃插入排序，转而使用插入排序。
  • 然而，对于较大的输入，插入排序很慢——在最坏和平均情况下它的时间复杂度为O(n^2)。
  • 空间就是O(1)。
  • 它很稳定。
  • 它已就位。
  • 它通过维护列表的“已排序”和“未排序”子部分来对列表进行排序。它会将未排序子部分的项目插入到已排序子部分中。
  • 在从未排序子部分插入项目之前，插入排序会将要插入的项目与已排序子部分中的项目进行比较。
  • 它通过遍历已排序的子部分并将每个项目与要插入的项目进行比较来实现这一点。它维护一个新项目应插入到的索引。
  • 一旦要插入的项目不再小于与其进行比较的项目，就会将其插入到计算出的索引处，并重复该过程，直到对整个输入进行排序。
  • 首先，排序的子部分只有一个项目（这意味着它默认排序）并且每次插入后都会增加一个。

希尔排序

资源

  1. Shellsort 概述 + 实现。
  2. 希尔排序的时间复杂度。

总结

  • 它基于插入排序，并且实现起来稍微复杂一些。
  • 它是不稳定的。
  • 它已就位。
  • 它的时间复杂度在不同实现之间并不一致，取决于所使用的间隔/间隙序列。一般认为它的运行时间在O(n)到之间O(n^2)，但最佳情况O(n log n)（线性对数）是可能的。
  • 希尔排序使用间隔/间隙来确定哪些项需要相互比较。如果间隔为 3，则每个项都会与距离 3 个项远的项（而不是其相邻项）进行比较。
  • 我在 Shellsort 实现中使用了Knuth 的间隙序列1,3,7,21,48,112,etc.。这将产生 的间隙。
  • 在排序过程中，列表每次迭代完成后，间隔都会不断减小。间隔最终会变为 1，然后会比较相邻的元素。比较完成后，列表/数组就排序完成了。
  • 在插入排序的基础上使用间隔/间隙序列，意味着会比较列表/数组中分布更广的项（而不是像插入排序那样只比较相邻的项）。与插入排序相比，这可以加快排序速度。

快速排序

资源

  1. 快速排序概述。
  2. 快速排序概述 + 实现。
  3. 详细的快速排序概述 + 实施。
  4. 快速排序概述 + 历史。

总结

  • 最快的排序之一，平均运行时间为O(n log n)。
  • 它的最坏情况时间复杂度为O(n^2)，但是随机打乱输入或选择随机枢轴可以避免这种最坏情况。
  • 空间是O(log n)（对数的）。
  • 这是一种分而治之算法。
  • 它是不稳定的。
  • 它已就位。
  • 快速排序会围绕所谓的“枢轴项”将给定列表一分为二。这种拆分称为“分区”。枢轴左侧的所有项都小于枢轴，而右侧的所有项都大于枢轴。完成此操作后，将对两个子列表进行递归排序。
  • Quicksort 有两种变体：Lomuto和Hoare。
  • Tony Hoare 发明了快速排序，他的变体实现起来比 Lomuto 的变体略微复杂（使用了递归），但比 Lomuto 的变体更高效（Lomuto 的变体不使用递归，更容易实现）。我的快速排序实现参考了 Hoare 的变体。
  • 你还会注意到，在我的快速排序实现中，我随机选择了主元，这是为了避免最坏情况下的二次时间复杂度。你也可以选择在排序前随机打乱输入，但由于 C# 没有内置的打乱算法，所以我选择了随机主元。
  • 面试中有时会问一个有趣的问题，叫做荷兰国旗问题。这个问题可以用快速排序的变体来解决。
  • 荷兰国旗问题本质上要求我们对由三种颜色组成的随机输入进行排序（荷兰国旗有三种颜色）。并将输入排序，使每种颜色归为一类。例如：[red, white, red, white, blue, white, white]排序后可能得到： 。这个问题有几种变体，但都可以使用三路快速排序[blue, white, white, white, white, red, red]在线性时间内高效解决。
  • 三路快速排序将输入分成 3 个子部分：小于枢轴的项、等于枢轴的项和大于枢轴的项。
  • 有关使用三向快速排序解决荷兰国旗问题的更详细概述，请查看《算法》一书中快速排序章节的熵最优排序部分。

归并排序

资源

  1. 归并排序概述。
  2. 归并排序概述 + 实施。
  3. 详细的归并排序概述 + 实施。
  4. 合并排序概述 + 历史。

总结

  • 另一种快速排序。与快速排序一样，归并排序也是每个程序员都应该熟悉的一种排序方法，因为它速度相对较快。
  • 简单来说，归并排序将数组分成两半，并对每一半进行独立排序 - 然后将两个排序后的部分合并在一起。
  • 从理论上讲，它比快速排序更快，平均和最佳情况的时间复杂度为O(n log n)，空间复杂度为O(n)。
  • 它很稳定。
  • 这是一种分而治之算法。
  • 它尚未到位。
  • 与霍尔的快速排序类似，归并排序也是递归的。它同样将输入列表/数组一分为二，然后对每一半进行排序。对每一半进行排序后，归并排序会将它们重新合并在一起（因此得名）。
  • 我发现归并排序是实现起来最复杂的排序算法。其次复杂的是快速排序。
  • 归并排序有两种常见类型：自上而下和自下而上。
  • 自上而下的归并排序算法从原始输入开始向下进行，将其一分为二，然后递归地将得到的每一半拆分，并持续进行，直到原始输入的每个子部分都变成一系列包含单个元素的列表。之后，它会将这些列表重新合并在一起，同时展开堆栈，形成一个已排序的数组。
  • 自下而下归并排序则以相反的方向进行（从列表的单个元素开始向上排序）。它首先对输入中单个元素大小的子部分进行合并。
  • 我的合并排序实现是自上而下的。

堆排序

资源

  1. 堆排序概述 + 实现。

总结

  • 堆排序理论上非常快。它的时间复杂度O(n log n)在平均和最坏情况下为 。最佳情况为O(n)。空间为O(1)。
  • 尽管理论上速度更快，但在实践中通常比快速/合并排序慢。
  • 它是不稳定的。
  • 它已就位。
  • 堆排序首先将输入转换为堆（通常是最大堆），然后继续从堆中移除最大项（堆中的第一个/父项），并将其与最右边的子项（最后一个项）交换。交换完成后，它会减少一个计数器（以忽略移到末尾的最大项），然后向下遍历位于第一个索引处的项。此过程重复进行，直到数组排序完成。
  • 您还可以使用最小堆进行堆排序，我在上一篇关于二叉堆的文章中也这样做过- 但是使用最大堆需要更少的内存开销/操作。

奖金种类

  • 外部归并排序- 这是归并排序的一种变体，它进行K 路合并，以处理待排序数据大于可用内存的情况。外部归并排序概述。
  • 计数排序是一种稳定的排序方法，它通过计算每个元素出现的次数，并根据这些次数计算元素应该插入的索引。这里有一个关于计数排序的精彩视频概述。
  • 基数排序 (Radixsort)是一种稳定的排序方法，其底层使用了计数排序，但每次只会对输入的数字进行排序。对于字符串，它每次只会对一个字母进行排序。例如：[123, 456, 111, 122, 333]每个数字会先按其最后一位数字排序，然后数组会按第二位数字排序，依此类推，直到输入排序完毕。这里有一个关于基数排序的精彩视频概述。

下面您将找到讨论的所有排序算法的实现：

using System;
public class Program
{
private static int[] BubbleSort(int[] input)
{
bool keepSwapping = true;
while (keepSwapping)
{
keepSwapping = false;
for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] > input[i + 1])
{
int temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
keepSwapping = true;
}
}
}
return input;
}
public static int[] SelectionSort(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
int indexOfMin = i;
for (int j = i; j < input.Length; j++)
{
if (input[indexOfMin] > input[j])
{
indexOfMin = j;
}
}
int temp = input[i];
input[i] = input[indexOfMin];
input[indexOfMin] = temp;
}
return input;
}
public static int[] InsertionSort(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
int insertAt = i;
int valueToInsert = input[insertAt];
while (insertAt > 0 && input[insertAt - 1] > valueToInsert)
{
input[insertAt] = input[insertAt - 1];
insertAt--;
}
input[insertAt] = valueToInsert;
}
return input;
}
public static int[] ShellSort(int[] input)
{
int interval = 1;
while (interval < input.Length / 3)
{
interval = 3 * interval + 1;
}
while (interval > 0)
{
for (int i = interval; i < input.Length; i++)
{
int index = i;
while (index >= interval && input[index - interval] > input[index])
{
int temp = input[index];
input[index] = input[index - interval];
input[index - interval] = temp;
index -= interval;
}
}
interval /= 3;
}
return input;
}
public static int[] QuickSort(int[] input)
{
return DoQuickSort(input, 0, input.Length - 1);
}
private static int[] DoQuickSort(int[] input, int start, int end)
{
if (start >= end)
{
return input;
}
int partitionIndex = Partition(input, start, end);
DoQuickSort(input, start, partitionIndex - 1);
DoQuickSort(input, partitionIndex + 1, end);
return input;
}
private static int Partition(int[] input, int start, int end)
{
int lo = start;
int hi = end + 1;
int pivotIndex = new Random().Next(start, end);
int pivot = input[pivotIndex];
input[pivotIndex] = input[start];
input[start] = pivot;
while (true)
{
while (input[++lo] < pivot)
{
if (lo == end)
{
break;
}
}
while (input[--hi] > pivot)
{
if (hi == start)
{
break;
}
}
if (lo >= hi)
{
break;
}
int temp = input[lo];
input[lo] = input[hi];
input[hi] = temp;
}
input[start] = input[hi];
input[hi] = pivot;
return hi;
}
public static int[] Mergesort(int[] input)
{
int[] aux = new int[input.Length];
return DoMergesort(input, aux, 0, input.Length - 1);
}
private static int[] DoMergesort(int[] input, int[] aux, int start, int end)
{
if (start >= end)
{
return input;
}
int middle = start + (end - start) / 2;
DoMergesort(input, aux, start, middle);
DoMergesort(input, aux, middle + 1, end);
return Merge(input, aux, start, middle, end);
// return Merge2(input, aux, start, middle, end);
}
private static int[] Merge(int[] input, int[] aux, int start, int middle, int end)
{
for (int i = start; i <= end; i++)
{
aux[i] = input[i];
}
int startLeft = start;//left most of left array
int startRight = middle + 1;//left most of right array
for (int i = start; i <= end; i++)
{
if (startLeft > middle)
{
input[i] = aux[startRight++];
}
else if (startRight > end)
{
input[i] = aux[startLeft++];
}
else if (aux[startRight] < aux[startLeft])
{
input[i] = aux[startRight++];
}
else
{
input[i] = aux[startLeft++];
}
}
return input;
}
private static int[] Merge2(int[] input, int[] aux, int start, int middle, int end)
{
for (int i = start; i <= end; i++)
{
aux[i] = input[i];
}
int startLeft = start;//left most of left array
int startRight = middle + 1;//left most of right array
int mergeIndex;
for (mergeIndex = start; startLeft <= middle && startRight <= end; mergeIndex++)
{
if (aux[startRight] < aux[startLeft])
{
input[mergeIndex] = aux[startRight++];
}
else
{
input[mergeIndex] = aux[startLeft++];
}
}
while (startLeft <= middle)
{
input[mergeIndex++] = aux[startLeft++];
}
while (startRight <= end)
{
input[mergeIndex++] = aux[startRight++];
}
return input;
}
private static int[] Mergesort2(int[] input)
{
int length = input.Length;
if (length < 2)
{
return input;
}
int middle = length / 2;
int[] left = new int[middle];
int[] right = new int[length - middle];
for (int i = 0; i < middle; i++)
{
left[i] = input[i];
}
for (int i = middle; i < length; i++)
{
right[i - middle] = input[i];
}
int[] leftSorted = Mergesort2(left);
int[] rightSorted = Mergesort2(right);
return Merge(leftSorted, rightSorted);
}
private static int[] Merge(int[] left, int[] right)
{
int leftIndex = 0;
int rightIndex = 0;
int mergedIndex = 0;
int[] merged = new int[left.Length + right.Length];
while (leftIndex < left.Length && rightIndex < right.Length)
{
if (left[leftIndex] <= right[rightIndex])
{
merged[mergedIndex++] = left[leftIndex++];
}
else
{
merged[mergedIndex++] = right[rightIndex++];
}
}
while (leftIndex < left.Length)
{
merged[mergedIndex++] = left[leftIndex++];
}
while (rightIndex < right.Length)
{
merged[mergedIndex++] = right[rightIndex++];
}
return merged;
}
public static int[] Heapsort(int[] input)
{
Heapify(input);
int heapSize = input.Length;
while (heapSize > 0)
{
// Take max from start of array, put last element of array at front (where max should be),
// then percolate down so that next biggest element is at front of array
// make sure to decrement heapSize in ExtractMax() to ignore previously appended max items
// (which get appended at end of array during heapsort)
int max = ExtractMax(input, heapSize);
heapSize -= 1;
// Add max to end of array and work towards front
input[heapSize] = max;
}
return input;
}
private static void Heapify(int[] input)
{
var heapSize = input.Length;
// Ignore leaf nodes (given an array of size N, leafs are at N/2 + 1, N/2 + 2, etc.)
var startAt = heapSize / 2;
for (int i = startAt; i >= 0; i--)
{
PercolateDown(input, heapSize, i);
}
}
private static void PercolateDown(int[] input, int heapSize, int i)
{
while (GetLeftChildIndex(i) < heapSize)
{
int maxChildIndex = GetMaxChildIndex(input, heapSize, i);
if (input[i] < input[maxChildIndex])
{
Swap(input, i, maxChildIndex);
}
// Keep percolating down the smaller element
i = maxChildIndex;
}
}
private static void Swap(int[] input, int indexA, int indexB)
{
int temp = input[indexA];
input[indexA] = input[indexB];
input[indexB] = temp;
}
private static int GetMaxChildIndex(int[] input, int heapSize, int i)
{
int leftChildIndex = GetLeftChildIndex(i);
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex > heapSize)
{
return leftChildIndex;
}
if (input[leftChildIndex] > input[rightChildIndex])
{
return leftChildIndex;
}
return rightChildIndex;
}
private static int GetLeftChildIndex(int i)
{
return i * 2;
}
private static int ExtractMax(int[] input, int heapSize)
{
// Take first element and put last element in its place
// Array now has 1 less element in it (and free slot at the end)
int max = input[0];
input[0] = input[heapSize - 1];
// Ignore last slot, and percolate down the first element - which just got added to first/max slot
// to ensure true max element is at index 0
PercolateDown(input, heapSize - 1, 0);
return max;
}
public static void Main()
{
var input = new[] { 18, 11, 42, 6, 18, 3 };
var input1 = new[] { 18, 11, 42, 6, 18, 3 };
var input2 = new[] { 18, 11, 42, 6, 18, 3 };
var input3 = new[] { 18, 11, 42, 6, 18, 3 };
var input4 = new[] { 18, 11, 42, 6, 18, 3 };
var input5 = new[] { 18, 11, 42, 6, 18, 3 };
var input6 = new[] { 18, 11, 42, 6, 18, 3 };
var input7 = new[] { 18, 11, 42, 6, 18, 3 };
var sorted = Mergesort(input);
var sorted1 = Heapsort(input1);
var sorted2 = Mergesort2(input2);
var sorted3 = BubbleSort(input3);
var sorted4 = InsertionSort(input4);
var sorted5 = SelectionSort(input5);
var sorted6 = QuickSort(input6);
var sorted7 = ShellSort(input7);
}
}
view raw Sorting.cs hosted with ❤ by GitHub
using System;
public class Program
{
private static int[] BubbleSort(int[] input)
{
bool keepSwapping = true;
while (keepSwapping)
{
keepSwapping = false;
for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] > input[i + 1])
{
int temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
keepSwapping = true;
}
}
}
return input;
}
public static int[] SelectionSort(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
int indexOfMin = i;
for (int j = i; j < input.Length; j++)
{
if (input[indexOfMin] > input[j])
{
indexOfMin = j;
}
}
int temp = input[i];
input[i] = input[indexOfMin];
input[indexOfMin] = temp;
}
return input;
}
public static int[] InsertionSort(int[] input)
{
for (int i = 0; i < input.Length; i++)
{
int insertAt = i;
int valueToInsert = input[insertAt];
while (insertAt > 0 && input[insertAt - 1] > valueToInsert)
{
input[insertAt] = input[insertAt - 1];
insertAt--;
}
input[insertAt] = valueToInsert;
}
return input;
}
public static int[] ShellSort(int[] input)
{
int interval = 1;
while (interval < input.Length / 3)
{
interval = 3 * interval + 1;
}
while (interval > 0)
{
for (int i = interval; i < input.Length; i++)
{
int index = i;
while (index >= interval && input[index - interval] > input[index])
{
int temp = input[index];
input[index] = input[index - interval];
input[index - interval] = temp;
index -= interval;
}
}
interval /= 3;
}
return input;
}
public static int[] QuickSort(int[] input)
{
return DoQuickSort(input, 0, input.Length - 1);
}
private static int[] DoQuickSort(int[] input, int start, int end)
{
if (start >= end)
{
return input;
}
int partitionIndex = Partition(input, start, end);
DoQuickSort(input, start, partitionIndex - 1);
DoQuickSort(input, partitionIndex + 1, end);
return input;
}
private static int Partition(int[] input, int start, int end)
{
int lo = start;
int hi = end + 1;
int pivotIndex = new Random().Next(start, end);
int pivot = input[pivotIndex];
input[pivotIndex] = input[start];
input[start] = pivot;
while (true)
{
while (input[++lo] < pivot)
{
if (lo == end)
{
break;
}
}
while (input[--hi] > pivot)
{
if (hi == start)
{
break;
}
}
if (lo >= hi)
{
break;
}
int temp = input[lo];
input[lo] = input[hi];
input[hi] = temp;
}
input[start] = input[hi];
input[hi] = pivot;
return hi;
}
public static int[] Mergesort(int[] input)
{
int[] aux = new int[input.Length];
return DoMergesort(input, aux, 0, input.Length - 1);
}
private static int[] DoMergesort(int[] input, int[] aux, int start, int end)
{
if (start >= end)
{
return input;
}
int middle = start + (end - start) / 2;
DoMergesort(input, aux, start, middle);
DoMergesort(input, aux, middle + 1, end);
return Merge(input, aux, start, middle, end);
// return Merge2(input, aux, start, middle, end);
}
private static int[] Merge(int[] input, int[] aux, int start, int middle, int end)
{
for (int i = start; i <= end; i++)
{
aux[i] = input[i];
}
int startLeft = start;//left most of left array
int startRight = middle + 1;//left most of right array
for (int i = start; i <= end; i++)
{
if (startLeft > middle)
{
input[i] = aux[startRight++];
}
else if (startRight > end)
{
input[i] = aux[startLeft++];
}
else if (aux[startRight] < aux[startLeft])
{
input[i] = aux[startRight++];
}
else
{
input[i] = aux[startLeft++];
}
}
return input;
}
private static int[] Merge2(int[] input, int[] aux, int start, int middle, int end)
{
for (int i = start; i <= end; i++)
{
aux[i] = input[i];
}
int startLeft = start;//left most of left array
int startRight = middle + 1;//left most of right array
int mergeIndex;
for (mergeIndex = start; startLeft <= middle && startRight <= end; mergeIndex++)
{
if (aux[startRight] < aux[startLeft])
{
input[mergeIndex] = aux[startRight++];
}
else
{
input[mergeIndex] = aux[startLeft++];
}
}
while (startLeft <= middle)
{
input[mergeIndex++] = aux[startLeft++];
}
while (startRight <= end)
{
input[mergeIndex++] = aux[startRight++];
}
return input;
}
private static int[] Mergesort2(int[] input)
{
int length = input.Length;
if (length < 2)
{
return input;
}
int middle = length / 2;
int[] left = new int[middle];
int[] right = new int[length - middle];
for (int i = 0; i < middle; i++)
{
left[i] = input[i];
}
for (int i = middle; i < length; i++)
{
right[i - middle] = input[i];
}
int[] leftSorted = Mergesort2(left);
int[] rightSorted = Mergesort2(right);
return Merge(leftSorted, rightSorted);
}
private static int[] Merge(int[] left, int[] right)
{
int leftIndex = 0;
int rightIndex = 0;
int mergedIndex = 0;
int[] merged = new int[left.Length + right.Length];
while (leftIndex < left.Length && rightIndex < right.Length)
{
if (left[leftIndex] <= right[rightIndex])
{
merged[mergedIndex++] = left[leftIndex++];
}
else
{
merged[mergedIndex++] = right[rightIndex++];
}
}
while (leftIndex < left.Length)
{
merged[mergedIndex++] = left[leftIndex++];
}
while (rightIndex < right.Length)
{
merged[mergedIndex++] = right[rightIndex++];
}
return merged;
}
public static int[] Heapsort(int[] input)
{
Heapify(input);
int heapSize = input.Length;
while (heapSize > 0)
{
// Take max from start of array, put last element of array at front (where max should be),
// then percolate down so that next biggest element is at front of array
// make sure to decrement heapSize in ExtractMax() to ignore previously appended max items
// (which get appended at end of array during heapsort)
int max = ExtractMax(input, heapSize);
heapSize -= 1;
// Add max to end of array and work towards front
input[heapSize] = max;
}
return input;
}
private static void Heapify(int[] input)
{
var heapSize = input.Length;
// Ignore leaf nodes (given an array of size N, leafs are at N/2 + 1, N/2 + 2, etc.)
var startAt = heapSize / 2;
for (int i = startAt; i >= 0; i--)
{
PercolateDown(input, heapSize, i);
}
}
private static void PercolateDown(int[] input, int heapSize, int i)
{
while (GetLeftChildIndex(i) < heapSize)
{
int maxChildIndex = GetMaxChildIndex(input, heapSize, i);
if (input[i] < input[maxChildIndex])
{
Swap(input, i, maxChildIndex);
}
// Keep percolating down the smaller element
i = maxChildIndex;
}
}
private static void Swap(int[] input, int indexA, int indexB)
{
int temp = input[indexA];
input[indexA] = input[indexB];
input[indexB] = temp;
}
private static int GetMaxChildIndex(int[] input, int heapSize, int i)
{
int leftChildIndex = GetLeftChildIndex(i);
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex > heapSize)
{
return leftChildIndex;
}
if (input[leftChildIndex] > input[rightChildIndex])
{
return leftChildIndex;
}
return rightChildIndex;
}
private static int GetLeftChildIndex(int i)
{
return i * 2;
}
private static int ExtractMax(int[] input, int heapSize)
{
// Take first element and put last element in its place
// Array now has 1 less element in it (and free slot at the end)
int max = input[0];
input[0] = input[heapSize - 1];
// Ignore last slot, and percolate down the first element - which just got added to first/max slot
// to ensure true max element is at index 0
PercolateDown(input, heapSize - 1, 0);
return max;
}
public static void Main()
{
var input = new[] { 18, 11, 42, 6, 18, 3 };
var input1 = new[] { 18, 11, 42, 6, 18, 3 };
var input2 = new[] { 18, 11, 42, 6, 18, 3 };
var input3 = new[] { 18, 11, 42, 6, 18, 3 };
var input4 = new[] { 18, 11, 42, 6, 18, 3 };
var input5 = new[] { 18, 11, 42, 6, 18, 3 };
var input6 = new[] { 18, 11, 42, 6, 18, 3 };
var input7 = new[] { 18, 11, 42, 6, 18, 3 };
var sorted = Mergesort(input);
var sorted1 = Heapsort(input1);
var sorted2 = Mergesort2(input2);
var sorted3 = BubbleSort(input3);
var sorted4 = InsertionSort(input4);
var sorted5 = SelectionSort(input5);
var sorted6 = QuickSort(input6);
var sorted7 = ShellSort(input7);
}
}
view raw Sorting.cs hosted with ❤ by GitHub

与往常一样，如果您发现这篇文章中有任何错误，请告诉我！

鏂囩珷鏉ユ簮锛�https://dev.to/jjb/part-12-common-sorting-algorithms-2f37
Devto 翻译
PREV
不要重复你的数据 - 从代码审查中学习获取重构的代码和上述组件的解释
NEXT
CS Level Up系列介绍