选择排序 - 学习记录

选择排序#

第一步：在数组中找到最大值，并记录最大值下标maxIndex，并将最大值与最后一个值交换，即：

1
swap(a[maxIndex], a[n - 1]);

第二步：在剩下的待排序数列中重新找到最大值，重复第一步 swap(a[maxIndex], a[n - 2]); 循环操作直至数列排序完成。

C++代码如下：

1
#include<stdio.h>
2
#include<iostream>
3
#include<vector>
4
using namespace std;
5

6
void SelectSort(vector<int> &vec) {//选择排序
7
  int maxIndex = 0;
8
  for (int i = vec.size() - 1; i >= 0; --i) {
9
    maxIndex = 0;
10
    for (int j = 0; j <= i; ++j) {//注意是j<=i，因为是找数组中最大值，包括最后一个数
11
      if (vec[maxIndex] < vec[j]) {
12
        maxIndex = j;
13
      }
14
    }
15
    swap(vec[maxIndex], vec[i]);
16
  }
17
}
18

19
int main() {
20
  vector<int> a = {5, 2, 3, 1, 4};
21
  SelectSort(a);
22
  for (int i = 0; i < 5; ++i) {
23
    cout << a[i] << " ";
24
  }
25
  return 0;
26
}