Python中各种排序算法

陶远航

Python中各种排序算法

import time
import random
from typing import List
from numpy import sort as npst
#冒泡排序
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
#快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
#radix sort
def radix_sort(arr:List[int]):
    n = len(str(max(arr)))
    for k in range(n):
        bucket_list=[[] for i in range(10)]
        for i in arr:
            bucket_list[i//(10**k)%10].append(i)
        arr=[j for i in bucket_list for j in i]
    return arr
#Python自带排序
def easysort(list1):
    l2=list1
    l2.sort()
    return l2
#numpy排序
def npsort(list1):
    l2=list1
    return npst(l2)

#时间比较
list1=[]
for i in range(10000):
    list1.append(random.randint(1,100000))
t1=time.time()
print(bubble_sort(list1))
t2=time.time()
print(t2-t1)
t1=time.time()
print(quick_sort(list1))
t2=time.time()
print(t2-t1)
t1=time.time()
print(radix_sort(list1))
t2=time.time()
print(t2-t1)
t1=time.time()
print(easysort(list1))
t2=time.time()
print(t2-t1)
t1=time.time()
print(list(npsort(list1)))
t2=time.time()
print(t2-t1)