排序算法二：选择排序

2018 年 3 月 3 日 20:57:55数据结构和算法评论514字数 600阅读 2 分 0 秒阅读模式

一、原理

选择排序（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] 替换

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 对换：

排序算法二：选择排序-图片1

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

排序算法二：选择排序-图片2

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

排序算法二：选择排序-图片3

执行完第三趟排序后，数组就已经有序了。但是对计算机而言却并不知情，它还会继续判断后面的 [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]);
        }
    }
}

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]

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]);
    }
}