# 1. 选择排序：循环找最小值，依次放在左侧
def select_sort(arr):
    for i in range(len(arr)-1):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if i != min_index:
            # 交换两个元素位置
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


# 2. 冒泡排序
# 和插入排序相同点: 都是循环比较相邻的两个元素
# 不同点：每次循环只会和后面的一个元素比大小，不会和前面的元素比较
# 特点: 每次循环把最大值依次放在后面
def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


# 3. 插入排序：
# 循环比较相邻的两个元素，小的放左边；如果交换后发现左侧还有小元素，继续交换位置

def insert_sort(arr):
    for i in range(len(arr)):
        pre_index = i - 1
        current = arr[i]
        while pre_index >= 0 and arr[pre_index] > current:
            arr[pre_index+1] = arr[pre_index]
            pre_index -= 1
        arr[pre_index+1] = current
    return arr


# 4. 希尔排序，插入排序的升级
def shell_sort(arr):
    meta = 2
    n = len(arr)
    gap = int(n // meta)
    while gap > 0:
        for i in range(gap, n):
            current = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > current:
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = current

        gap = int(gap//meta)
    return arr


# 5. 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]  # 取最后一个数作为pivot
    i = 0  # i记录比pivot小的数的个数
    j = 0  # j用来遍历整个数列
    n = len(arr)

    while j < n-1:
        if arr[j] < pivot:   # 比pivot小的放前面
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
        j += 1
    arr[i], arr[-1] = arr[-1], arr[i]

    if i > 0:
        # 比pivot小的数据不为空， 则对其进行快速排序
        arr[:i] = quick_sort(arr[:i])
    if i+1 < n:
        # 比pivot大的数据不为空， 则对其进行快速排序
        arr[i+1:] = quick_sort(arr[i+1:])
    return arr


# 6. 归并排序
def mergeSort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr) // 2
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(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))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


# 7. 堆排序, 理解视频：https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=4983284716020974089
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    for i in range(n, -1, -1):  # 递减的时候，第2个值-1表示到0结束，包括0
        heapify(arr, n, i)

        # 一个个交换元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)
    return arr


# 8.计数排序
# https://blog.csdn.net/weixin_43790276/article/details/107398262
def counting_sort(arr):
    if len(arr) < 2:
        return arr
    max_num = max(arr)
    count = [0] * (max_num + 1)  # 新建一个计数列表，长度为待排序列表最大值加1。
    for num in arr:
        count[num] += 1  # 把待排序元素值当作count列表的下标，计算每个待排序元素重复的次数
    new_arr = list()
    for i in range(len(count)):
        for j in range(count[i]):  # count[i]就是count列表中元素i重复的次数
            new_arr.append(i)
    return new_arr


# 9 基数排序

# coding=utf-8
def radix_sort(array):
    # 找出带排序元素最大数有几位
    max_num = max(array)
    place = 1
    while max_num >= 10**place:
        place += 1

    for i in range(place):
        # 当i=0时，找个位的基数都有哪些；当i=1时，找十位的基数都有哪些
        buckets = [[] for _ in range(10)]
        for num in array:
            radix = int(num/(10**i) % 10)
            buckets[radix].append(num)

        # 按基数对元素进行排序
        j = 0
        for k in range(10):
            for num in buckets[k]:
                array[j] = num
                j += 1
    return array



a = [1, 4, 9, 3, 5]
# x = bubble_sort(a)
#x = mergeSort(a)
#x = heapSort(a)
x = counting_sort(a)
print(x)