直接选择排序

直接选择排序（Selection Sort）特性总结

1. 理解难度：算法思想非常直观、易于理解。

   • 每一轮从未排序部分中选出最小（或最大）元素，放到已排序部分的末尾。
   • 但由于效率较低，在实际工程中很少使用。

2. 时间复杂度：

   • **最好 / 平均 / 最坏情况均为 $ O(n^2) $ **
   • 原因：无论输入数据如何，都需要进行约 $ \frac{n(n-1)}{2} $ 次比较。

3. 空间复杂度：

   • ** O(1) **（原地排序）
   • 仅使用常数个额外变量，无需额外存储空间。

voidSelectSort(int*arr,intn){intbegin=0;intend=n-1;while(begin<end){intmax=end,min=begin;//让max和min跟随begin和end更新，避免因为没有发生交换等情况最后导致错误交换值。for(inti=begin;i<=end;i++){if(arr[i]>arr[max]){max=i;//选择排序只交换当前值与最值，如果此处直接交换，会造成多次交换，破坏原有的序列。}if(arr[i]<arr[min]){min=i;}}Swap(&arr[max],&arr[end]);if(min==end)//先选择最大值时如果最小值在序列尾，会造成交换最小值前，最小值的下标发生变化，此时需要变更下标,若选择先排最小值，同理要防止最大值出现在begin位置时造成的下标偏移{min=max;}Swap(&arr[min],&arr[begin]);begin++;end--;}}

该代码中为直接选择排序的优化方法——双向选择排序，同时对首端和尾端选择，可以提升选择排序效率