冒泡排序

• 冒泡排序是一种比较简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们顺序错误就调换。
• 冒泡排序的算法实现：
  1. 比较相邻的两个元素，如果第一个比第二个大（升序排列），就交换它们两个的位置。
  2. 对每一对相邻的元素做同样的工作，从第一对到结尾的最后一对。这时zuihou最后的元素将会是最大的数。
  3. 针对所有的元素，重复以上的步骤，除了结尾已排序好的。直到没有任何一对数字需要比较。
• 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