import random


'''
    冒泡排序
    1. 循环数组，从左向右开始，比较A1与A2的值，如果A1>A2，则交换A1与A2的位置，再比较A2与A3的大小，如A2>A3..
    2. 以此类推，第一次循环结束时最大的数字已经在最右边，循环n-1次，即排序结束
'''


def bubble_sort(sort_list):
    bubble_list_length = len(sort_list)
    while bubble_list_length > 0:
        for _i in range(0, bubble_list_length-1):
            if sort_list[_i] > sort_list[_i + 1]:
                sort_list[_i], sort_list[_i +
                                         1] = sort_list[_i+1], sort_list[_i]
        bubble_list_length -= 1
    return sort_list


'''
    插入排序
    1. 获取数组长度n，循环range(1,n)，获得A0，A1，比较A0,A1大小并交换位置
    2. 第二次循环，获得A0,A1,A2，比较A0,A1,A2，从右往左比较交换位置，以此类推
'''


def insert_sort(sort_list):
    length = len(sort_list)
    for i in range(1, length):
        for j in range(i, 0, -1):
            if sort_list[j] < sort_list[j-1]:
                sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
    return sort_list


'''
    希尔排序
    1. 改良版插入排序，基本等同于插入排序的分组
'''


def diminishing_increment_sort(sort_list):
    length = len(sort_list)
    h = 1
    while h < length/3:
        h = 3*h+1
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and sort_list[j] < sort_list[j-h]:
                sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j]
                j -= h
        h = h//3
    return sort_list


'''
    快速排序
    1. 取任意一个数作为基准数（第一个/倒数第一均可），并在源数组中删除该数
    2. 建立两个新数组，分别为左数组和右数组
    3. 循环源数组，将每一个数与基准数进行比较，较小的归入左数组，较大的归入右数组
    4. 递归调用自身，将左数组跟右数组递归调用至数组大小小于2，将所有数组合并即可
'''


def quick_sort(sort_list):
    if len(sort_list) > 2:
        mid = sort_list[0]
        sort_list.remove(mid)
        left_list = []
        right_list = []
        for i in range(0, len(sort_list)):
            if sort_list[i] < mid:
                left_list.append(sort_list[i])
            if sort_list[i] > mid:
                right_list.append(sort_list[i])
        return quick_sort(left_list) + [mid] + quick_sort(right_list)
    else:
        return sort_list

'''
    直接选择排序
    1. 创建新数组，循环当前数据，pop出最小数，添加到新数组，以此类推
'''
def selection_sort(sort_list):
    def _select_min_number(temp_list):
        if len(temp_list) is 0:
            return None
        min_number = temp_list[0]
        for _n in temp_list:
            if _n < min_number:
                min_number = _n
        return min_number

    new_list = []
    length = len(sort_list)
    while length > 0:
        min_number = _select_min_number(sort_list)
        new_list.append(min_number)
        sort_list.remove(min_number)
        length -= 1
    return new_list

'''
    计数排序
    1. 新建一个一样大小的数组
    2. 循环旧数组，取出第一个数A1，再循环一遍旧数组，逐一比较，记所有小于A1的数为p，记所有等于A1的数为q
    3. 赋值给新数组下标为[p]-[p+q]范围的数为A1，以此类推
'''
def counting_sort(sort_list):
    length = len(sort_list)
    new_list = [None]*length
    for i in range(length):
        p = 0
        q = 0
        for j in range(length):
            if sort_list[j]<sort_list[i]:
                p+=1
            if sort_list[j]==sort_list[i]:
                q+=1
        for k in range(p,p+q):
            new_list[k] = sort_list[i]
    return new_list



if __name__ == '__main__':
    _range = 100
    length = 5
    _list = random.sample(range(_range), length)
    print('before sort is ', _list)
    _list = diminishing_increment_sort(_list)
    print('alter sort is', _list)