- 程序从标准输入中读取数据（一系列大写字母），并保存在数组中
- 将数组的元素从小到大排序，并输出结果
模板
#!/usr/bin/python3.5
class Sort:
def less(self, x, y):
return x < y;
def exch(self, sample, i, j):
t = sample[i]
sample[i] = sample[j]
sample[j] = t
def show(self, sample):
for element in sample:
print(element, end=' ')
print()
def isSorted(self, sample):
length = len(sample)
for i in range(1, length):
if self.less(sample[i], sample[i-1]):
return False
return True
def sort():
pass # 在子类中定义具体的排序算法
if __name__ == '__main__':
# 标准输入中读取字符，并将其排序
sample = input().split()
# sort = Select() 使用一种算法
sort.sort(sample)
if sort.isSorted(sample):
sort.show(sample)
- N：总是表示数组的长度
选择排序
原理
选择排序：首先从数值找出一个最小元素，将它与数值中第一个元素交换；再从剩下的元素中找出最小元素，将它与数值中第二个元素交换....直到整个数值有序；
代码描述
两层循环：
- 第一层依次遍历整个数组，假设当前为第 i 次，并将它当做最小元素 the_min
- 第二层依次遍历 i 后面的元素，假设当前为 j ，将 j 与 the_min 比较，如果 j 小于 the_min，则 j 变成 the_min （最终 the_min 为 i ~ 到数组完的最小元素）
- 交换 i 和 the_min 的位置，继续第一层循环
实现
class Sort:
.......
class Select(Sort):
def sort(self, sample):
N = len(sample)
for i in range(N): # 第 i 次扫描数组
the_min = i
for j in range(i+1, N): # 找出最小的元素
if self.less(sample[j], sample[the_min]):
the_min = j
self.exch(sample, i, the_min)
if __name__ == '__main__':
# 标准输入中读取字符，并将其排序
sample = input().split()
sort = Select() # 使用选择排序算法
sort.sort(sample)
if sort.isSorted(sample):
sort.show(sample)
/mnt/f/python $ cat data.txt
D G A B E C F
/mnt/f/python $ python3 selection.py < data.txt
A B C D E F G
效率
假设数组的长度为 N：
- 排序总共要交换 N 次
- 排序总共要比较 N² / 2 次
背景颜色代表比较次数
分析
选择排序的缺点在于：一个完全有序的数组和一个随机顺序的数组的排序时间一样长
插入排序
原理
插入排序：大循环遍历数组（1 ~ N-1）元素，内循环将当前的元素与前面的元素逐个比较，如果小于前面的元素，则交换；（左边已排序的元素总是有序 — . —）
D G A B E C F
当前元素
1. D - G 比较，不用交换：D G|A B E C F - G
2.1 G - A 比较，需要交换：D A G|B E C F - A
2.2 D - A 比较，需要交换：A D G|B E C F - A
3.1 G - B 比较，需要交换：A D B G|E C F - B
代码描述
两层循环：
- 第一层依次遍历第二个元素到数组完，假设当前为 i
- 第二层将它与前面区域的元素比较：首先，和前面相邻的元素比较，较小则交换，再与前面相邻的元素比较，小则交换，直到遇到一个
比它大的，结束（因为前面已经有序，肯定比它小，不需要再比较）；继续第一层循环
- 第二层将它与前面区域的元素比较：首先，和前面相邻的元素比较，较小则交换，再与前面相邻的元素比较，小则交换，直到遇到一个
实现
class Insert(Sort):
def sort(self, sample):
N = len(sample)
for i in range(1, N):
for j in range(i, 0, -1):
if self.less(sample[j], sample[j-1]):
self.exch(sample, j, j-1)
else:
break # 左边已排序的元素总是有序 — . —
if __name__ == '__main__':
# 标准输入中读取字符，并将其排序
sample = input().split()
# sort = Select()
sort = Insert() # 使用插入排序算法
sort.sort(sample)
if sort.isSorted(sample):
sort.show(sample)
分析
- 当一个数组已经有序时，插入排序的仅需遍历一次数组（不需要进行交换）
- 插入排序适合部分有序的数组，比如：
- 一个有序的大数组，接上一个随机小数组
- 数组中仅有几个元素的位置不正确
- 数组中的每个元素距离它们的目的位置不远
- 缺点是：每次仅交换相邻的两个元素
希尔排序
Shell 希尔排序是对插入排序的改进，（插入排序适用于部分有序的数组；缺点是只交换相邻的元素），希尔排序确定一个间隔 h，将整个数组 h 个子数组，对子数组进行插入排序；
h = 4
D G A B E C F
D ----- E
G ----- C
A ----- F
B -----
代码描述
- 根据数组长度 N 计算间隔 h（初始为 1），
h = h * 3 + 1==》 1, 4, 13, 40, 121 .... N/3 - 根据 h, 数组会被分成 h 个子数组，将子数组进行插入排序
- 三层循环
- 第一层逐渐缩小间隔 h ：将 h 从 h 递减到 1 （
h = h / 3）- 第二层用 i 代替 h ，依次遍历 i 到数组完 （这样每次会操作一个不同的子数组 h1, h2, ..., h, h1, ....）
- 第三层对某一个子数组进行插入排序：用 j 代替 i, 将 j 与 前面相邻的 j - h 比较，小则交换....
- 第二层用 i 代替 h ，依次遍历 i 到数组完 （这样每次会操作一个不同的子数组 h1, h2, ..., h, h1, ....）
- 第一层逐渐缩小间隔 h ：将 h 从 h 递减到 1 （
- h 减至 1时，相当于对整个数组进行插入排序
代码
class Shell(Sort):
def sort(self, sample):
N = len(sample)
h = 1
while h < (N // 3):
h = h * 3 + 1
while h >= 1:
for i in range(h, N):
j = i
while self.less(sample[j], sample[j-h]) and j >= h: # 当 j = h 时，比较 子数组最前的两个元素
self.exch(sample, j, j-h)
print(sample)
j -= h
h = h // 3
