排序基本算法
先来一张图片，平常排序算法总览
来源于百度百科
接下来介绍本次的主题：选择排序
来源于百度百科
原理
每一次从待排序的数据元素中选出最小(或最大)的一个元素，放在序列的起始位置，直到序列有序。注意，它是不稳定的排序方法，即其并不能保证相同元素的名次不变。
- 时间复杂度 O(n^2)
- n 值较小时， 选择排序比冒泡排序快
def selection_sort(list_test):
for i in range(0, len(list_test)):
min_d = i # 0 1
for j in range(i + 1, len(list_test)): # 1 - len(list_test)
if list_test[j] < list_test[min_d]:
min_d = j
list_test[i], list_test[min_d] = list_test[min_d], list_test[i]
解读
两层循环，第一层从 0 到 len(list_test)，第二层从 1 到 len(list_test)，第一层的 min_d 相当于下标， 从第二层循环开始，每次比较序列的第一个元素和其之后的元素，如果发现比第一个元素小的，将其下标赋值给 min_d，直至最后发现一个比下标为 min_d 小的，然后将其下标保存起来。在第二层循环结束后，将比第一个元素和下标为 min_d 元素交换位置。然后继续开始比较。。。
还有一种方式比较好理解：
def findsmallest(arr):
# 找到 arr 中最小的元素
smallest = arr[0]
smallest_index = 0
for i in xrange(1,len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newarr = []
for i in xrange(len(arr)):
smallest = findsmallest(arr)
newarr.append(arr.pop(smallest))
return newarr
你觉得呢？
