def selection_sort(gList):
    """选择排序
    :param gList: 给定的一组序列
    :return: 返回排好序的序列
    """
    length = len(gList)
    for i in range(length - 1):
        flag = i
        for j in range(i+1, length):
            if gList[flag] > gList[j]:
                flag = j
        # 如果最小值的索引与最小值相对应，则无需再次交换
        if flag != i:
            gList[flag], gList[i] = gList[i], gList[flag]

    return gList
    

def bubble_sort(gList):
    """冒泡排序"""
    length = len(gList)
    for i in range(length):
        for j in range(i+1, length):
            if gList[i] > gList[j]:
                gList[i], gList[j] = gList[j], gList[i]
    return gList

def insertion_sort(gList):
    """插入排序"""
    length = len(gList)
    for i in range(1, length):
        temp = gList[i]  # 当前的待插入的值
        j = i - 1  # 前一个值
        while j >= 0:
            if gList[j] > temp:
                gList[j+1] = gList[j]  # 插入的动作
                gList[j] = temp  # 插入完毕
            j -= 1
    return gList

def merge_sort(gList: list) -> list:
    """归并排序
    :param gList: 给定序列
    :return: 升序排列后的集合
    """

    def merge(left: list, right: list) -> list:
        """merge left and right
        :param left: left list
        :param right: right list
        :return: merge reslut
        """
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result

    if len(gList) <= 1:
        return gList
    num = len(gList) // 2
    left = merge_sort(gList[:num])
    right = merge_sort(gList[num:])
    return merge(left, right)


if __name__ == '__main__':
    gList = [3, 5, 2, 4, 1]
    print("----排序前:", gList)
    print("----归并排序后: ", merge_sort(gList))

# -*- coding: utf-8 -*-

def quick_sort(gList, left=0, right=None) -> list:
    """快速排序
    :param gList: 给定一组序列
    :param left:
    :param right:
    :return: 升序排序后的序列
    """
    if right is None:
        right = len(gList)-1

    if left > right:
        return gList

    key = gList[left]
    low = left
    high = right

    while left < right:
        while left < right and gList[right] >= key:
            right -= 1
        gList[left] = gList[right]

        while left < right and gList[left] <= key:
            left += 1
        gList[right] = gList[left]
    gList[right] = key
    quick_sort(gList, low, left-1)
    quick_sort(gList, left+1, high)
    return gList


if __name__ == '__main__':
    gList = [3, 5, 2, 4, 1, 6, 7]
    print("----排序前:", gList)
    print("----快速排序后: ", quick_sort(gList))

# -*- coding: utf-8 -*-
def shell_sort(gList) -> list:
    """希尔排序"""
    length = len(gList)
    step = 2
    group = length // step
    while group > 0:
        for startPos in range(group):
            gap_insertion_sort(gList, startPos, group)
        group = group // 2
    return gList


def gap_insertion_sort(gList, start, gap):
    for i in range(start+gap, len(gList), gap):
        curr_value = gList[i]
        pos = i

        while pos >= gap and gList[pos-gap] > curr_value:
            gList[pos] = gList[pos-gap]
            pos = pos - gap
        gList[pos] = curr_value


if __name__ == '__main__':
    gList = [5, 4, 2, 1, 7, 3, 6]
    print("-----yuzhou1su-----", gList)
    print("-----希尔排序后:", shell_sort(gList))

def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index

    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index

    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)


def heap_sort(unsorted):
    """堆排序"""
    length = len(unsorted)
    for i in range(length // 2 - 1, -1, -1):
        heapify(unsorted, i, length)
    for i in range(length - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted


if __name__ == '__main__':
    gList = [5, 4, 2, 1, 7, 3, 6]
    print("-----yuzhou1su-----", gList)
    print("-----堆排序后:", heap_sort(gList))

# -*- coding: utf-8 -*-
# @Time      : 2020-09-10 14:31
# @Author    : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File      : counting_sort.py
# @Software  : PyCharm


def counting_sort(unsorted):
    """计数排序
    :param unsorted：给定一组序列
    :return: 升序序列
    """
    if unsorted is []:
        return []
    # 根据给定序列求信息
    coll_len = len(unsorted)
    coll_max = max(unsorted)
    coll_min = min(unsorted)

    # 创建计数数组
    counting_arr_length = coll_max + 1 - coll_min
    counting_arr = [0] * counting_arr_length

    # 计数操作
    for number in unsorted:
        counting_arr[number - coll_min] += 1

    # 将每个位置与它的前一个相加。counting_arr[i]统计出多少个
    # element <= i的元素
    for i in range(1, counting_arr_length):
        counting_arr[i] = counting_arr[i] + counting_arr[i - 1]

    # 创建保存升序结果的数组
    ordered = [0] * coll_len
    for i in reversed(range(0, coll_len)):
        ordered[counting_arr[unsorted[i] - coll_min] - 1] = unsorted[i]
        counting_arr[unsorted[i] - coll_min] -= 1

    return ordered


if __name__ == '__main__':
    gList = [5, 4, 2, 1, 3, 6]
    print("-----yuzhou1su：", gList)
    print("-----计数排序后:", counting_sort(gList))

# -*- coding: utf-8 -*-
# @Time      : 2020-09-10 15:30
# @Author    : yuzhou_1su
# @ContactMe : www.yuzhou_1su@163.com
# @File      : bucket_sort.py
# @Software  : PyCharm
import math


def insertion_sort(collection):
    for i in range(1, len(collection)):
        temp = collection[i]
        index = i
        while index > 0 and temp < collection[index - 1]:
            collection[index] = collection[index-1]
            index -= 1
        collection[index] = temp


def bucket_sort(collection):
    code = hashing(collection)
    buckets = [list() for _ in range(code[1])]
    for i in collection:
        x = rehashing(i, code)
        buck = buckets[x]
        buck.append(i)

    for bucket in buckets:
        insertion_sort(bucket)

    ndx = 0
    for buc in range(len(buckets)):
        for val in buckets[buc]:
            collection[ndx] = val
            ndx += 1
    return collection


def hashing(collection):
    m = collection[0]
    for i in range(1, len(collection)):
        if m < collection[i]:
            m = collection[i]
    result = [m, int(math.sqrt(len(collection)))]
    return result


def rehashing(i, code):
    return int(i / code[0] * (code[1] - 1))


if __name__ == '__main__':
    gList = [5, 4, 2, 1, 3, 6]
    print("-----yuzhou1su：", gList)
    print("-----桶排序后:", bucket_sort(gList))

def radix_sort(unsorted):
    radix = 10
    max_len = False
    tmp, placement = -1, 1
    while not max_len:
        max_len = True
        buckets = [list() for _ in range(radix)]
        for i in unsorted:
            tmp = int(i / placement)
            buckets[tmp % radix].append(i)
            if max_len and tmp > 0:
                max_len = False
        a = 0
        for b in range(radix):
            buck = buckets[b]
            for i in buck:
                unsorted[a] = i
                a += 1
        # move to next digit
        placement *= radix
    return unsorted


if __name__ == '__main__':
    gList = [5, 4, 2, 1, 3, 6]
    print("-----yuzhou1su：", gList)
    print("-----基数排序后:", radix_sort(gList))