代码准备

In [1]:
import copy
import math
import random
import time

SEED =2019
MIN = 0
MAX = 10000
LIST_LENGTH = 1000
NUM_TESTS = 50

random.seed(SEED)
UNSORTED_LISTS = [
    [random.randint(MIN, MAX) for i in range(LIST_LENGTH)] 
    for j in range(NUM_TESTS)
]
SORTED_LISTS = [
    sorted(unsorted_list) 
    for unsorted_list in UNSORTED_LISTS
]

def test_sort_functions(functions, verbose=False):
    func_times = {}
    
    print('Testing ...')
    for name, func in functions.items():
        unsorted_lists_copy = copy.deepcopy(UNSORTED_LISTS)

        start = time.time()
        sorted_lists = [func(unsorted_list) for unsorted_list in unsorted_lists_copy]
        stop = time.time()

        func_time = stop - start
        func_times[name] = func_time

        is_ac = True
        for i in range(NUM_TESTS):
            if sorted_lists[i] != SORTED_LISTS[i]:
                is_ac = False
                break

        print(f'[✓] {name:20s} {func_time:.3f} s' if is_ac else
              f'[x] {name:20s}')

    print('\nRanking')
    min_func_time = min(func_times.values())
    sorted_func_times = sorted(
        [[name, func_time, func_time / min_func_time]
         for name, func_time in func_times.items()], key=lambda x: x[1]
    )
    for i, (name, func_time, time_factor) in enumerate(sorted_func_times):
        print(f'{i:2d}: {name:20s} {func_time:.3f} s {time_factor:-6.1f}')

def sort_func(nums):
    raise NotImplementedError

排序算法的实现

冒泡排序(Bubble Sort)

In [2]:
def bubble_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        for j in range(0, n - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

插入排序(Insertion Sort)

In [3]:
def insertion_sort(nums):
    n = len(nums)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1],nums[j]
            else:
                break
    return nums

选择排序(Selection Sort)

In [4]:
def selection_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        if i != min_idx:
            nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

归并排序(Merge Sort)

In [5]:
def merge_sort(nums):
    n = len(nums)
    if(n < 2):
        return nums
    middle = math.floor(n / 2)
    left, right = nums[0:middle], nums[middle:]
    return _merge(merge_sort(left), merge_sort(right))

def _merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    if left:
        result.extend(left);
    if right:
        result.extend(right);
    return result

希尔排序(Shell Sort)

In [6]:
def shell_sort(nums):
    n = len(nums)
    gap = 1
    while gap < n / 2:
        gap *= 2
    while gap >= 1:
        for i in range(gap, n):
            for j in range(i, 0, -gap):
                if nums[j] < nums[j - gap]:
                    nums[j], nums[j - gap] = nums[j - gap], nums[j]
                else:
                    break
        gap = int(gap / 2)
    return nums

计数排序(Counting Sort)

In [7]:
def counting_sort(nums, value_min=MIN, value_max=MAX):
    value_range = value_max - value_min + 1
    bucket = [0] * value_range
    for num in nums:
        bucket[num - value_min] += 1
    nums = [num + value_min
            for num in range(value_range)
            for _ in range(bucket[num])]
    return nums

桶排序(Bucket Sort)

In [8]:
def bucket_sort(nums, value_min=MIN, value_max=MAX, num_buckets=20, sort_func=sorted):
    value_range = value_max - value_min + 1
    buckets = [[] for _ in range(num_buckets)]
    for num in nums:
        bucket_id = math.floor((num - value_min) / (value_range / num_buckets))
        buckets[bucket_id].append(num)
    for bucket_id in range(num_buckets):
        buckets[bucket_id] = sort_func(buckets[bucket_id])
    nums = [num
            for bucket in buckets
            for num in bucket]
    return nums

基数排序(Radix Sort)

In [9]:
def radix_sort(nums):
    max_value = max(nums)
    max_digit = int(math.log10(max_value) + 1)

    for digit in range(0, max_digit):
        buckets = [[] for _ in range(10)]
        for num in nums:
            bucket_id = int(num / 10 ** digit % 10)
            buckets[bucket_id].append(num)

        nums = [num
                for bucket in buckets
                for num in bucket]
            
    return nums

堆排序(Heap Sort)

In [10]:
def heap_sort(nums): 
    n = len(nums)

    # Build max heap
    for i in range(n, -1, -1): 
        _heapify(nums, heap_len=n, curr=i) 

    # Sort
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        _heapify(nums, heap_len=i, curr=0) 

    return nums

def _heapify(nums, heap_len, curr): 
    max_idx = curr
    l = 2 * curr + 1
    r = 2 * curr + 2

    if l < heap_len and nums[curr] < nums[l]: 
        max_idx = l 

    if r < heap_len and nums[max_idx] < nums[r]: 
        max_idx = r 

    if max_idx != curr: 
        nums[curr], nums[max_idx] = nums[max_idx], nums[curr]
        _heapify(nums, heap_len=heap_len, curr=max_idx) 

快速排序(Quick Sort)

In [11]:
def quick_sort(nums):
    return _quick_sort(nums, left=0, right=len(nums) - 1)

def _quick_sort(nums, left, right):
    if left < right:
        partition_idx = _partition(nums, left, right)
        _quick_sort(nums, left, partition_idx - 1)
        _quick_sort(nums, partition_idx + 1, right)
    return nums

def _partition(nums, left, right):
    pivot = left
    idx = pivot + 1
    i = idx
    while  i <= right:
        if nums[i] < nums[pivot]:
            nums[i], nums[idx] = nums[idx], nums[i]
            idx += 1
        i += 1
    nums[pivot], nums[idx - 1] = nums[idx - 1], nums[pivot]
    return idx - 1

性能测试

In [12]:
sort_functions = {
    'sorted': sorted,
    'Bubble Sort': bubble_sort,
    'Insertion Sort': insertion_sort,
    'Selection Sort': selection_sort,
    'Merge Sort': merge_sort,
    'Shell Sort': shell_sort,
    'Counting Sort': counting_sort,
    'Bucket Sort (sorted)': bucket_sort,
    'Radix Sort': radix_sort,
    'Heap Sort': heap_sort,
    'Quick Sort': quick_sort,
}
test_sort_functions(sort_functions)
Testing ...
[✓] sorted               0.004 s
[✓] Bubble Sort          3.720 s
[✓] Insertion Sort       2.487 s
[✓] Selection Sort       1.665 s
[✓] Merge Sort           0.128 s
[✓] Shell Sort           0.571 s
[✓] Counting Sort        0.089 s
[✓] Bucket Sort (sorted) 0.015 s
[✓] Radix Sort           0.079 s
[✓] Heap Sort            0.198 s
[✓] Quick Sort           0.099 s

Ranking
 0: sorted               0.004 s    1.0
 1: Bucket Sort (sorted) 0.015 s    4.1
 2: Radix Sort           0.079 s   21.7
 3: Counting Sort        0.089 s   24.5
 4: Quick Sort           0.099 s   27.5
 5: Merge Sort           0.128 s   35.5
 6: Heap Sort            0.198 s   54.6
 7: Shell Sort           0.571 s  157.7
 8: Selection Sort       1.665 s  460.1
 9: Insertion Sort       2.487 s  687.1
10: Bubble Sort          3.720 s 1027.8