第二章：排序基础
2019-03-30 本文已影响0人
fxqp1043
选择排序算法（selectionSort）
算法思想：
（直白描述）
1. 找出所有元素中的最小值，与第一个位置的元素互换。
2. 找出剩下的元素中的最小值，与第二个位置的元素互换。
3. 以此类推。
（形式化描述）
重复（元素个数-1）次
# 从0开始
把第一个没有排序过的元素设置为最小值
遍历每个没有排序过的元素
如果元素 < 现在的最小值
将此元素设置成为新的最小值
将最小值和第一个没有排序过的位置交换
算法图示：
选择排序.gif
Python使用函数实现：
def selectionSort(arrList):
'''
选择排序
:param arrList:可迭代对象
:return:
'''
for i in range(0, len(arrList)):
# 寻找[i, len(arrlist))区间的最小值
minIndex = i
for j in range(i+1, len(arrList)):
if arrList[j] < arrList[i]:
minIndex = j
# 交换i位置和最小值
# 注意双向交换
arrList[i], arrList[minIndex] = arrList[minIndex], arrList[i]
# 测试
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
selectionSort(a)
print(a)
# 输出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
使用模板（泛型）编写算法：
随机生成算法测试用例：
测试算法性能
插入排序算法（insertionSort）
算法思想：
（直白描述）
1.当只考虑第一个元素的时候，它已经排好序了，第一个元素不动。
2.寻找第二个元素合适的位置，把它和第一个元素比较，如果小于第一个元素，交换，否则，它的位置是合适的，继续下一次循环。
3.寻找第三个元素合适的位置，先和第二个元素比较，如果小于第二个元素，和第二个元素交换位置，然后和第一个元素比较，如果小于第一个元素，和第一个元素交换位置，继续下一次循环。
Python使用函数实现：
def insertionSort(arrList):
# 从1开始，第0个元素已经有序
for i in range(1, len(arrList)):
# 寻找arrList[i]合适的插入位置
for j in range(i, 0, -1):
# 如果当前位置元素比前一个位置元素小，交换
if arrList[j] < arrList[j-1]:
arrList[j-1], arrList[j] = arrList[j], arrList[j-1]
# 否则，当前元素位置合适，寻找下一个元素的合适位置
else:
break
a = [10, 9, 8, 7, 6]
insertionSort(a)
print(a)
# [6, 7, 8, 9, 10]
插入排序算法的改进
算法思想：
（形式化描述）
将第一个元素标记为已排序
遍历每个没有排序过的元素
“提取” 元素 X
i = 最后排序过元素的指数 到 0 的遍历
如果现在排序过的元素 > 提取的元素
将排序过的元素向右移一格
否则：插入提取的元素
算法图示：
插入排序.gif
Python使用函数实现：
def insertionSort(arrList):
# 从1开始，第0个元素已经有序
for i in range(1, len(arrList)):
# 寻找arrList[i]合适的插入位置
# 将当前元素提取出来
x = arrList[i]
# j保存元素应该插入的位置，初始为i
j = i
# -1取不到，可以取到0
for j in range(i, -1, -1):
if arrList[j-1] > x:
# 赋值而不做交换
arrList[j] = arrList[j-1]
else:
# 位置合适
break
arrList[j] = x
a = [10, 9, 8, 7, 6]
insertionSort(a)
print(a)
# [6, 7, 8, 9, 10]
