选择排序

选择排序SelectionSort

介绍：

学习它之前首先要知道它的两个很鲜明的特点。

1. 运行时间和输入无关

为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供任何实质性帮助的信息。因此使用这种排序的我们会惊讶的发现，一个已经有序的数组或者数组内元素全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长！而其他算法会更善于利用输入的初始状态，选择排序则不然。

2. 数据移动是最少的

选择排序的交换次数和数组大小关系是线性关系，选择排序无疑是最简单直观的排序。看下面的原理时可以很容易明白这一点。

步骤：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

源代码：(python实现)

def select_sort(ary):

    n = len(ary)

    for i in range(0,n):

        min = i                            #最小元素下标标记

        for j in range(i+1,n):

            if ary[j] < ary[min] :

                min = j                    #找到最小值的下标

        ary[min],ary[i] = ary[i],ary[min]  #交换两者

    return ary