选择排序详解

选择排序详解

1.核心思想

将序列分为已排序的和未排序的区间，每一轮从未排序的区间中找到最小值并与未排序区间的第一个元素交换，逐步扩大已排序的区间

步骤

• 每一轮便利未排序的部分，找到最小值所对应的下标并作标记
• 交换最小值和未排序部分的第一个元素
• 重复上述步骤

2.代码实现

voidchoice(int*arr,intsz){intindex,temp;for(intk=0;k<sz-1;k++){index=k;for(inti=k+1;i<sz;i++){if(arr[i]<arr[index]){index=i;}}temp=arr[index];arr[index]=arr[k];arr[k]=temp;}}intmain(){intarr[]={2,3,4,5,6,1};intsz=sizeof(arr)/sizeof(arr[0]);choice(arr,sz);for(inti=0;i<sz;i++){printf("%-2d",arr[i]);}return0;}

3. 步骤拆解

• 要排序的数组是{ 2,3,4,5,6,1 }
• 通过sz = sizeof(arr) / sizeof(arr[0]);计算出要排序的元素个数，那么一共排序sz-1次即可
• 默认未排序部分的最小值为未排序部分的首元素index = k，通过循环对比找到真正的最小值，出内层循环的时候index即为未排序部分最小值所对应的下标
• 将未排序部分的最小值和第一个元素交换，第一轮是将1和2进行交换
• 交换完成后k+1，重复上述步骤

特性分析

1. 时间复杂度：最好、最坏、平均时间复杂度均为O(n^2)，因为无论数组是否已有序，都需要完成n-1轮的比较。

2. 空间复杂度：O(1)，仅使用了临时变量temp等，属于原地排序。

3. 稳定性：不稳定排序。例如数组[2, 1, 2]，第一轮会将第一个2和1交换，导致两个2的相对位置改变。

4. 适用场景：数据量较小的场景，因为交换次数少（每轮最多1次交换），比冒泡排序更高效。