排序算法(快速排序)

快速排序算法效率高，运行稳定的算法。jdk 内置就是采用的快速排序算法。

和归并排序相似快排也是采用分治法思想，将待排数列分成两部分，取一个参照元素，从两端到中间依次比较所有元素，将较小和较大元素分开。

然后重复这个过程，直至分到一个列表只有一个元素。

"""
@Author TZG
@Email 1651504722@qq.com
"""
import random
import time
import sys


# 生成一个长度1w的随机数列
a = []
for i in range(10000):
    a.append(random.randint(0, 10000))

print(len(a))
temp = a[:]
temp[5:9995] = ['...']
print(temp)


# 快速排序
def quickSortTurn(L, low, high):
    i = low
    j = high
    if i >= j:
        return
    key = L[i]
    while i < j:
        while i < j and L[j] >= key:
            j = j - 1
        L[i] = L[j]
        while i < j and L[i] <= key:
            i = i + 1
        L[j] = L[i]
    L[i] = key
    quickSortTurn(L, low, i - 1)
    quickSortTurn(L, j + 1, high)
    return L


def quickSort(L):
    return quickSortTurn(L, 0, len(L)-1)


# 快速排序开始
begin = time.time()
b = quickSort(a)
end = time.time()
print(len(b))
temp = b[:]
temp[5:9995] = ['...']
print(temp)
t3 = (end - begin)
print("耗时：%ss" % t3)

输出：

10000
[4987, 3878, 5304, 3628, 3937, '...', 7613, 4245, 5005, 7630, 1]
10000
[1, 3, 3, 8, 8, '...', 9990, 9991, 9992, 9997, 9998]
耗时：0.025002479553222656s