【数据结构】直接选择排序详解！

1.直接选择排序

• 🐧 begin 有可能就是 maxi ，所以交换的时候，要及时更新 maxi
  

• 🍎 直接选择排序是不稳定的，例如： 9 [9] 5 [5]，排序后，因为直接选择排序是会交换数据的，排序后可能变成了 [5] 5 [9] 9

// 直接选择排序
// 时间复杂度： O(n^2)
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin; i <= end; i++){if (a[i] < a[mini])mini = i;if (a[i] > a[maxi])maxi = i;}Swap(&a[begin], &a[mini]);// 此时的 maxi 有可能已经改变if (begin == maxi)maxi = mini;Swap(&a[end], &a[maxi]);begin++, end--;}
}