冒泡排序
- 冒泡排序是一种比较简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们顺序错误就调换。
- 冒泡排序的算法实现：
- 比较相邻的两个元素，如果第一个比第二个大（升序排列），就交换它们两个的位置。
- 对每一对相邻的元素做同样的工作，从第一对到结尾的最后一对。这时zuihou最后的元素将会是最大的数。
- 针对所有的元素，重复以上的步骤，除了结尾已排序好的。直到没有任何一对数字需要比较。
- python代码实现
import random, time
# 随机生成一个列表，里面有10000个数字
data = [random.randint(10, 10000) for i in range(10000)]
# 冒泡排序
def bubble(data):
for i in range(len(data) - 1, 0, -1):
for j in range(i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
# 统计排序用了多久时间
start = time.time()
bubble(data)
end = time.time()
print(end - start)
耗时：7.338299751281738秒
快速排序
快速排序又称为划分交换排序
1.通过一趟排序将要排序的数据分割成独立的两部分
2.其中一部分的所有数据都比另外一部分的所有数据都要小
3.然后再按照此方法对这两部分数据分别进行快速排序
4.然后整个过程可以递归进行，以此达到整个数据变成有序序列-
实现步骤：
1.从数列中挑出一个元素为“基准”
2.重归排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任意一边），在这个分区结束后该基准就处于数列的中间位置。这个称为分区操作。
3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序.PNG python代码实现方式一
# 随机生成一个列表
data = [random.randint(10, 10000) for i in range(10000)]
# 快速排序方式一
def quick_sort(data):
left, middle, right = [], [], []
if len(data) > 1:
pivot = data[0]
for i in data:
if i < pivot:
left.append(i)
elif i == pivot:
middle.append(i)
else:
right.append(i)
return quick_sort(left) + middle + quick_sort(right)
else:
return data
start = time.time()
quick_sort(data)
end = time.time()
print(end - start)
耗时：0.016863584518432617秒
- python代码实现二
# 随机生成一个列表
data = [random.randint(10, 10000) for i in range(10000)]
# 快速排序方式二
def quick2_sort(data: list, start: int, end: int):
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid = data[start]
# low为序列左边的由左向右移动的游标
low = start
# high为序列右边的由右向左移动的游标
high = end
while low < high:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low < high and data[high] >= mid:
high -= 1
# 将high指向的元素放到low的位置上
data[low] = data[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and data[low] < mid:
low += 1
# 将low指向的元素放到high的位置上
data[high] = data[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
data[low] = mid
# 对基准元素左边的子序列进行快速排序
quick2_sort(data, start, low - 1)
# 对基准元素右边的子序列进行快速排序
quick2_sort(data, low + 1, end)
start = time.time()
quick2_sort(data, 0, 10000 - 1)
end = time.time()
print(end - start)
耗时：0.01979970932006836秒
冒泡排序和快速排序的对比
同样的一组数据，快速排序所需要的时间比冒泡排序快的太多了
排序算法总结
排序算法总结.PNG
