不使用python中提供的sorted/sorted，自己实现三种排序方法，随机产生1000个[1,100000]之间的整数进行排序，各进行10次，对比三种方法的执行速度。
选择的：冒泡排序，插入排序，快速排序
由于1000个数体现不了算法的差别，我将1000改为10000。
冒泡排序算法平均复杂度为O(n^2)所以最慢.
插入排序算法平均复杂度也是O（n^2）但他相对冒泡排序来说，已近有了较大的改进.
快速排序算法平均复杂度是O（nlog2n）相对于上面两个要快很多.
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
import random import time def int_generator(n, floor, ceil): arr = [] for x in range(n): arr.append(random.randint(floor, ceil)) return arr def bubble_sort(num): if len(num) == 0 or len(num) == 1: return num for i in range(len(num)): for j in range(len(num)-1-i): if num[j] > num[j+1]: temp = num[j] num[j] = num[j+1] num[j+1] = temp return num def insert_sort(num): if len(num) == 0 or len(num) == 1: return num for i in range(1, len(num)): value = num[i] j = i-1 while j >= 0 and num[j] > value: num[j+1] = num[j] j -= 1 num[j+1] = value return num def partition(arr, low, high): p = arr[low] while low < high: while low < high and arr[high] >= p: high -= 1 arr[low] = arr[high] while low < high and arr[low] <= p: low += 1 arr[high] = arr[low] arr[low] = p return low def quick_sort(arr, low, high): if low < high: p = partition(arr, low, high) quick_sort(arr, low, p-1) quick_sort(arr, p+1, high) print('-----------------冒泡排序-----------------') start1 = time.time() for _ in range(50): arr1 = int_generator(1000, 1, 100000) bubble_sort(arr1) end1 = time.time() result1 = end1-start1 print(arr1) print("插入排序时间:%ds" % result1) print('------------------------------------------\n') print('-----------------插入排序-----------------') start2 = time.time() for _ in range(50): arr2 = int_generator(1000, 1, 100000) insert_sort(arr2) end2 = time.time() result2 = end2-start2 print(arr1) print("插入排序时间:%ds" % result2) print('------------------------------------------\n') print('-----------------快速排序-----------------') start3 = time.time() for _ in range(50): arr3 = int_generator(1000, 1, 100000) quick_sort(arr3, 0, len(arr3) - 1) end3 = time.time() result3 = end3-start3 print(arr1) print("快速排序时间:%ds" % result3) print('------------------------------------------\n') |
