选择排序的概念

选择排序（Selection Sort）是一种基于比较的简单排序算法，其核心思想是通过反复查找未排序部分的最小（或最大）元素，将其与未排序部分的起始位置交换，逐步构建有序序列。

举例分析

对 3 1 9 6 4 进行降序排列

大的靠前

选择排序的核心思路

选择排序是一种简单直观的排序算法，其核心思想可用以下步骤概括：

1. ​分区划分​

   • 将数组分为 ​已排序区​（左侧）和 ​未排序区​（右侧）
   • 初始时：已排序区为空（[ ]），未排序区为完整数组（[a0, a1, ..., an]）

2. ​查找极值​

   • 每轮扫描未排序区，查找最小（升序）或最大（降序）元素
   • 记录该极值元素的索引位置

3. ​元素交换​

   • 将极值元素与未排序区首个元素交换位置
   • 此时：被交换元素加入已排序区末尾​

4. ​重复缩减​

   • 缩小未排序区范围（右边界左移）
   • 重复上述过程，直至未排序区为空

代码演示

  正确代码

#define _CRT_SECURE_NO_WARNINGS  // 禁用Visual Studio的安全警告
#define N 10                     // 定义数组长度常量
#include<stdio.h>                // 标准输入输出库

int main()
{
    // 初始化待排序数组（共10个元素）
    int a[N] = { 1,6,4,8,3,2,9,10,7,5 };
    int i = 0;  // 外层循环计数器

    // 外层循环：控制排序轮数（只需N-1轮）
    // 因为我们排好前面的数字时，最后一个数字也自然排好了
    for (i = 0; i < N-1; i++)
    {
        int max = i;  // 假设当前起始位置i是最大值位置
        int j = 0;    // 内层循环计数器

        // 内层循环：在未排序部分[i+1, N-1]中查找最大值
        // 如果初始为 j=i，答案是不变的，只是会多进行一次自己与自己的比较
        for (j = i +1; j < N; j++)
        {
            // 若发现更大值则更新最大值位置
            if (a[j] > a[max])
            {
                max = j;  // 记录新最大值的位置
            }
        }
        // 你不检查交换也可以，只是会出现自己与自己交换，多此一举
        // 检查是否需要交换
        if (max != i)  // 若最大值不在起始位置
        {
            // 交换当前位置i与最大值位置max的元素
            int tmp = a[i];     // 临时存储当前元素
            a[i] = a[max];      // 将最大值移到当前位置
            a[max] = tmp;       // 将原值放入原最大值位置
        }
    }

    // 可选：添加打印结果代码（当前未启用）
    /*
    printf("降序排序结果: ");
    for (int k = 0; k < N; k++) {
        printf("%d ", a[k]);
    }
    */
    return 0;
}

错误代码

#define N 10
#include<stdio.h>

//错误的代码1

int main()
{
	
	int a[N] = { 1,6,4,8,3,2,9,10,7,5 };

	int i = 0;

	int max = 0;

	for (i = 0; i < N-1 ; i++)
	{
		int j = i+1;
		for (j = i+1; j < N; j++)
		{
			if (a[max] < a[j])
			{
				max = j;
			}
		}

		int tmp = a[i];
		a[i] = a[max];
		a[max] = tmp;
	}

	return 0;
}

还是和之前一样，用外层循环来控制排序轮数，用内层循环在未排序部分寻找最大值

不同点在于，这个代码的max初始化在循环外，只有开始时初始化过一次

可是，max只是一个工具，用它来记录我们找到的最大值，刚开始给max假设一个值

后面再遇到更大的值，max也会更新，找到的最大值该是多少就是多少

那为什么这样写有问题呢？

代码运行：

在排序前输出了一次，排序后又输出一次

发现，结果竟然是正确的，其实这只是巧合正确

那么什么时候会出错？

int a[N] = { 10,6,4,8,3,2,9,1,7,5 };报错
int a[5]={3,2,5,1,4};报错
这个代码的max没有重置，每次都会继承上一次循环得到的max值
如果出现那种最大值就在i本身的位置时，max就会被错误保留
而我们的i++是写死的，每次都把最大值交换到，i++完的地方
 
如果使用 int a[N] = { 1,6,4,8,3,2,9,10,7,5 };  会巧合的得出正确结果

调试结果分析 

例子

int a[N] = { 10,6,4,8,3,2,9,1,7,5 };报错

初始化: 
    arr = [10,6,4,8,3,2,9,1,7,5]
    max = 0 (指向值10)

i = 0 (外层循环第一轮):
    内层循环 j=0到9:
        j=0: a[0]=10 > a[max]=10? 无变化
        j=1: a[1]=6 > a[0]=10? 无变化
        j=2: a[2]=4 > a[0]=10? 无变化
        j=3: a[3]=8 > a[0]=10? 无变化
        j=4: a[4]=3 > a[0]=10? 无变化
        j=5: a[5]=2 > a[0]=10? 无变化
        j=6: a[6]=9 > a[0]=10? 无变化
        j=7: a[7]=1 > a[0]=10? 无变化
        j=8: a[8]=7 > a[0]=10? 无变化
        j=9: a[9]=5 > a[0]=10? 无变化
    交换: a[0]↔a[0] (自身交换) → 数组不变

仍然为 {10,6,4,8,3,2,9,1,7,5} 

     max保持为0 (指向值10)

i = 1 (外层循环第二轮):
    max=0 (来自上一轮)
    内层循环 j=1到9:
        j=1: a[1]=6 > a[0]=10? 无变化
        j=2: a[2]=4 > a[0]=10? 无变化
        j=3: a[3]=8 > a[0]=10? 无变化
        j=4: a[4]=3 > a[0]=10? 无变化
        j=5: a[5]=2 > a[0]=10? 无变化
        j=6: a[6]=9 > a[0]=10? 无变化  
        j=7: a[7]=1 > a[0]=10? 无变化
        j=8: a[8]=7 > a[0]=10? 无变化
        j=9: a[9]=5 > a[0]=10? 无变化
    交换: a[1]↔a[0] 

arr变为[6,10,4,8,3,2,9,1,7,5]  // 错误交换

    max保持为0 (指向值6)

i = 2 (外层循环第三轮):
    max=0 (指向位置0的值6)
    内层循环 j=2到9:
        j=2: a[2]=4 > a[0]=6? 无变化
        j=3: a[3]=8 > a[0]=6 → max=3
        ...继续查找最大值
    交换后数组更乱...

为什么这时候会出错？

max只在刚开始初始化过一次，后面就再也没有对max重新假设最大值了

所以每一次的max的值，都会继承上一次循环得到的max值

如果出现那种最大值就在i本身的位置时，max就会被错误保留

max还停留在已排序区，但是i++已经来到了未排序区的第一个元素

把排好的元素交换到，未排序区，肯定是不行的

而我们的i++是写死的，每次都把最大值交换到，i++完的地方

或者再举一个更简单的例子：

例子

int a[5]={3,2,5,1,4};报错

初始数组：[3, 2, 5, 1, 4]

第1轮（i=0）：

• max初始化为0（指向a[0]=3）
• 遍历j=0→4：
  • j=2时：a[2]=5 > a[0]=3 → 更新max=2（找到最大值5）
• 交换a[0]和a[2] → 数组更新为[5, 2, 3, 1, 4] ✅ 最大值5排序完成

第2轮（i=1）：

• max未重置，仍为2（指向a[2]=3）
• 遍历j=1→4（未排序部分：[2, 3, 1, 4]）：
  • j=4时：a[4]=4 > a[2]=3 → 更新max=4（找到次大值4）
• 交换a[1]和a[4] → 数组更新为[5, 4, 3, 1, 2] ✅ 次大值4排序完成

第3轮（i=2）：

• max未重置，仍为4（指向a[4]=2）
• 遍历j=2→4（未排序部分：[3, 1, 2]）：
  • j=2时：a[2]=3 > a[4]=2 → 更新max=2（找到3）
• 交换a[2]和a[2]（无变化）→ 数组保持[5, 4, 3, 1, 2] ⚠️ 错误：max未正确更新，第三大值处理失败

第4轮（i=3）：

• max未重置，仍为2（指向a[2]=3）
• 遍历j=3→4（未排序部分：[1, 2]）：
  • j=3时：a[3]=1 < a[2]=3 → 不更新max
  • j=4时：a[4]=2 < 3 → 不更新max
• 交换a[3]和a[2]（max=2）→ 数组变为[5, 4, 1, 3, 2] ❌ 排序错误

预期结果：[5, 4, 3, 2, 1] 实际结果：[5, 4, 1, 3, 2]

现在知道为什么错了吧

总结：

在选择排序中max初始的时候是假设一个值，但是我们假设的这个max值应该存在未排序区中

也就是在循环内部直接写int max=i;

也就是

#define N 10
#include<stdio.h>
int main()
{
	int a[N] = { 1,6,4,8,3,2,9,10,7,5 };
	
	int i = 0;

	for (i = 0; i < N-1; i++)
	{
		int max = i;

		int j = 0;
		for (j = i +1; j < N; j++)
		{
			if (a[j] > a[max])
			{
				max = j;
			}
		}

		if (max != i)
		{
			int tmp = a[i];
			a[i] = a[max];
			a[max] = tmp;
		}

	}

	return 0;
}

                                                                                        

                                                                                                                         -----------豪哥

                                                                                                                            2025.8.2  台风天

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/ambition20242/article/details/149860418