选择排序

发表于 | 分类于 |
字数统计: 268 字 | 阅读时长 ≈ 1 分钟

选择排序是一种简单直观的排序算法，无论什么数据进去，时间复杂都都是O(n^2^)。

算法步骤

  1. 在未排序序列中找到最小（大）元素，存放在排序序列的起始位置；
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
  3. 重复第二步，直到所有元素均排序完成；

动图演示

selectionSort

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 方法模版，适配int、float类型数据
template <typename T>
void selectionSort(T arr[], size_t len) {
    for (int i = 0; i < len; i++) {
        int min_index = i;
        for (int j = i; j < len; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            arr[i] = arr[i] ^ arr[min_index];
            arr[min_index] = arr[i] ^ arr[min_index];
            arr[i] = arr[i] ^ arr[min_index];
        }
    }
}
int main(int argc, const char * argv[]) {
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
    int len = (int) sizeof(arr) / sizeof(*arr);
    selectionSort(arr, len);
    for (int i = 0; i < len; i++) {
        std::cout<< "arr[" << i << "] = " << arr[i] << std::endl;
    }
    return 0;
}