c语言排序法

1.冒泡法

基本思想

冒泡排序就像水中的气泡一样，较大的元素会慢慢”浮”到数组的顶端（右侧），而较小的元素会”沉”到底部（左侧）。

算法步骤

核心原理

• 比较相邻的两个元素
• 如果顺序错误（前一个比后一个大），就交换它们
• 每一轮都会将当前最大的元素”冒泡”到它应该在的位置

代码实现

#include<stdio.h>
int main()
{
    int a[100];      // 定义数组，最多存储100个整数
    int t, n, i, j;  // 定义变量：t用于交换临时存储，n为元素个数，i,j为循环计数器
    
    // 输入数据
    scanf("%d", &n);        // 输入要排序的数字个数
    for(i = 0; i < n; i++)  // 循环读入n个数字到数组中
        scanf("%d", &a[i]);
    
    /**************************************************
     * 冒泡排序核心算法开始
     * 原理：相邻元素两两比较，较大的元素向后"冒泡"
     **************************************************/
    for(i = 0; i < n-1; i++)  // 外层循环：控制排序轮数，n个元素需要n-1轮
    {
        /**************************************************
         * 第i轮排序说明：
         * - 每完成一轮，当前最大的元素就会"冒泡"到正确位置
         * - 经过i轮后，最后i个元素已经有序，不需要再比较
         * - 所以内层循环次数逐轮减少：n-i-1
         **************************************************/
        for(j = 0; j < n-i-1; j++)  // 内层循环：比较相邻元素，范围逐渐缩小
        {
            /**************************************************
             * 相邻元素比较：
             * - 如果前一个元素大于后一个元素，说明顺序错误
             * - 需要进行交换，让较大的元素向后移动
             **************************************************/
            if(a[j] > a[j+1])  // 比较相邻的两个元素
            {
                // 交换两个元素的位置（三变量交换法）
                t = a[j];       // 临时保存前一个元素
                a[j] = a[j+1];  // 将后一个元素移到前面
                a[j+1] = t;     // 将临时保存的元素移到后面
                
                /**************************************************
                 * 交换效果示例（假设a[j]=5, a[j+1]=3）：
                 * 交换前：[..., 5, 3, ...]
                 * 交换后：[..., 3, 5, ...]
                 * 较大的5向后移动了一位
                 **************************************************/
            }
        }
        
        /**************************************************
         * 第i轮排序完成后的效果：
         * - 第0轮：最大的元素"冒泡"到最后一个位置a[n-1]
         * - 第1轮：第二大的元素"冒泡"到倒数第二个位置a[n-2]
         * - 第i轮：第i+1大的元素"冒泡"到a[n-i-1]位置
         **************************************************/
    }
    // 冒泡排序核心算法结束
    
    // 输出排序结果
    for(i = 0; i < n; i++)  // 循环输出排序后的数组
        printf("%d ", a[i]);
    
    return 0;
}

1.循环条件为什么是 n-i-1？

for(j = 0; j < n-i-1; j++)

• 因为每完成一轮，最大的元素就已经在正确位置
• 下一轮就不需要再比较已经排好的元素
• 所以比较次数逐轮减少

原理图解

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

第0轮排序 (i=0)：

初始: [5, 3, 8, 4, 2]
比较过程：
j=0: 5>3? 是 → 交换 → [3, 5, 8, 4, 2]
j=1: 5>8? 否 → 不变 → [3, 5, 8, 4, 2]  
j=2: 8>4? 是 → 交换 → [3, 5, 4, 8, 2]
j=3: 8>2? 是 → 交换 → [3, 5, 4, 2, 8] ← 最大的8已到位

第1轮排序 (i=1)：

当前: [3, 5, 4, 2, 8] (8已排好)
比较过程：
j=0: 3>5? 否 → 不变 → [3, 5, 4, 2, 8]
j=1: 5>4? 是 → 交换 → [3, 4, 5, 2, 8]
j=2: 5>2? 是 → 交换 → [3, 4, 2, 5, 8] ← 第二大的5已到位

第2轮排序 (i=2)：

当前: [3, 4, 2, 5, 8] (5,8已排好)
比较过程：
j=0: 3>4? 否 → 不变 → [3, 4, 2, 5, 8]
j=1: 4>2? 是 → 交换 → [3, 2, 4, 5, 8] ← 第三大的4已到位

第3轮排序 (i=3)：

当前: [3, 2, 4, 5, 8] (4,5,8已排好)
比较过程：
j=0: 3>2? 是 → 交换 → [2, 3, 4, 5, 8] ← 全部排序完成

总结

冒泡排序的优点：

• 简单易懂，代码实现容易
• 空间复杂度低
• 稳定排序（相等元素的相对位置不变）

缺点：

• 效率较低，不适合大量数据

2.选择法

基本思路

选择排序的核心思想是：每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

算法步骤

• 在未排序序列中找到最小元素
• 将其存放到排序序列的起始位置
• 从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾
• 重复直到所有元素均排序完毕

代码实现

#include<stdio.h>

// 选择排序函数
void sort(int x[], int n)  // x[]: 待排序数组, n: 数组元素个数
{
    int i, j, t;          // 定义循环变量和临时交换变量
    
    /**************************************************
     * 选择排序核心算法开始
     * 原理：每轮选择未排序部分的最小元素，放到已排序部分末尾
     **************************************************/
    for(i = 0; i < n-1; i++)  // 外层循环：从第一个元素到倒数第二个元素
    {
        /**************************************************
         * 第i轮排序说明：
         * - 前i个元素已经排好序
         * - 现在要从第i个位置开始寻找剩余元素中的最小值
         **************************************************/
        int min = i;  // 初始化最小元素索引为当前位置i
        
        /**************************************************
         * 第一步：在未排序部分寻找最小元素
         * 内层循环范围：从i+1到数组末尾(n-1)
         * 目的：找到未排序部分中最小元素的位置
         **************************************************/
        for(j = i+1; j < n; j++)  // 遍历未排序部分的所有元素
        {
            /**************************************************
             * 比较当前元素与已知最小元素
             * 如果找到更小的元素，更新最小元素索引
             **************************************************/
            if(x[j] < x[min])  // 发现比当前最小值更小的元素
            {
                min = j;  // 更新最小元素的位置
            }
        }  // 内层循环结束，此时min指向未排序部分的最小元素
        
        /**************************************************
         * 第二步：将找到的最小元素交换到当前位置i
         * 注意：只有找到的最小元素不在当前位置时才需要交换
         **************************************************/
        if(min != i)  // 如果最小元素不在当前位置
        {    
            // 三变量交换法：交换当前元素与最小元素
            t = x[i];        // 临时保存当前位置的元素
            x[i] = x[min];   // 将最小元素放到当前位置
            x[min] = t;      // 将原当前位置元素放到最小元素的位置
            
            /**************************************************
             * 交换效果示例（假设i=0, min=4, x=[5,3,8,4,2]）：
             * 交换前：[5, 3, 8, 4, 2]
             * 交换后：[2, 3, 8, 4, 5]
             * 最小元素2被放到了最前面，完成第0轮排序
             **************************************************/
        }
        
        /**************************************************
         * 第i轮排序完成后的效果：
         * - 第0轮：最小元素移动到x[0]位置
         * - 第1轮：第二小元素移动到x[1]位置  
         * - 第i轮：第i+1小的元素移动到x[i]位置
         * 前i+1个元素已经有序
         **************************************************/
    }
    // 选择排序完成
}

int main()
{
    int n, i;           // n: 元素个数, i: 循环计数器
    int x[100];         // 定义数组，最多存储100个整数
    
    // 输入数据部分
    scanf("%d", &n);        // 输入要排序的数字个数
    for(i = 0; i < n; i++)  // 循环读入n个数字到数组中
        scanf("%d", &x[i]);
    
    // 调用选择排序函数对数组进行排序
    sort(x, n);
    
    // 输出排序结果
    for(i = 0; i < n; i++)  // 循环输出排序后的数组元素
        printf("%d ", x[i]);
    
    return 0;
}

原理图解

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

第0轮排序 (i=0)

初始: [5, 3, 8, 4, 2]
min = 0 (假设5是最小值)

比较过程：
j=1: x[1]=3 < x[0]=5? ✓ → min=1
j=2: x[2]=8 < x[1]=3? ✗ → min=1  
j=3: x[3]=4 < x[1]=3? ✗ → min=1
j=4: x[4]=2 < x[1]=3? ✓ → min=4

找到最小值：x[4]=2
交换 x[0] 和 x[4]：
[2, 3, 8, 4, 5]
↑
已排序

第1轮排序 (i=1)

当前: [2, 3, 8, 4, 5]
min = 1 (假设3是最小值)

比较过程：
j=2: x[2]=8 < x[1]=3? ✗ → min=1
j=3: x[3]=4 < x[1]=3? ✗ → min=1
j=4: x[4]=5 < x[1]=3? ✗ → min=1

最小值已在正确位置，无需交换：
[2, 3, 8, 4, 5]
    ↑
   已排序

第2轮排序 (i=2)

当前: [2, 3, 8, 4, 5]
min = 2 (假设8是最小值)

比较过程：
j=3: x[3]=4 < x[2]=8? ✓ → min=3
j=4: x[4]=5 < x[3]=4? ✗ → min=3

找到最小值：x[3]=4
交换 x[2] 和 x[3]：
[2, 3, 4, 8, 5]
       ↑
       已排序

第3轮排序 (i=3)

当前: [2, 3, 4, 8, 5]
min = 3 (假设8是最小值)

比较过程：
j=4: x[4]=5 < x[3]=8? ✓ → min=4

找到最小值：x[4]=5
交换 x[3] 和 x[4]：
[2, 3, 4, 5, 8]
          ↑
         已排序

最终结果

[2, 3, 4, 5, 8]
 全部有序

总结

选择法排序的优点：

• 交换次数少：每轮最多一次交换
• 简单直观：算法逻辑清晰明确
• 性能稳定：无论输入数据如何，比较次数固定

缺点：

• 不稳定排序：可能改变相等元素的相对顺序
• 适应性差：无论输入如何都要完成所有比较