python 之 排序

注：

算法演示工具： https://algorithm-visualizer.org/

参考：https://www.runoob.com/python3/python3-examples.html

参考：《算法图解》

环境： Visual Code Python2.7

快速排序

简介：从未排序的序列中找到最小（最大）元素，存放到新序列中。然后再从剩下未排序的序列中继续查找，直到末尾。

时间： O(n*n)

图示：

 示例：

# -*- coding:UTF-8 -*-
#!/usr/bin/env python
import sys

# 查找最小原色
def FindSmallest(arr):
    smallest = arr[0]           # 默认最小值
    smallIndex = 0              # 默认最小值索引

    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallIndex = i

    return smallIndex

# 选择排序
def SelectSort(arr):
    newArr = []
    for i in range(len(arr)):
        print(u'--> 查找序列:{0}'.format(arr))
        # 查找数组中最小元素索引
        smallIndex = FindSmallest(arr)
        # 原有数组移除指定值
        smallValue = arr.pop(smallIndex)
        # 将值放置到新列表中
        newArr.append(smallValue)

    return newArr


if __name__ == '__main__':
    arr = [-5,10,8,6,0,5]
    print(u'未排序序列:{0}'.format(arr))
    newArr = SelectSort(arr)
    print(u'已排序序列:{0}'.format(newArr))


'''
未排序序列:[-5, 10, 8, 6, 0, 5]
--> 查找序列:[-5, 10, 8, 6, 0, 5]
--> 查找序列:[10, 8, 6, 0, 5]
--> 查找序列:[10, 8, 6, 5]
--> 查找序列:[10, 8, 6]
--> 查找序列:[10, 8]
--> 查找序列:[10]
已排序序列:[-5, 0, 5, 6, 8, 10]
'''