选择排序_驱动网

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

选择排序

2023-03-28 13:08:45 来源：博客园

(资料图片)

欢迎关注fish的公众号：fish码农成长之旅

相信大家对扑克牌并不陌生，当我们在齐牌的时候是不是会按照大小顺序进行排列，选择排序的过程就跟扑克牌差不多一样的直观简单。其排序时间复杂度总是O(n^2)的。

算法步骤

把整个数组分为已经排序的部分和未排序的部分，初始已经排序的部分为0，未排序的部分为n(数组大小)

首先根据自己的需求在未排序数组中找到最小(大)的数放在已排序数组末端，已经排序好的大小加一，未排序数组大小减一，然后重复此步骤继续在未排序的数组中找最小(大)的数放在已排序的末端。

实例演示

总共6个数的排序，按照从小到大排序，原始数据为：3 38 5 1 9 4

可以看出，每一次排序一个数就是遍历出最小(大)的位置，然后跟已经排序好数组的末端那个数交换位置，当遍历n次之后整个数组排序完毕。

代码实现

template void selection_sort(std::vector &arrs) {  int n = arrs.size();  // 数组的大小  if (n <= 1) {         // 一个数的情况不需要排序    return;  }  for (int idx_i = 0; idx_i < n - 1;       ++idx_i) {  // 为什么 n - 1：最后只剩一个数，就不需要再比较了    int target_idx = idx_i;    for (int idx_j = idx_i + 1; idx_j < n; ++idx_j) {      // 三目运算， 取最小值的下标赋值给 target_idx      target_idx = arrs[idx_j] < arrs[target_idx] ? idx_j : target_idx;    }    std::swap(arrs[idx_i], arrs[target_idx]);  // 交换两个位置的数  }}

关键词：