一、原理

选择排序(Selection sort)是一种简单直观的排序算法,它的工作原理是:从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

选择排序无论在最坏或是最好的情况,时间复杂度都是O($n^2$)

排序逻辑:

for i in (i, n-1)
    min = data[i]
    for j in (j, n)
        如果min>data[j],标记当前位置,重新设置min,继续循环
    把最小的元素min和data[i]替换

图解

以序列[3, 1, 5, 4, 7]为例,执行第一趟排序时,找到的最小元素是1,把它放到最前面和3对换:

第二趟排序,未排序数组为[3, 5, 4, 7],此时数组内最小的元素是3,刚好就是当前数组最开头的位置,因此无需替换,继续下一趟排序。

第三趟排序,未排序数组为[5, 4, 7],此时数组内最小的元素是4,放到最前面和5对换:

执行完第三趟排序后,数组就已经有序了。但是对计算机而言却并不知情,它还会继续判断后面的[5, 7],但是刚好每次排序的时候,他们就处于应该在的位置。

二、代码实现

2.1 C++实现

template <typename T>
void select_sort(vector<T> &v) {
    size_t i, j;
    // 记录最小的下标
    T min_idx;

    if (v.size() < 2)
        return;

    // 只用执行n-1趟排序
    for (i = 0; i < v.size() - 1; i++) {
        min_idx = i;

        // 找到最小的下标
        for (j = i + 1; j < v.size(); j++) {
            if (v[j] < v[min_idx])
                min_idx = j;
        }

        // 替换最小的
        if (min_idx != i) {
            my_swap(v[i], v[min_idx]);
        }
    }
}

2.2 python实现

def select_sort(data):
    size = len(data)
    for i in range(size - 1):
        k = i
        for j in range(i + 1, size):
            if data[j] < data[k]:
                k = j
        if k != i:
            data[k], data[i] = data[i], data[k]

2.3 c语言实现

int select_sort(int* data, unsigned int len) {
    unsigned int i, j, min;

    for (i = 0; i < len - 2; i++) {
        min = i;
        for (j = i + 1; j < len - 2; j++) {
            if (data[j] < data[i])
                min = j;
        }
        if (min != i)
            swap(data[min], data[i]);
    }
}
最后修改:2020 年 02 月 07 日
喜欢就给我点赞吧