一、原理
- 冒泡排序
- 1.比较相邻的元素，如果前一个比后一个大，就交换它们。
- 2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样一轮比较结束，最大的数被移动到了最后的位置。
- 3.针对所有的元素重复以上的步骤，除了最后一个。
- 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 快速排序
- 1.先从数列中取出一个数作为基准数。
- 2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3.再对左右区间重复第二步，直到各区间只有一个数。
更多参考「快速排序」，对挖坑填数进行总结:- 1．i=L; j=R; 将基准数挖出形成第一个坑a[i]。
- 2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- 3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
二、代码实现
题目：随机给定一个数组，按从小到大排序。
逻辑代码：
from time import time
import numpy as np
# 冒泡排序
def bubble_sort(arr):
length = len(arr)
for i in range(length - 1):
for j in range(0, length - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# 快速排序
def quick_sort(arr, l, r):
'''
采用"挖坑填数+分治法"
'''
if l < r:
i, j, x = l, r, arr[l] # 取第一个数为基准数
while i < j:
while i < j and arr[j] >= x: # 从右向左找第一个小于x的数
j -= 1
if i < j:
arr[i] = arr[j] # 填坑a[i]
i += 1
while i < j and arr[i] < x: # 从左向右找第一个大于等于x的数
i += 1
if i < j:
arr[j] = arr[i] # 填坑a[j]
j -= 1
arr[i] = x # 将基准数填入a[i]
quick_sort(arr, l, i - 1) # 递归调用
quick_sort(arr, i + 1, r)
if __name__ == "__main__":
# 冒泡排序
np.random.seed(10)
array = list(np.random.randint(0, 1000, size=(2000,)))
start = time()
bubble_sort(array)
end = time()
print(f"bubble_sort()函数耗时{end - start}秒")
print(array[:100])
# 快速排序
np.random.seed(10)
array = list(np.random.randint(0, 1000, size=(2000,)))
start = time()
quick_sort(array, 0, len(array) - 1)
end = time()
print(f"quick_sort()函数耗时{end - start}秒")
print(array[:100])
运行结果如下，)
：
