一、算法简介

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

二、算法步骤

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

三、算法动态图

四、代码实现

void SelectionSort_1(std::vector<int> &arr)
{
    int min;
    for (int i = 0; i < arr.size() - 1; i++)
    {
        min = i;
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        if (i != min)
        {
            std::swap(arr[i], arr[min]);
        }
    }
}

python

def selectionSort(arr);
	for i in range(len(arr) - 1):
        minIndex = i
        for j in range(i + 1, len(arr));
        	if(arr[j] < arr[minIndex]):
                minIndex = j;
        if i != minIndex;
        	arr[i], arr[minIndex] = arr[minIndex],arr[i]
	return arr

java

public class SelectionSort implements IArraySort{
    
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
        for (int i = 0; i < arr.length - 1; i++) {
			int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[min]) {
					min = j;
                }
            }
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
    }
    return arr;
    
}

javascript

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, tmp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    return arr;
}

五、算法时间复杂度

从选择排序的过程来看，它最大的特点就是交换移动据次数相当少这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第 i趟排序需要进行 n-i 次关键字的比较，此时需要比较

∑

−

\sum_{i=1}^{n-1} n-i

$\sum_{i = 1}^{n - 1} n - i$ = n-1+n-2n+…+

(

−

)

\frac{n(n-1)}{2}

$\frac{n ( n - 1 )}{2}$ 。而对交换次教而，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1 次，基于最终的排序时间是比较与交换的次数总和因此，总的时间复杂度依然为 O（n ）。应该说，尽管与冒泡排序同为 O(n )，但简单选择排序的性能还是要略优于冒泡排序。