O(n^2)级别的排序算法 选择排序算法+数据结构=编程
算法实际上是依托于数据结构的，没有数据结构就没有算法。
以下代码在Python3.5上正常运行，转载请注明出处。
给Python学习算法实战课的同学，一个参考。
By.秋名山车神
算法与数据结构C++精解
将一个列表：10, 9, 8, 7, 6, 5, 4, 3, 2, 1 进行从小到大排序：
普通实现# arr为待排序的列表
# 在从0到n之间进行排序
def selection_sort(arr, n):
for i in range(n):
# 假定i的位置是最小值
minIndex = i
for j in range(i+1, n):
if arr[j] < arr[minIndex]:
minIndex = j
# 交换arr[i] 和 arr[minIndex]的值
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
# 生成测试数据
a = [10,9,8,7,6,5,4,3,2,1]
selection_sort(a, 10)
for i in a:
print(str(i), end = " ")
print()自定义类型排序
Student.py
class Student(object):
def __init__(self, name, score):
self.name = name
self.score = score
# 重载小于运算符
def __lt__(self, otherStudent):
# 类似其他语言的三元运算符，如果分数相等则比较名称
return (self.score < otherStudent.score if self.score != otherStudent.score else self.name < otherStudent.name)
# 只比较分数
# return self.score < otherStudent.score
# 当使用print打印一个对象的时候，按照这种格式显示
def __repr__(self):
return "Student: " + self.name + " " + str(self.score)main.py
from Student import Student
def selection_sort(arr, n):
for i in range(n):
# 假定i的位置是最小值
minIndex = i
for j in range(i+1, n):
if arr[j] < arr[minIndex]:
minIndex = j
# 交换arr[i] 和 arr[minIndex]的值
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
# 测试模板函数，传入整型列表
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
selection_sort( a , 10 )
for i in a:
print(str(i), end = " ")
print()
# 测试模板函数，传入浮点数列表
b = [4.4, 3.3, 2.2, 1.1]
selection_sort(b,4)
for i in b:
print(str(i), end = " ")
print()
# 测试模板函数，传入字符串列表
c = ["D", "C", "B", "A"]
selection_sort(c,4)
for i in c:
print(str(i), end = " ")
print()
# 测试模板函数，传入自定义结构体Student列表
d = [Student("D", 80), Student("C", 100), Student("B", 95), Student("A", 95)]
selection_sort(d,4)
for i in d:
print(str(i))
print()或许我们可以更灵活
SortTestHelper.py
import random
import time
class SortTestHelper(object):
def generate_random_array(n, rangeL, rangeR):
assert rangeL <= rangeR
arr = [None for _ in range(n)]
random.seed(int(time.time()))
for i in range(n):
arr[i] = random.randint(rangeL, rangeR) % (rangeR - rangeL + 1) + rangeL
return arr
def print_array(arr):
for o in arr:
print(o, end = " ")
print()main.py
from SortTestHelper import SortTestHelper
"""
Python的每一个数字都被描述为一个不可变对象
它需要不断的创建对象，修改引用，垃圾回收，等等一系列操作
所以它不像其他语言那样能够快速操作庞大的千万次的数值运算
Python社区为了弥补这一缺点，使用C语言实现了排序功能
"""
def selection_sort(arr, n):
for i in range(n):
minIndex = i
for j in range(i+1, n):
if arr[j] < arr[minIndex]:
minIndex = j
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
N = 10000
arr = SortTestHelper.generate_random_array(N, 0, 10000)
"""
我为什么要这么做？
1. Python社区不希望程序员自己再造轮子
2. 前面我们已经使用模仿C++的算法实现过了
3. 这正是Python最大的魅力之所在
4. 人生苦短，我用Python
我想降序排列？
arr.sort(reverse = True)
干杯！
"""
arr.sort()
# Python的特点导致操作数字会特别的慢
# selectionSort(arr, N)
print(arr)可以增加一个消耗时长测试的方法
SortTestHelper.py
import random
import time
class SortTestHelper(object):
def generate_random_array(n, rangeL, rangeR):
assert rangeL <= rangeR
arr = [None for _ in range(n)]
random.seed(int(time.time()))
for i in range(n):
arr[i] = random.randint(rangeL, rangeR) % (rangeR - rangeL + 1) + rangeL
return arr
def is_sort(arr, n):
for i in range(n - 1):
if arr[i] > arr[i+1]:
return False
return True
def test_sort(sort_name, sort_def, **kwargs):
arr = kwargs.get("arr")
n = kwargs.get("n")
start_time = time.time()
sort_def(arr, n)
# 十万个数字的级别测试需要非常久的时间，建议使用Python内置函数测试十万级别
# 是不是被内置函数的效率惊呆了？
# arr.sort()
# end_time = time.time()
assert SortTestHelper.is_sort(arr, n)
# python标准建议我们使用format来替换字符串，而不是%。
print("{:.6f} s".format(end_time - start_time))main.py
from SortTestHelper import SortTestHelper
def selection_sort(arr, n):
for i in range(n):
minIndex = i
for j in range(i+1, n):
if arr[j] < arr[minIndex]:
minIndex = j
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
n = 10000
arr = SortTestHelper.generate_random_array(n, 0, n)
# 可以看到Python操作大量数值类型是如此耗时
SortTestHelper.test_sort("fun1", selection_sort, arr=arr, n=n)
