Python-选择排序

选择排序算法

选择排序虽然是效率不是很高的排序算法，不过它在我们编程的时候还是会经常使用，出场次数有时候可能要比效率更高的那些算法更高。

首先咱们通过一个动图来了解选择排序的过程：

5863482636c750d9e5cb683374fba9d4.gif

通过这个动图，我们可以发现选择排序的过程为：每次一轮遍历都找到当前最小的元素并和未排序元素的第一个元素交换位置。

接下来编写代码：

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

def main():
    arr = [3,1,2,4,6,7,8,9,5]
    sort(arr)
    print(arr)

if __name__ == "__main__":
    main()
    pass

执行会输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

使用随机数生成测试用例

通过上面我们已经掌握了选择排序代码的编写了，不过我们会发现，上面代码的测试数组太简单了，只有1-9，这么一段数据集太少了并不能测试我们编写的排序算法到底靠不靠谱。

那如何才能靠谱呢？

你应该已经想到了：加大测试集，增加测试次数，是的，没错，当我们数据量大，测试集非常多的时候这段程序如果依然能正确的进行排序，那我们就可以判断它是一个正确的排序算法了。

好了，问题来了，如何才能生成大量的数据集（比如说一万条）呢？

手写肯定是不行，所以咱们需要通过程序帮我们生成，接下来我们分两步完成生成随机测试用例并测试。

1. 使用随机数生成大量测试集；
2. 测试程序是否已经是排好序的状态。

第一步：随机生成1万条测试用例

使用random模块我们就可以生成随机数了
利用random模块的random.randint(a,b)方法就可以生成从a到b的随机数。
编写代码：

import random
def getRandomArr(num):
    arr = []
    for i in range(num):
        arr.append(random.randint(0,num))
    return arr

这段代码可以生成num个从0到num的随机数。

第二部：测试代码编写

接下来我们需要编写一个函数检测数组是否已经是排好序的。

def isSorted(arr):
    for i in range(len(arr)-1):
        if arr[i] > arr[i+1]:
            return False
    return True

完整代码：

import random

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

def main():
    arr = getRandomArr(10000)  #测试一万条数据
    sort(arr)
    
    print(isSorted(arr))#检测是否排好序

#获取随机数
def getRandomArr(num):
    arr = []
    for i in range(num):
        arr.append(random.randint(0,num))
    return arr

#检测是否已排序
def isSorted(arr):
    for i in range(len(arr)-1):
        if arr[i] > arr[i+1]:
            return False
    return True


if __name__ == "__main__":
    main()
    pass

这样子我们就完成了一个选择排序的编写与测试啦。

绘图查看选择排序的算法执行效率

还不想这么早结束，咱们在执行代码的时候发现当测试集数据量非常大的时候我们的程序非常慢，其实选择排序算是一种效率较低的排序算法，它的代码执行效率为：