O(n^2)时间复杂度的排序算法——选择排序

选择排序的想法

通俗版

又到了一年中秋佳节，满街的柚子引得老王直流口水。然而从街头到街尾这么多的水果摊，哪个摊位的柚子性价比最高呢？老王不知道，但是他想到了一个法子能够选出性价比最高的水果摊。他先假定街头的第一个水果摊的柚子性价比最高，然后他从街头到结尾，挨个水果摊走访一遍，每次遇到性价比比之前认定的性价比高，就拿笔记下这个水果摊的位置，并以把水果摊作为比对的对象，继续走访。等他走访完街尾最后一个水果摊时，从他的本子上就知道街上哪个位置的水果摊性价比最高。这时候遇到了老李，老李说要是你能给我把这些水果摊柚子的性价比给我从高到低排好，我给你250. 老王这可乐了，这不简单。刚才我已经把性价比最好的找出来了，现在我再按照之前的套路来不就能每次都从剩下的没有水果摊中找到性价比最好的嘛。于是老王很快就给老李一个按照性价高低排好的水果摊。
这就是选择排序中的选择，每次选择一个标准与下一个比较，最后返回得到最好的那个。可以从下面的代码好好体会老王的每一个动作。

专业版

这个博主给出了这样的描述：

选择排序将数据分为有序区和无序区，从无序区选一个最小的元素直接放到有序区的最后。
数组为a[0,…,n-1]:
1.初始时，数组全为无序区为a[0,…,n-1]。令i=0
2.在无序区a[i+1,…,n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0,…,i+1]就形成了一个有序区。
3.i++并重复第二步直到i==n-1, 排序完成.

C++代码：

void Selectsort(int a[], int n)
{
    int i, j, nMinIndex;
    for (i = 0; i < n; i++)
    {
        nMinIndex = i; //设定最小元素的位置
        for (j = i + 1; j < n; j++)
            if (a[j] < a[nMinIndex])
                nMinIndex = j; 
        Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头
    }
}
inline void Swap(int &a, int &b)
{
    if（a != b){
        int c = a;
        a = b;
        b = c;
    }
}

Python实现：

def selectSort(s):
    l = len(s)
    for i in range(l):
        min_ind = i
        for j in range(i+1,l):
            if s[min_ind] > s[j]:
                min_ind = j
        if i != min_ind:
            s[min_ind], s[i] = s[i], s[min_ind]

在线测试：
https://goo.gl/9i5ct4

import random
seq = [random.randint(0,20) for _ in range(20)]
selectSort(seq)

排序的过程：