第三章 排序

作者: Qiuo 分类: 数据结构 发布时间: 2020-04-02 01:30

排序的好处

1.数据容易被读
2.数据有利于统计和整理
3.可以大幅度减少数据查找的时间

冒泡排序

初始数据
55 23 87 62 16
第一次扫描:
55 23 87 62 16
23 55 87 62 16
23 55 87 62 16
23 55 62 87 16
23 55 62 16 87
第二次扫描:
23 55 62 16 87
23 55 62 16 87
23 55 16 62 87
23 55 16 62 87
第三次扫描:
23 55 16 62 87
23 55 16 62 87
23 16 55 62 87
第四次扫描:
23 16 55 62 87
16 23 55 62 87
# 冒泡排序
data = [16, 25, 39, 27, 12, 8, 45, 63]
print("冒泡排序法:原始数据为:")
for i in range(len(data)):
    print("%3d" % data[i], end="")
print()
for i in range(7, -1, -1):
    for j in range(i):
        if data[j] > data[j+1]:
            data[j], data[j+1] = data[j+1], data[j]
    print("第%d次排序的结果是:" % (8-i), end="")
    for j in range(8):
        print("%3d" % data[j], end="")
    print()
print("排序后的结果为:")
for j in range(8):
    print("%3d" % data[j], end="")
print()
#程序运行结果为
# 冒泡排序法:原始数据为:
# 16 25 39 27 12 8 45 63
# 第1次排序的结果是: 16 25 27 12 8 39 45 63
# 第2次排序的结果是: 16 25 12 8 27 39 45 63
# 第3次排序的结果是: 16 12 8 25 27 39 45 63
# 第4次排序的结果是: 12 8 16 25 27 39 45 63
# 第5次排序的结果是: 8 12 16 25 27 39 45 63
# 第6次排序的结果是: 8 12 16 25 27 39 45 63
# 第7次排序的结果是: 8 12 16 25 27 39 45 63
# 第8次排序的结果是: 8 12 16 25 27 39 45 63
# 排序后的结果为:
# 8 12 16 25 27 39 45 63

选择排序

选择排序属于枚举法的应用
反复从未排序的数列里取出最小的元素,加入到另一个数列,
最后的结果就是已排序的数列.
选择排序的两种方式
第一种从大到小,将最大值放入第一个位置
第二种从小到大,将最小值放入第一个位置
原始值
55 23 87 62 16
第一次扫描
55 23 87 62 16
16 23 87 62 55
第二次扫描
16 23 87 63 55
16 23 87 62 55
第三次扫描
16 23 87 62 55
16 23 55 62 87
第四次扫描
16 23 55 62 87
16 23 55 62 87
#选择排序
data = [16, 25, 39, 27, 12, 8, 45, 63]
print("原始数据为:")
for i in range(8):
    print("%3d" % data[i], end="")
print("\n------------------------")


def select(data):
    for i in range(8): #控制排序输出个数
        for j in range(i+1, 8): #控制排序次数
            if data[i] > data[j]:
                data[i], data[j] = data[j], data[i]
        print("%3d" % data[i], end="")
print()


print("排序结果为:")
select(data)

# 运行结果
# 原始数据为:
# 16 25 39 27 12 8 45 63 
# ------------------------
# 排序结果为:
# 8 12 16 25 27 39 45 63

快速排序

快速排序又称分割交换法,是目前公认最佳的排序法,也是分治法的方式
缺点就是对于小规模的数据集性能不是很好。
先在数据中找到虚拟的中间值,
并按此中间值将所有打算排序的数据分为两个部分.
其中小于中间值的数据放入左边,大于中间值的放在右边,
再以同样的方式分别处理左右两边的数据,直到排序完成为止. 
标签云