Skip to main content

一、排序算法

高考考点​

排序算法：冒泡排序法、选择排序法、插入排序法

一、排序是什么？​

排序就是把一堆乱序的数字，按升序或降序排好。本文中涉及的案例默认升序排序。

比如：[5, 2, 8, 1, 9] → 排序后 → [1, 2, 5, 8, 9]

二、冒泡排序（Bubble Sort）​

1.工作原理​

冒泡排序通过反复比较相邻元素，将最大的元素一步步"冒泡"到数组末尾，从而实现排序。

初始：[5, 2, 8, 1, 9]
第1轮：比较相邻的两个数，大的往后移
[2, 5, 8, 1, 9]  ← 5和2比较，交换
[2, 5, 1, 8, 9]  ← 8和1比较，交换
[2, 5, 1, 8, 9]  ← 8和9比较，不交换
最大的9已经"冒"到最后

第2轮：[2, 5, 1, 8, 9]
[2, 1, 5, 8, 9]  ← 5和1比较，交换
[2, 1, 5, 8, 9]  ← 5和8比较，不交换
次大的8到倒数第二

第3轮：[2, 1, 5, 8, 9]
[1, 2, 5, 8, 9]  ← 2和1比较，交换
继续...

最终：[1, 2, 5, 8, 9]

2.代码实现​

using System;

class Program
{
    static void Main()
    {
        int[] arr = {5, 2, 8, 1, 9};
        BubbleSort(arr);
        Console.WriteLine(string.Join(",", arr)); // 输出：1,2,5,8,9
    }
    
    static public int[] BubbleSort(int[] arr)
    {
        // 防御性检查：避免传入空数组/长度为1的数组时报错
        if (arr == null || arr.Length <= 1)
        {
            return arr;
        }
        
        for( int i = 0; i < arr.Length - 1; i++ )
        {
            // 内层循环：每轮冒泡后，最后i个元素已排好序，无需再比较
            for ( int j = 0; j < arr.Length - 1 - i; j++ )
            {
                if( arr[j] > arr[j+1])
                {
                    // 修复：正确的交换逻辑
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp; // 关键修正：赋值temp而非arr[j]
                } 
            }
        }
        return arr;
    }
}

3.输出结果​

排序前：5, 2, 8, 1, 9

第1轮开始：
  交换 5 和 2 → 2, 5, 8, 1, 9
  交换 8 和 1 → 2, 5, 1, 8, 9

第2轮开始：
  交换 5 和 1 → 2, 1, 5, 8, 9

第3轮开始：
  交换 2 和 1 → 1, 2, 5, 8, 9

第4轮开始：

排序后：1, 2, 5, 8, 9

三、选择排序（Selection Sort）​

1.选择排序是什么​

每一轮只找最小的，放到当前最前面，重复到有序。

2.自然语言描述​

以数组 [5, 3, 8, 4, 2] 为例：

初始状态：已排序区间为空，未排序区间为整个数组 → [] [5, 3, 8, 4, 2]

第 1 轮：
遍历未排序区间 [5, 3, 8, 4, 2]，找到最小值 2，记录其索引 4。
将最小值 2 与未排序区间的第一个元素 5 交换位置。
结果：已排序区间 [2]，未排序区间 [3, 8, 4, 5] → [2] [3, 8, 4, 5]

第 2 轮：
遍历未排序区间 [3, 8, 4, 5]，找到最小值 3，记录其索引 0（未排序区间内的索引）。
最小值 3 就是未排序区间的第一个元素，无需交换。
结果：已排序区间 [2, 3]，未排序区间 [8, 4, 5] → [2, 3] [8, 4, 5]

第 3 轮：
遍历未排序区间 [8, 4, 5]，找到最小值 4，记录其索引 1（未排序区间内的索引）。
将最小值 4 与未排序区间的第一个元素 8 交换位置。
结果：已排序区间 [2, 3, 4]，未排序区间 [8, 5] → [2, 3, 4] [8, 5]

第 4 轮：
遍历未排序区间 [8, 5]，找到最小值 5，记录其索引 1（未排序区间内的索引）。
将最小值 5 与未排序区间的第一个元素 8 交换位置。
结果：已排序区间 [2, 3, 4, 5]，未排序区间 [8] → [2, 3, 4, 5] [8]
结束：未排序区间只剩一个元素，默认有序，最终数组为 [2, 3, 4, 5, 8]。

3.代码实现​

using System;

class SelectionSortExample
{
    static void Main()
    {
        int[] numbers = { 5, 3, 8, 4, 2 };
        
        // 选择排序
        for (int i = 0; i < numbers.Length - 1; i++)  // 外层：当前位置
        {
            int minIndex = i;  // 假设当前位置是最小的
            
            // 在剩下的数中找真正的最小值
            for (int j = i + 1; j < numbers.Length; j++)
            {
                if (numbers[j] < numbers[minIndex])
                {
                    minIndex = j;
                }
            }
            
            // 如果找到的最小值不在当前位置，就交换
            if (minIndex != i)
            {
                int temp = numbers[i];
                numbers[i] = numbers[minIndex];
                numbers[minIndex] = temp;
            }
            else
            {
                Console.WriteLine($"  最小值 {numbers[minIndex]} 已在正确位置");
            }
        }
        
        Console.WriteLine("\n排序后：" + string.Join(", ", numbers));
    }
}

四、插入排序（Insertion Sort）​

1.工作原理​

选择排序可以类比整理扑克牌的场景：

  1. 想象手里已经有一些未排好序的牌
  2. 每抓到一张新牌，你会从后往前对比手里的牌，把新牌插入到一个合适的位置，让手里的牌始终保持有序。

2.自然语言描述​

以数组 [5, 3, 8, 4, 2] 为例

初始状态：已排序区间 [5]，未排序区间 [3, 8, 4, 2]

第 1 轮：
待插入元素：未排序区间第一个元素 3
从已排序区间末尾（元素 5）往前对比：3 < 5，将 5 后移一位，已排序区间变为 [5, 5]
已无更前面的元素，将 3 插入到最前面
结果：[3, 5] [8, 4, 2]

第 2 轮：
待插入元素：8
从已排序区间末尾（元素 5）往前对比：8 > 5，无需后移元素
直接将 8 插入到已排序区间末尾
结果：[3, 5, 8] [4, 2]

第 3 轮：
待插入元素：4
从已排序区间末尾（元素 8）往前对比：4 < 8，将 8 后移一位 → [3, 5, 8, 8]
继续往前对比：4 < 5，将 5 后移一位 → [3, 5, 5, 8]
继续往前对比：4 > 3，停止后移
将 4 插入到 3 和 5 之间
结果：[3, 4, 5, 8] [2]

第 4 轮：
待插入元素：2
从已排序区间末尾（元素 8）往前对比，依次将 8、5、4、3 后移一位 → [3, 3, 4, 5, 8]
已无更前面的元素，将 2 插入到最前面
结果：[2, 3, 4, 5, 8]（未排序区间为空，排序完成）

3.代码实现：​

using System;

class InsertionSortExample
{
    static void Main()
    {
        int[] arr = { 5, 3, 8, 4, 2 };
        
        // 数组长度
        int n = arr.Length;
        // 外层循环：遍历未排序区间（从索引1开始，索引0为初始已排序区间）
        for (int i = 1; i < n; i++)
        {
            // 步骤1：取出未排序区间的第一个元素（索引i）作为待插入元素
            int insertValue = arr[i];
            // 步骤2：定义已排序区间的末尾索引（初始为i-1，从后往前对比）
            int j = i - 1;

            // 内层循环：从后往前遍历已排序区间，找到待插入元素的合适位置
            // 条件：1. j >= 0（不越界） 2. arr[j] > insertValue（当前元素比待插入元素大，需要后移）
            while (j >= 0 && arr[j] > insertValue)
            {
                // 将当前元素后移一位，给待插入元素腾出空间
                arr[j + 1] = arr[j];
                // 索引往前移动，继续对比下一个元素
                j--;
            }

            // 步骤3：将待插入元素插入到找到的合适位置（j+1，因为循环结束后j多减了1）
            arr[j + 1] = insertValue;
        }
    }
}

运行结果

排序后的数组：2, 3, 4, 5, 8

4.算法评价​

  • 时间复杂度：
    • 最好情况：O(n)（数组已经有序，内层 while 循环无需执行，只需外层遍历一次）。
    • 最坏情况 / 平均情况：O(n²)（数组逆序，每个元素都需要遍历整个已排序区间）。
  • 空间复杂度：O(1)，属于「原地排序」，无需额外辅助数组，仅用少量临时变量，空间效率高。

五、三种排序评价对比（重要！）​

特性冒泡排序选择排序插入排序
思想相邻比较，大的往后每次选最小的放前面像插牌一样插入
时间复杂度O(n²)O(n²)O(n²)
空间复杂度O(1)O(1)O(1)
优点简单易懂交换次数少对部分有序数据快
缺点效率低不稳定数据量大时慢
适合场景教学、小数据数据量小数据基本有序

记住：这些基础排序算法虽然效率不高，但它们是理解更复杂算法的基础！

六、练习题​

练习题1：冒泡排序手动模拟​

题目：用手动模拟冒泡排序对数组 [6, 3, 9, 2, 7] 进行排序

要求：写出每一轮比较和交换的过程

答案：

初始：[6, 3, 9, 2, 7]

第1轮：
  比较6和3，交换 → [3, 6, 9, 2, 7]
  比较6和9，不交换
  比较9和2，交换 → [3, 6, 2, 9, 7]
  比较9和7，交换 → [3, 6, 2, 7, 9]

第2轮：
  比较3和6，不交换
  比较6和2，交换 → [3, 2, 6, 7, 9]
  比较6和7，不交换

第3轮：
  比较3和2，交换 → [2, 3, 6, 7, 9]

第4轮：
  比较2和3，不交换

结果：[2, 3, 6, 7, 9]

练习题2：选择排序C#代码填空​

题目：补全选择排序代码中的空白

void SelectionSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int minIndex = ______;  // 填空1
        
        for (int j = ______; j < array.Length; j++)  // 填空2
        {
            if (array[j] < array[minIndex])
            {
                minIndex = ______;  // 填空3
            }
        }
        
        if (minIndex != i)
        {
            // 交换
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

答案：

// 填空1：i
// 填空2：i + 1
// 填空3：j

练习题3：插入排序逻辑判断​

题目：对数组 [4, 1, 3, 2] 进行插入排序，回答以下问题：

  1. 处理第2个元素(1)时，需要向前比较几次？
  2. 处理第4个元素(2)时，它最终插入到什么位置？
  3. 整个排序过程中，总共进行了多少次元素移动？

答案：

处理过程：
初始：[4, 1, 3, 2]

第2个元素(1)：
  与4比较，4>1，4后移 → [4, 4, 3, 2]
  插入1到第1位 → [1, 4, 3, 2]   // 比较1次，移动1次

第3个元素(3)：
  与4比较，4>3，4后移 → [1, 4, 4, 2]
  与1比较，1<3，停止 → 插入3到第2位 → [1, 3, 4, 2]  // 比较2次，移动1次

第4个元素(2)：
  与4比较，4>2，4后移 → [1, 3, 4, 4]
  与3比较，3>2，3后移 → [1, 3, 3, 4]
  与1比较，1<2，停止 → 插入2到第2位 → [1, 2, 3, 4]  // 比较3次，移动2次

答案：
1. 比较1次
2. 插入到第2位（索引1）
3. 总共移动次数：1 + 1 + 2 = 4次

练习题4：理解冒泡排序过程​

题目：观察下面的冒泡排序过程，回答后面的问题

// 对数组 [7, 3, 9, 2, 5] 进行冒泡排序
// 请写出每一轮的结果

初始：[7, 3, 9, 2, 5]

第1轮（比较相邻，大的后移）：
  7和3比较 → 交换 → [3, 7, 9, 2, 5]
  7和9比较 → 不交换
  9和2比较 → 交换 → [3, 7, 2, 9, 5]
  9和5比较 → 交换 → [3, 7, 2, 5, 9]

第2轮：
  3和7比较 → 不交换
  7和2比较 → 交换 → [3, 2, 7, 5, 9]
  7和5比较 → 交换 → [3, 2, 5, 7, 9]
  （9已排好，不比较）

问题：
1. 第3轮开始时数组是什么？
2. 第3轮需要比较几次？
3. 总共需要多少轮才能完全排好？

答案：
1. 第3轮开始：[3, 2, 5, 7, 9]
2. 第3轮比较：2次（3和2，2和5）
3. 总共需要：4轮（n-1轮，n=5）

练习题5：手动执行选择排序​

题目：手动对数组 [8, 3, 6, 1, 4] 执行选择排序，写出每一步

要求：写出每一轮找到的最小值和交换过程

初始：[8, 3, 6, 1, 4]

第1轮：
  找最小值：从全部中找，最小值是1（位置3）
  交换：8和1交换 → [1, 3, 6, 8, 4]

第2轮：
  找最小值：从[3,6,8,4]中找，最小值是3（位置1）
  交换：3已在正确位置，不交换 → [1, 3, 6, 8, 4]

第3轮：
  找最小值：从[6,8,4]中找，最小值是4（位置4）
  交换：6和4交换 → [1, 3, 4, 8, 6]

第4轮：
  找最小值：从[8,6]中找，最小值是6（位置4）
  交换：8和6交换 → [1, 3, 4, 6, 8]

完成：[1, 3, 4, 6, 8]