企业官网建设流程全解析

简单选择排序的核心逻辑是：在每趟排序中从未排序的部分选出最小（或最大）元素，将其与该部分的第一个元素交换位置，从而逐步构建有序序列。通过 n-1 趟选择，完成整个数组的排序。

voidSelectSort(intdata[],intn){inti,j,k,tmp;for(i=0;i<n-1;i++){k=i;// 假设第i个位置就是最小值的位置for(j=i+1;j<n;j++)/* 找出最小关键字的下标 */if(data[j]<data[k])k=j;if(k!=i){// 若最小值不在第i位，则交换tmp=data[i];data[i]=data[k];data[k]=tmp;}}}

性能分析如下：

• 比较次数：固定为n(n−1)2\frac{n(n-1)}{2}2n(n−1)​，时间复杂度为O(n2)O(n^2)O(n2)，不随输入数据分布变化。
• 移动次数：
  • 最好情况（已有序）：0 次；
  • 最坏情况（逆序）：每趟都发生交换，共3(n−1)3(n-1)3(n−1)次移动（每次交换3次赋值）。
• 稳定性：不稳定。例如，当有相同关键字的元素时，交换可能导致它们相对顺序改变。
• 空间复杂度：O(1)O(1)O(1)，仅使用常量额外空间。
• 简单选择排序是不稳定的，原因在于它在每趟选择中将最小元素与未排序部分的首元素进行直接交换，而不管这两个元素是否具有相同的值。这种交换可能改变相同关键字元素之间的相对顺序，从而破坏稳定性。

🔍 举例说明：

假设有一个待排序的数组，其中包含两个相同的元素5a和5b（下标 a、b 用于区分先后顺序）：

原始序列：[5a, 2, 5b, 1]

我们希望排序后相同元素5a和5b的相对位置保持不变（即5a仍在5b前面），才能称为稳定排序。

执行选择排序过程：

• 第1趟：从[5a, 2, 5b, 1]中找最小值 →1（下标3）

• 将1与第一个元素5a交换：

  结果：[1, 2, 5b, 5a]

此时，原本在后面的5a被换到了最后，而5b却排在了前面。

• 最终结果中：5b出现在5a前面，改变了相同关键字元素的相对顺序。

👉 因此，该算法是不稳定的。

✅ 总结

尽管选择排序逻辑清晰、空间效率高，但由于其通过“交换”而非“插入”来调整位置，容易打乱相等元素的原始次序，所以不具备稳定性。