C#中常见的排序算法详解

本文将详细介绍 C# 中几种常见的排序算法，帮助读者更好地理解和应用这些算法。每种算法都附有详细的解释和代码示例，以便读者能够轻松上手。

冒泡排序

介绍

冒泡排序是一种简单的排序算法，其基本思想是通过多次遍历数组，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。这样，每一轮遍历都会将当前未排序部分的最大值移动到末尾。冒泡排序的时间复杂度为 O(n²)。

动图演示

代码示例

public static int[] BubbleSort(int[] arr)
{
    for (int i = 0; i     {
        for (int j = 0; j         {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

选择排序

介绍

选择排序是一种简单直观的排序算法。它的基本思想是每次从未排序的部分中找到最小的元素，将其放到已排序部分的末尾。选择排序的时间复杂度也是 O(n²)。

动图演示

代码示例

public static int[] SelectSort(int[] arr)
{
    for (int i = 0; i     {
        int minIndex = i;
        for (int j = i + 1; j         {
            if (arr[j]             {
                minIndex = j;
            }
        }
        if (minIndex != i)
        {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

插入排序

介绍

插入排序是一种简单直观的排序算法，其基本思想是将每个待排序的元素插入到已排序部分的适当位置。插入排序的时间复杂度也是 O(n²)。

动图演示

代码示例

public static int[] InsertSort(int[] arr)
{
    for (int i = 1; i     {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

希尔排序

介绍

希尔排序是插入排序的一种改进版本，通过引入增量序列来减少元素之间的比较次数。希尔排序的时间复杂度通常优于 O(n²)，但具体取决于增量序列的选择。

动图演示

代码示例

public static int[] ShellSort(int[] arr)
{
    int n = arr.Length;
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i         {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp)
            {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
    return arr;
}

快速排序

介绍

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。快速排序的平均时间复杂度为 O(n log n)。

动图演示

代码示例

public static int[] QuickSort(int[] arr)
{
    return QuickSortRecursive(arr, 0, arr.Length - 1);
}

private static int[] QuickSortRecursive(int[] arr, int low, int high)
{
    if (low     {
        int pi = Partition(arr, low, high);
        QuickSortRecursive(arr, low, pi - 1);
        QuickSortRecursive(arr, pi + 1, high);
    }
    return arr;
}

private static int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j     {
        if (arr[j] <= pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, high);
    return i + 1;
}

private static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

参考资料：博客园 - 常见排序算法详解，博客园 - 排序算法总结