C#算法之冒泡排序、插入排序、选择排序

在学习C#算法的过程中，冒泡排序、插入排序、选择排序是最基础且常用的排序算法之一。这些排序算法可以对数组进行排序，使其按照升序或降序排列。

本文将详细讲解这三种排序算法的原理和实现步骤，并提供两个示例说明。

冒泡排序

冒泡排序是一种比较简单的排序算法，其基本思想是：将相邻的两个元素进行比较，如果前一个元素比后一个元素大，就交换它们的位置。

具体实现步骤如下：

1. 从数组的第一个元素开始，依次将相邻的两个元素进行比较，如果顺序不对，则交换它们的位置。

2. 把数组中的元素全部比较一遍后，确定最后一个元素是最大或最小的，然后再重复以上步骤，但是不再比较最后一个元素。

3. 重复以上步骤，直到所有元素都排序完成。

冒泡排序的时间复杂度为O(n^2)，未排序的数组越大，所需的时间就越长。代码示例如下：

public static void BubbleSort(int[] arr)
{
    int temp;

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

示例1：对数组{5, 3, 8, 6, 4}进行冒泡排序，结果应该为{3, 4, 5, 6, 8}。

int[] arr = {5, 3, 8, 6, 4};
BubbleSort(arr);
foreach (int i in arr)
{
    Console.Write(i + " ");
}

输出结果为：3 4 5 6 8

插入排序

插入排序是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体实现步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序。

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。

3. 如果已排序的元素大于新元素，将该元素移到下一个位置。

4. 重复步骤3，直到已排序的元素小于或等于新元素。

5. 将新元素插入到该位置后。

6. 重复步骤2~5，直到所有元素都排序完成。

插入排序的时间复杂度为O(n^2)。代码示例如下：

public static void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int value = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > value)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = value;
    }
}

示例2：对数组{12, 11, 13, 5, 6}进行插入排序，结果应该为{5, 6, 11, 12, 13}。

int[] arr = { 12, 11, 13, 5, 6 };
InsertionSort(arr);
foreach (int i in arr)
{
    Console.Write(i + " ");
}

输出结果为：5 6 11 12 13

选择排序

选择排序也是一种简单的排序算法，其基本思想是每次找到最小值或最大值，将其放到数组的最前面或最后面，然后对剩余的未排序的元素重复以上步骤。具体实现步骤如下：

1. 在未排序的元素中找到最小值或最大值，将其放到序列的起始位置。

2. 从剩余未排序的元素中继续寻找最小值或最大值，放到已排序的序列的末尾。

3. 重复步骤2，直到所有元素都排序完成。

选择排序的时间复杂度也是O(n^2)。代码示例如下：

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;
    }
}

示例3：对数组{64, 25, 12, 22, 11}进行选择排序，结果应该为{11, 12, 22, 25, 64}。

int[] arr = { 64, 25, 12, 22, 11 };
SelectionSort(arr);
foreach (int i in arr)
{
    Console.Write(i + " ");
}

输出结果为：11 12 22 25 64

以上便是冒泡排序、插入排序、选择排序的详细介绍和代码示例。在实际应用中，可以根据具体场景选择不同的排序算法来提高效率和准确性。