八大排序算法及其性能（Python实现）

---

import time
import random
import copy
def bubble_sort(list):
    '''
    冒泡排序
    '''
    length = len(list)
    # 第一级遍历
    for index in range(1, length):
        # 第二级遍历
        for j in range(1, length - index):
            if list[j] > list[j + 1]:
                # 交换两者数据，这里没用temp是因为python 特性元组。
                list[j + 1], list[j] = list[j], list[j + 1]
    return list
def bubble_sort_flag(list):
    '''
    带标记的冒泡排序
    '''
    length = len(list)
    flag = True
    for index in range(1, length):
        if not flag:  # 没有发生交换，直接返回list
            return list
        flag = False
        for j in range(1, length - index):
            if list[j] > list[j + 1]:
                list[j + 1], list[j] = list[j], list[j + 1]
                flag = True
    return list
def selection_sort(list):
    '''
    选择排序
    '''
    n = len(list)
    for i in range(1, n):
        min = i
        for j in range(i + 1, n):
            if list[j] < list[min]:
                min = j
        if i != min:
            list[min], list[i] = list[i], list[min]
    return list
def insert_sort(list):
    '''
    插入排序
    '''
    n = len(list)
    for i in range(2, n):
        # 后一个元素和前一个元素比较
        # 如果比前一个小
        if list[i] < list[i - 1]:
            list[0] = list[i]
            j = i - 1
            while list[j] > list[0]:
                list[j + 1] = list[j]
                j -= 1
            list[j + 1] = list[0]
    return list
def shell_sort(list):
    '''
    希尔排序
    '''
    length = len(list)
    # 初始步长
    increment = length
    while increment > 1:
        increment = increment // 3 + 1;
        for i in range(increment + 1, length):
            if list[i] < list[i - increment]:
                list[0] = list[i]
                j = i
                while j >= increment and list[j - increment] > list[0]:
                    list[j] = list[j - increment]
                    j -= increment
                list[j] = list[0]
    return list
def merge_sort(list):
    '''
    归并排序
    '''
    # 认为长度不大于1的数列是有序的
    if len(list) <= 1:
        return list
    # 二分列表
    middle = len(list) // 2
    left = merge_sort(list[:middle])
    right = merge_sort(list[middle:])
    # 最后一次合并
    return merge(left, right)
# 合并
def merge(left, right):
    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result
def quick_sort(list):
    '''
    快速排序
    '''
    if len(list) <= 1:
        return list
    else:
        pivot = list[0]
        return quick_sort([x for x in list[1:] if x < pivot]) + [pivot] + quick_sort([x for x in list[1:] if x >= pivot])
def shiftDown(arr, index, length):  # 自顶向下堆化，从k开始堆化
    N = length - 1
    while 2 * index <= N:
        j = 2 * index
        if j < N and arr[j] < arr[j + 1]:  # 选出左右孩子节点中更大的那个
            j += 1
        if arr[index] < arr[j]:
            arr[index], arr[j] = arr[j], arr[index]
            index = j
        else:
            break
def heap_Sort(l):
    '''
    堆排序
    '''
    n = len(l) - 1
    for i in range(n // 2, 0, -1):
        shiftDown(l, i, len(l))
    while n > 1:
        l[1], l[n] = l[n], l[1]
        shiftDown(l, 1, n)
        n -= 1
def count_sort(list):
    '''
    计数排序
    '''
    # 取得最大值和最小值
    max_ = max(list)
    min_ = min(list)
    # 创建数组C
    length = max_ - min_ + 1
    count = [0] * length
    # 统计每项出现的次数
    for index in list:
        if index > 0:
            count[index] += 1
        # 负数放在最大数后面
        if index < 0:
            count[max_ + abs(index)] += 1
    index = 1
    # 填值
    for a in range(length - 1, max_, -1):
        for c in range(1, count[a] + 1):
            list[index] = -a + max_
            index += 1
    for a in range(max_ + 1):
        for c in range(1, count[a] + 1):
            list[index] = a
            index += 1
    return list
def test(func, random_list):
    l = copy.deepcopy(random_list)
    print(func.__doc__)
    s = time.time()
    func(l)
    print(time.time() - s)
func = [bubble_sort, bubble_sort_flag, selection_sort, insert_sort, merge_sort, shell_sort, quick_sort, count_sort,
        heap_Sort]
for i in range(3):
    print('-----------------')
    random_list = [random.randint(1, 10000) for i in range(40)]
    random_list[0] = 0
    last = []
    for each_func in func:
        test(each_func, random_list)