C#七大经典排序算法系列（下）

《C#七大经典排序算法系列（下）》是一篇文章，通过介绍七种经典的排序算法，帮助读者更好地理解排序算法的原理和操作，并且让读者掌握这些算法的基本实现方法。本文将会细致地讲解每种算法的思路、时间复杂度以及使用场景，希望读者能在阅读后掌握七种排序算法的差异和选用方法。

文章包含七种排序算法，分别为：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序和希尔排序。以下分别对每种算法进行详细讲解：

冒泡排序

冒泡排序的基本思想是，从最后一个元素开始，逐个和前一个元素比较，如果后一个元素比前一个元素小，则交换它们的位置，一直重复这个过程直到排序完成。冒泡排序的时间复杂度为O(n²)，平均性能较差，不适合大规模数据排序。下面是用C#代码实现冒泡排序的示例：

public static void BubbleSort(int[] arr)
{
    for (int i = arr.Length - 1; i >= 0; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

选择排序

选择排序的基本思想是，每次从未排序的元素中选择最小的元素，将它交换到已排序元素的最后面，最终得到有序序列。选择排序的时间复杂度也为O(n²)，与冒泡排序相当，不适合大规模数据排序。以下是用C#代码实现选择排序的示例：

public static void SelectionSort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

插入排序

插入排序的基本思想是，将待排序的原素插入到已排序序列中的适当位置，使得插入后仍然有序。插入排序的时间复杂度为O(n²)，最好情况下，插入排序可以达到O(n)的时间复杂度。以下是用C#代码实现插入排序的示例：

public static void InsertSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
}

快速排序

快速排序是一种分治算法，它的基本思想是选择一个关键元素，将序列分为两个子序列，左侧子序列元素均小于关键元素，右侧子序列元素均大于关键元素，然后对两个子序列递归进行快速排序，直到子序列长度为1。快速排序的时间复杂度为O(nlogn)，其中常数因子比归并排序小，是常用的排序算法。以下是用C#代码实现快速排序的示例：

public static void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;
    int pivot = arr[left];
    int l = left + 1, r = right;

    while (l <= r)
    {
        if (arr[l] < pivot && arr[r] > pivot)
        {
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;
        }
        if (arr[l] >= pivot) l++;
        if (arr[r] <= pivot) r--;
    }

    int temp2 = arr[left];
    arr[left] = arr[r];
    arr[r] = temp2;

    QuickSort(arr, left, r - 1);
    QuickSort(arr, r + 1, right);
}

归并排序

归并排序是一种分治算法，它将序列分为两个子序列，对子序列进行递归排序，然后将两个子序列合并成一个有序序列。归并排序的时间复杂度为O(nlogn)，不易受到初始数据集的影响，是一种底层排序算法。以下是用C#代码实现归并排序的示例：

public static void MergeSort(int[] arr, int start, int end)
{
    if (start >= end) return;

    int mid = (start + end) / 2;
    MergeSort(arr, start, mid);
    MergeSort(arr, mid + 1, end);
    int[] temp = new int[end - start + 1];
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end)
    {
        if (arr[i] <= arr[j])
        {
            temp[k] = arr[i];
            i++;
        }
        else
        {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }

    while (i <= mid)
    {
        temp[k] = arr[i];
        i++;
        k++;
    }

    while (j <= end)
    {
        temp[k] = arr[j];
        j++;
        k++;
    }

    for (i = start, k = 0; i <= end; i++, k++)
    {
        arr[i] = temp[k];
    }
}

堆排序

堆排序是一种树形选择排序，它的基本思想是将序列构建成一个堆，然后将堆的最大元素与末尾元素交换，重复执行该操作，直到序列有序。堆排序的时间复杂度为O(nlogn)，常数因子较大，但不受数据序列的影响，适合数据规模很大的情况。以下是用C#代码实现堆排序的示例：

public static void HeapSort(int[] arr)
{
    for (int i = arr.Length / 2 - 1; i >= 0; i--)
    {
        Heapify(arr, i, arr.Length);
    }

    for (int i = arr.Length - 1; i >= 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        Heapify(arr, 0, i);
    }
}

public static void Heapify(int[] arr, int index, int size)
{
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int largest = index;

    if (left < size && arr[left] > arr[largest])
    {
        largest = left;
    }

    if (right < size && arr[right] > arr[largest])
    {
        largest = right;
    }

    if (largest != index)
    {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;

        Heapify(arr, largest, size);
    }
}

希尔排序

希尔排序是一种分组插入排序算法，它的基本思想是将数据按一定间隔分组，对每组内的数据进行插入排序，然后逐渐缩小间隔，直到间隔为1，最后使用普通插入排序完成排序。希尔排序的时间复杂度在O(nlogn)和O(n²)之间，取决于步长序列，但是通常情况下表现良好。以下是用C#代码实现希尔排序的示例：

public static void ShellSort(int[] arr)
{
    int len = arr.Length;
    int gap = 1;
    while (gap < len) gap = gap * 3 + 1;

    while (gap > 0)
    {
        for (int i = gap; i < len; i++)
        {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp)
            {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = temp;
        }
        gap = gap / 3;
    }
}

以上就是七种经典排序算法的讲解，读者可以根据自己的需求选择合适的算法。在实际开发中，排序算法被广泛的应用在数据库的排序、图像处理、机器学习等领域。