选择排序

复杂度分析

在最好/最坏的情况下，需要遍历 $n - 1$ 次，共进行 $n(n-1)/2$ 次比较。遍历/比较的时间复杂度是 $O(n^2)$。

选择排序是冒泡排序的改进。冒泡排序每一次比较出更大/更小值时都需要进行一次数据交换，但是选择排序只在遍历结束时进行一次数据交换，因此更快。

选择排序不是稳定排序。在排序的过程中，大小相等的两个元素的相对位置有可能发生改变。

实现

Rust

  1. fn select_sort<T>(nums: &mut [T])
  2. where
  3.     T: std::cmp::PartialOrd + Clone + Copy,
  4. {
  5.     for i in 0..(nums.len() - 1) {
  6.         let mut m = nums[i];
  7.         let mut k = i;
  8.         for j in (i + 1)..nums.len() {
  9.             if nums[j] < m {
  10.                 m = nums[j];
  11.                 k = j;
  12.             }
  13.         }
  14.         nums.swap(i, k);
  15.     }
  16. }

C++

  1. template<typename T>
  2. void selectSort(T nums[], int size) {
  3.     for (int i = 0; i < size - 1; i++) {
  4.         int k = i;
  5.         for (int j = i; j < size; j++) {
  6.             if (nums[j] < nums[k])
  7.                 k = j;
  8.         }
  9.         std::swap(nums[i], nums[k]);
  10.     }
  11. }