1.冒泡排序与鸡尾酒排序

'''
@Author : "HCL"
*冒泡排序以及其优化
1.当整体数组有序时结束循环
2.更新有序边界
*鸡尾酒排序
'''
from typing import List

#   python 自带的sorted()和sort原理归并排序，并且利用了python无法实现的底层实现，比侦察和那个归并排序快10-20倍
#   需要排序的列表
need_sortlist = [3, 2, 15, 4, 5, 6, 7, 8, 1222]


def bubble_sort(need_sortlist: List[int]) -> List[int]:
    """
    冒泡排序朴素版
    时间复杂度O(n^2)
    :param need_sortlist:待排序的数组
    :return: 排序完成的数组
    """
    for i in range(len(need_sortlist) - 1):
        for j in range(len(need_sortlist) - 1 - i):
            if need_sortlist[j] > need_sortlist[j + 1]:
                need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j]
    return need_sortlist


# print(bubble_sort(need_sortlist))

def bubble_sort1(need_sortlist: List[int]) -> List[int]:
    """
    冒泡排序朴素版优化
    1.当待排序数组已经有序，冒泡排序仍未执行完毕时，我们让函数每一轮比较结束后都判断数组是否有序，如果有序，则直接结束函数循环
    时间复杂度O(n^2)
    :param need_sortlist:待排序的数组
    :return: 排序完成的数组
    """
    #   控制外层循环
    for i in range(len(need_sortlist) - 1):
        #   每次大循环我们都认定数组已经有序
        isorted = True
        #   控制内层比较
        for j in range(len(need_sortlist) - 1 - i):
            if need_sortlist[j] > need_sortlist[j + 1]:
                need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j]
                #   一旦发生元素交换，说明数组仍无序
                isorted = False
        if isorted:
            break
    return need_sortlist


def bubble_sort2(need_sortlist: List[int]) -> List[int]:
    """
    冒泡排序朴素版优化
    1.当待排序数组已经有序，冒泡排序仍未执行完毕时，我们让函数每一轮比较结束后都判断数组是否有序，如果有序，则直接结束函数循环
    时间复杂度O(n^2)
    2.设计有序边界，避免数组实际有序区域大于冒泡排序逻辑有序区域
    :param need_sortlist:待排序的数组
    :return: 排序完成的数组
    """
    sorted_border = len(need_sortlist) - 1
    last_change_index = 0
    #   控制外层循环
    for i in range(len(need_sortlist) - 1):
        #   每次大循环我们都认定数组已经有序
        isorted = True
        #   控制内层比较
        for j in range(sorted_border):
            if need_sortlist[j] > need_sortlist[j + 1]:
                need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j]
                #   一旦发生元素交换，说明数组仍无序
                isorted = False
                #   记录并更新最后一次元素交换的位置
                last_change_index = j
        #   将有序边界设定为最后一次元素交换的位置
        sorted_border = last_change_index
        # print(sorted_border)
        if isorted:
            break
    return need_sortlist


# print(bubble_sort2(need_sortlist))

def cocktail_sort(need_sortlist: List[int]) -> List[int]:
    """
    鸡尾酒排序
    :param need_sortlist:待排序的数组
    :return: 排序完成的数组
    """
    #   记录大循环次数
    times = 0
    #   记录向左比较时交换元素的位置
    left_lastchange_index = 0
    #   记录向右比较时交换元素的位置zz
    right_lastchange_index = 0
    #   左有序边界
    leftsorted_border = 0
    #   右有序边界
    rightsorted_border = len(need_sortlist) - 1

    for i in range(len(need_sortlist) - 1):
        times = i
        #   默认有序
        issorted = True
        #   奇数次大循环，从左至右
        if (i + 1) % 2 != 0:
            # print(leftsorted_border,rightsorted_border)
            for j in range(leftsorted_border, rightsorted_border):
                if need_sortlist[j] > need_sortlist[j + 1]:
                    need_sortlist[j], need_sortlist[j + 1] = need_sortlist[j + 1], need_sortlist[j]
                    #   发生元素交换
                    issorted = False
                    left_lastchange_index = j
            if issorted:
                break
        #   偶数次大循环，从右至左
        else:
            for j in range(rightsorted_border, leftsorted_border, -1):
                if need_sortlist[j] < need_sortlist[j - 1]:
                    need_sortlist[j], need_sortlist[j - 1] = need_sortlist[j - 1], need_sortlist[j]
                    #   发生元素交换
                    issorted = False
                    right_lastchange_index = j
            if issorted:
                break

            leftsorted_border = left_lastchange_index
            rightsorted_border = right_lastchange_index

    print("共大循环%s次" % times)
    return need_sortlist


print(cocktail_sort(need_sortlist))

2.计数排序与桶排序

'''
@Author : "HCL"
计数排序&桶排序
'''
from typing import List


def count_sort(need_sortlist: List[int]) -> List[int]:
    """
    计数排序
    适用于
    1.整数排序。当数列元素不是整数时，不适合用计数排序。
    2.数值区间小。当数列最大和最小值差距过大时，不适合用计数排序。

    :param need_sortlist:
    :return:
    """
    #   创建结果数组
    res = [0 for i in range(len(need_sortlist))]
    #   获得数组最大值
    max_val = max(need_sortlist)
    #   获得数组最小值
    min_val = min(need_sortlist)
    #   创建计数数组，数组的长度等于最大值减去最小值+1，初始所有元素为0
    #   元素值的含义为当前元素的下标在待排序数组中出现的次数
    countlist = [0 for i in range(max_val - min_val + 1)]
    #   排序数组中  元素值 - 基准值 = 下标，
    for i in need_sortlist:
        countlist[i - min_val] += 1
    #   计数数组元素值累加，代表下标在完成排序后数组中的*位次*
    for i in range(1, len(countlist)):
        countlist[i] += countlist[i - 1]
    #   逆序遍历待排序数组，在结果数组对应 *位次* 填入元素
    for i in need_sortlist[-1::-1]:
        res[countlist[i - min_val] - 1] = i
        #   相同元素值每填入一个，位次-1
        countlist[i - min_val] -= 1

    return res


# print(count_sort([95, 94, 91, 98, 99, 90, 99, 93, 91, 92]))

def bucket_sort(need_sortelist: list) -> list:
    """
    桶排序
    :param need_sortelist: 待排序的数组
    :return: 排序完成的数组
    """
    res = []
    #   数组最大值
    max_val = max(need_sortelist)
    #   数组最小值
    min_val = min(need_sortelist)
    #   桶的数量
    bucket_num = len(need_sortelist)
    #   桶的区间跨度
    d = float(max_val - min_val) / (bucket_num - 1)

    #   创建桶
    bucket = [[] for i in range(bucket_num)]

    #   向桶里添加元素
    for i in need_sortelist:
        if i == min_val:
            bucket[0].append(i)
            continue
        n = int((i - min_val) / d)
        bucket[n - 1].append(i)
    # print(bucket)

    #   对每个桶里的元素排序
    for i in range(len(bucket)):
        #   sorted() O(nlogn)
        bucket[i] = sorted(bucket[i])
    # print(bucket)
    #   遍历桶，依次输出
    for i in bucket:
        res.extend(i)
    return res


print(bucket_sort([4.12, 6.421, 0.0023, 3.0, 2.123, 8.122, 4.12, 10.09]))

3.快速排序

'''
@Author : "HCL"
利用递归分治的思想，快速排序
'''
import time
from typing import List


def quicksort(need_sortlist: List[int]) -> List[int]:
    """
    快速排序，利用递归分治的思想
    :param need_sortlist:
    :return:
    """
    #   设置递归边界
    if len(need_sortlist) < 2:
        return need_sortlist
    provit = need_sortlist[0]
    # print(provit)
    #   比基准小的元素
    small = [i for i in need_sortlist[1:] if i < provit]
    #   比基准大的元素
    big = [i for i in need_sortlist[1:] if i > provit]
    return quicksort(small) + [provit] + quicksort(big)