排序算法 平均时间复杂度 最坏复杂度 空间复杂度 稳定性
冒泡排序 O(n2) O(n2) 0(1) 稳定
选择排序 O(n2) O(n2) 0(1) 不稳定
直接插入排序 O(n2) O(n2) 0(1) 稳定
快速排序 O(nlogn) O(n2) O(logn) 不稳定
归并排序 O(nlogn) O(nlogn) O(1) 稳定
堆排序 O(nlogn) O(nlogn) 0(1) 不稳定
希尔排序 O(nlogn) O(n8)1 O(1) 不稳定
基数排序 O(lognB) O(lognB) O(n) 稳定
二叉树排序 O(nlogn) O(nlogm) O(n) 稳定
计数排序 O(n + k) O(n + k) O(n+ k) 稳定
# -*- coding:UTF-8 -*-
def bubble_sort(sort_list):
    """
    冒泡排序
    :param sort_list: 
    :return: 
    """
    length = len(sort_list)
    # 第一级遍历
    for index in range(length):
        # 第二级遍历
        for j in range(1, length - index):
            if sort_list[j - 1] > sort_list[j]:
                # 交换两者数据,这里没用temp是因为python 特性元组。
                sort_list[j - 1], sort_list[j] = sort_list[j], sort_list[j - 1]
    return sort_list

# -*- coding:UTF-8 -*-
def selection_sort(sort_list):
    """
    选择排序
    :param sort_list: 
    :return: 
    """
    n = len(sort_list)
    for i in range(0, n):
        min_value = i
        for j in range(i+1, n):
            if sort_list[j] < sort_list[min_value]:
                min_value = j
                sort_list[min], sort_list[i] = sort_list[i], sort_list[min]
    return sort_list

# -*- coding:UTF-8 -*-
def insert_sort(sort_list):
    """
    插入排序
    :param sort_list: 
    :return: 
    """
    n = len(sort_list)
    for i in range(1, n):
        # 后一个元素和前一个元素比较
        # 如果比前一个小
        if sort_list[i] < sort_list[i - 1]:
            # 将这个数取出
            temp = sort_list[i]
            # 保存下标
            index = i
            # 从后往前依次比较每个元素
            for j in range(i - 1, -1, -1):
                # 和比取出元素大的元素交换
                if sort_list[j] > temp:
                    sort_list[j + 1] = sort_list[j]
                    index = j
                else:
                    break
            # 插入元素
            sort_list[index] = temp
    return sort_list


# -*- coding:UTF-8 -*-
def shell_sort(sort_list):
    """
    希尔排序
    :param sort_list: 
    :return: 
    """
    n = len(sort_list)
    # 初始步长
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = sort_list[i]
            j = i
            # 插入排序
            while j >= gap and sort_list[j - gap] > temp:
                sort_list[j] = sort_list[j - gap]
                j -= gap
            sort_list[j] = temp
        # 得到新的步长
        gap = gap // 2
    return sort_list


# -*- coding:UTF-8 -*-
def quick_sort(arr):
    """
    快速排序
    :param arr:
    :return:
    """
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return quick_sort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               quick_sort([x for x in arr[1:] if x >= pivot])


发表评论

电子邮件地址不会被公开。 必填项已用*标注