【码了么】python实现排序（二）-Python实现五大常用排序算法（选择排序）

智一面的面试题提供python的测试题

使用地址：http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9

二、选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为：选择排序

1.过程图解

2.算法思想

1. 设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素找到最小的元素，将它和第一个元素互换

2. 重复上述操作，我们找出第二小的元素和第二个位置的元素互换，以此类推找出剩余最小元素将它换到前面，即完成排序

3.代码实现

def selection_sort(arr):    """选择排序"""    # 第一层for表示循环选择的遍数    for i in range(len(arr) - 1):        # 将起始元素设为最小元素        min_index = i        # 第二层for表示最小元素和后面的元素逐个比较        for j in range(i + 1, len(arr)):            if arr[j] < arr[min_index]:                # 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标                min_index = j        # 查找一遍后将最小元素与起始元素互换        arr[min_index], arr[i] = arr[i], arr[min_index]    return arr

4.算法分析

选择排序和冒泡排序很类似，但是选择排序每轮比较只会有一次交换，而冒泡排序会有多次交换，交换次数比冒泡排序少，就减少cpu的消耗，所以在数据量小的时候可以用选择排序，实际适用的场合非常少。

1. 比较性：因为排序时元素之间需要比较，所以是比较排序

2. 稳定性：因为存在任意位置的两个元素交换，比如[5,  8, 5, 2]，第一个5会和2交换位置，所以改变了两个5原来的相对顺序，所以为不稳定排序。

3. 时间复杂度：我们看到选择排序同样是双层循环n*(n-1))，所以时间复杂度也为：O(n^2)

4. 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)

5. 记忆方法：选择对象要先选最小的，因为嫩，哈哈