排序算法是计算机科学中最基础的算法之一。无论是在学术研究中还是在实际项目中，排序算法都扮演着非常重要的角色。本文将详细介绍几种常见的排序算法：冒泡排序、快速排序、插入排序、选择排序、归并排序、希尔排序、堆排序和基数排序，并用C#代码展示其实现。
冒泡排序（Bubble Sort）
算法简介
冒泡排序是一种简单但效率较低的排序算法。它通过重复地遍历数组，比较相邻的元素并交换它们的位置，将较大的元素逐步“冒泡”到数组的末尾。
算法步骤
-
从第一个元素开始，比较相邻元素的大小。
-
如果前一个元素比后一个元素大，则交换它们的位置。
-
对每一轮遍历，未排序的部分长度减一。
-
重复以上步骤，直到没有元素需要交换。
C#实现
using System;class Program
{static void BubbleSort(int[] array){for (int i = 0; i < array.Length - 1; i++){for (int j = 0; j < array.Length - 1 - i; j++){if (array[j] > array[j + 1]){// 交换元素int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}static void Main(string[] args){int[] array = { 64, 34, 25, 12, 22, 11, 90 };Console.WriteLine("排序前: " + string.Join(", ", array));BubbleSort(array);Console.WriteLine("排序后: " + string.Join(", ", array));}
}
快速排序（Quick Sort）
算法简介
快速排序是一种分治算法，它通过选择一个基准值（pivot）将数组分为两个子数组：小于基准值的元素和大于基准值的元素，然后递归地对这两个子数组进行排序。
算法步骤
-
选择一个基准值。
-
将数组分为两部分：小于基准值的元素和大于基准值的元素。
-
递归地对两部分进行排序。
-
合并结果。
C#实现
using System;class Program
{static void QuickSort(int[] array, int left, int right){if (left < right){int pivotIndex = Partition(array, left, right);QuickSort(array, left, pivotIndex - 1);QuickSort(array, pivotIndex + 1, right);}}static int Partition(int[] array, int left, int right){int pivot = array[right];int i = left - 1;for (int j = left; j < right; j++){if (array[j] <= pivot){i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int temp1 = array[i + 1];array[i + 1] = array[right];array[right] = temp1;return i + 1;}static void Main(string[] args){int[] array = { 64, 34, 25, 12, 22, 11, 90 };Console.WriteLine("排序前: " + string.Join(", ", array));QuickSort(array, 0, array.Length - 1);Console.WriteLine("排序后: " + string.Join(", ", array));}
}插入排序（Insertion Sort）
算法简介
插入排序通过构建有序序列，将未排序的元素逐一插入到已排序序列中。它的效率在小规模数据集上表现较好。
算法步骤
-
从第二个元素开始，将当前元素与前面的元素进行比较。
-
如果当前元素比前面的元素小，则将其插入到正确的位置。
-
对剩余的元素重复上述步骤。
C#实现
using System;class Program
{static void SelectionSort(int[] array){for (int i = 0; i < array.Length - 1; i++){int minIndex = i;for (int j = i + 1; j < array.Length; j++){if (array[j] < array[minIndex]){minIndex = j;}}// 交换最小值int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}static void Main(string[] args){int[] array = { 64, 34, 25, 12, 22, 11, 90 };Console.WriteLine("排序前: " + string.Join(", ", array));SelectionSort(array);Console.WriteLine("排序后: " + string.Join(", ", array));}
}归并排序（Merge Sort）
算法简介
归并排序是一种分治算法，它将数组分成较小的部分，分别排序后再合并。
算法步骤
-
将数组递归分成两部分。
-
对每部分进行排序。
-
合并两个有序部分。
C#实现
using System;class Program
{static void MergeSort(int[] array, int left, int right){if (left < right){int mid = (left + right) / 2;MergeSort(array, left, mid);MergeSort(array, mid + 1, right);Merge(array, left, mid, right);}}static void Merge(int[] array, int left, int mid, int right){int n1 = mid - left + 1;int n2 = right - mid;int[] leftArray = new int[n1];int[] rightArray = new int[n2];Array.Copy(array, left, leftArray, 0, n1);Array.Copy(array, mid + 1, rightArray, 0, n2);int i = 0, j = 0, k = left;while (i < n1 && j < n2){if (leftArray[i] <= rightArray[j]){array[k++] = leftArray[i++];}else{array[k++] = rightArray[j++];}}while (i < n1){array[k++] = leftArray[i++];}while (j < n2){array[k++] = rightArray[j++];}}static void Main(string[] args){int[] array = { 64, 34, 25, 12, 22, 11, 90 };Console.WriteLine("排序前: " + string.Join(", ", array));MergeSort(array, 0, array.Length - 1);Console.WriteLine("排序后: " + string.Join(", ", array));}
}对比几种排序算法
| 算法 | 时间复杂度（最优） | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n^2) | O(log n) | 不稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
在这篇文章中，我们详细介绍了几种常见排序算法，包括冒泡排序、快速排序、插入排序、选择排序和归并排序。每种算法的原理、步骤以及C#代码实现都已展示。
如何选择排序算法？
-
数据规模较小： 可以选择插入排序或选择排序，因其实现简单。
-
追求性能： 快速排序或归并排序在大规模数据上表现优异。
-
稳定性需求： 如果排序后需要保持相同值的原始顺序，选择稳定的排序算法（如冒泡排序或归并排序）。