排序与搜索——选择排序

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序分析

排序过程：

我们把比较得到的最小的数字放在队首，首先把游标放在下标为0的元素这，然后依次与后面的其他数字作比较，比较到下标为3的时候，发现17比54大，那么最小值的下标0余3进行交换，但此时比较不会停止而是拿着下标的3的数字接着同剩下的数字进行比较，最后确定下标为3的是最小的，然后下标0和下标3的元素互换，同理，其他的也是如此。
代码实现：

def select_sort(li):
    n = len(li)
    for j in range(0,n-1):
        min_index = j
        for i in range(j*+1,n):
            if li[i]<li[min_index]:
                min_index = i
        li[j],li[min_index] = li[min_index],li[j]

if __name__ == '__main__':
    ali = [12,23,11,33,4,55,12,44,52,21]
    print(ali)
    select_sort(ali)
    print(ali)

时间复杂度

最优时间复杂度：O(n^2)
最坏时间复杂度：O(n^2)
稳定性：不稳定（考虑升序每次选择最大的情况）

稳定性的问题主要是升序问题：

元祖仅做标识

第一个（26,2）是不是要依次和后面的数据比较，一直比较到（26,1）发现俩一样大，但程序还是选择（26，2）大，然后接着同后面的数据比较，把（26，2）放到队尾了，然后接着遍历，最后会把（26,1）放到次尾部，故不稳定。