Python中各种排序算法

陶远航

Python中各种排序算法

1. import time
   
2. import random
   
3. from typing import List
   
4. from numpy import sort as npst
   
5. #冒泡排序
   
6. def bubble_sort(arr):
   
7.     n = len(arr)
   
8.     for i in range(n):
   
9.         for j in range(0, n-i-1):
   
10.             if arr[j] > arr[j+1] :
    
11.                 arr[j], arr[j+1] = arr[j+1], arr[j]
    
12.     return arr
    
13. #快速排序
    
14. def quick_sort(arr):
    
15.     if len(arr) <= 1:
    
16.         return arr
    
17.     pivot = arr[len(arr) // 2]
    
18.     left = [x for x in arr if x < pivot]
    
19.     middle = [x for x in arr if x == pivot]
    
20.     right = [x for x in arr if x > pivot]
    
21.     return quick_sort(left) + middle + quick_sort(right)
    
22. #radix sort
    
23. def radix_sort(arr:List[int]):
    
24.     n = len(str(max(arr)))
    
25.     for k in range(n):
    
26.         bucket_list=[[] for i in range(10)]
    
27.         for i in arr:
    
28.             bucket_list[i//(10**k)%10].append(i)
    
29.         arr=[j for i in bucket_list for j in i]
    
30.     return arr
    
31. #Python自带排序
    
32. def easysort(list1):
    
33.     l2=list1
    
34.     l2.sort()
    
35.     return l2
    
36. #numpy排序
    
37. def npsort(list1):
    
38.     l2=list1
    
39.     return npst(l2)
    
40. 
    
41. #时间比较
    
42. list1=[]
    
43. for i in range(10000):
    
44.     list1.append(random.randint(1,100000))
    
45. t1=time.time()
    
46. print(bubble_sort(list1))
    
47. t2=time.time()
    
48. print(t2-t1)
    
49. t1=time.time()
    
50. print(quick_sort(list1))
    
51. t2=time.time()
    
52. print(t2-t1)
    
53. t1=time.time()
    
54. print(radix_sort(list1))
    
55. t2=time.time()
    
56. print(t2-t1)
    
57. t1=time.time()
    
58. print(easysort(list1))
    
59. t2=time.time()
    
60. print(t2-t1)
    
61. t1=time.time()
    
62. print(list(npsort(list1)))
    
63. t2=time.time()
    
64. print(t2-t1)

复制代码