算法之选择排序

　　 概述：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序

分类	数据结构	时间复杂度	最优时间复杂度	平均时间复杂度	空间复杂度
选择排序	数组	О(n²)	О(n²)	О(n²)	总共О(n), 辅助空间 O(1)

代码范例

C语言

void selection_sort(int arr[], int len) {
    int i, j, min, temp;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++)
            if (arr[min] > arr[j])
                min = j;
        temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

Python

def selection_sort(L):
    N = len(L)
    exchanges_count = 0
    for i in range(N-1):
        min_index = i
        for j in range(i+1, N):
            if L[min_index] > L[j]:
                min_index = j
        if min_index != i:
            L[min_index], L[i] = L[i], L[min_index]
            exchanges_count += 1
        print('iteration #{}: {}'.format(i, L))
    print('Total {} swappings'.format(exchanges_count))
    return L

testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
print('Before selection sort: {}'.format(testlist))
print('After selection sort:  {}'.format(selection_sort(testlist)))

Java

public static void selection_sort(int[] arr) {
    int i, j, min, temp, len = arr.length;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++)
            if (arr[min] > arr[j])
                min = j;
        temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

JavaScript

Array.prototype.selection_sort = function() {
    var i, j, min;
    var temp;
    for (i = 0; i < this.length - 1; i++) {
        min = i;
        for (j = i + 1; j < this.length; j++)
            if (this[min] > this[j])
                min = j;
        temp = this[min];
        this[min] = this[i];
        this[i] = temp;
    }
};

PHP

function swap(&$x, &$y) {
    $t = $x;
    $x = $y;
    $y = $t;
}
function selection_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
    for ($i = 0; $i < count($arr) - 1; $i++) {
        $min = $i;
        for ($j = $i + 1; $j < count($arr); $j++)
            if ($arr[$min] > $arr[$j])
                $min = $j;
        swap($arr[$min], $arr[$i]);
    }
}

复杂度分析

选择排序的交换操作介于 0和 (n-1)次之间。选择排序的比较操作为 n(n-1)/2次之间。选择排序的赋值操作介于 0和 3(n-1)次之间。
比较次数 О(n²)，比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n * (n-1)/2。交换次数O(n)，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

参考：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F