import random, time
# 生成隨機數組
def generate_random_array(size, lrange, rrange):
    return [random.randint(lrange, rrange) for i in range(size)]
# 判斷數組是否順序有序
def is_order_asc(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True
# 排序算法裝飾器
def sort(name):
    def decoration(sort_func):
        def wrapper(*dargs, **dkw):
            start_time = time.time()
            sort_func(*dargs, **dkw)
            if is_order_asc(*dargs):
                print(name + '：數組排序所需時間為:' + str((time.time() - start_time) * 1000) + '毫秒')
            else:
                print(name + '：數組排序失敗')
        return wrapper
    return decoration
@sort('冒泡排序')
def bubble_sort(arr):
    length = len(arr)
    for i in range(length - 1):
        for j in range(length - 1):
            if arr[j + 1] < arr[j]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
@sort('選擇排序')
def select_sort(arr):
    for i in range(len(arr) - 1):
        min = i
        for j in range(i + 1,len(arr)):
            if arr[j] < arr[min]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]
@sort('插入排序')
def insert_sort(arr):
    for i in range(1, len(arr)):
        insert_value = arr[i]
        for j in range(i, -1, -1):
            if arr[j - 1] <= insert_value:
                break
            arr[j] = arr[j - 1]
        arr[j] = insert_value
@sort('希爾排序')
def shell_sort(arr):
    h = 1
    while h * 3 + 1 < len(arr):
        h = h * 3 + 1
    while h > 0:
        for i in range(h, len(arr)):
            insert_value = arr[i]
            for j in range(i, -1, -h):
                if (arr[j - h] <= insert_value):
                    break
                arr[j] = arr[j - h]
            arr[j] = insert_value
        h = int((h - 1) / 3)
@sort('統計排序')
def count_sort(arr):
    min_value = arr[0]
    max_value = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > max_value:
            max_value = arr[i]
        elif arr[i] < min_value:
            min_value = arr[i]
        else:
            pass
    count = [0 for i in range(max_value - min_value + 1)]
    for i in arr:
        count[i - min_value] += 1
    index = 0
    for i in range(len(count)):
        for j in range(count[i]):
            arr[index] = i + min_value
            index += 1
@sort('快速排序')
def quick_sort(arr):
    quick(arr, 0, len(arr) - 1)
def quick(arr, start, end):
    if start >= end:
        return
    pivot_index = partition(arr, start, end)
    quick(arr, start, pivot_index - 1)
    quick(arr, pivot_index + 1, end)
def partition(arr, start, end):
    pivot = arr[start]
    mark = start
    for i in range(start + 1, end + 1):
        if arr[i] <= pivot:
            mark += 1
            arr[i], arr[mark] = arr[mark], arr[i]
    arr[start], arr[mark] = arr[mark], arr[start]
    return mark
@sort('歸并排序')
def merge_sort(arr):
    merge_sort2(arr, 0, len(arr) - 1)
def merge_sort2(arr, start, end):
    if start >= end:
        return
    middle = int((end - start) / 2) + start
    merge_sort2(arr, start, middle)
    merge_sort2(arr, middle + 1, end)
    merge(arr, start, middle, end)
def merge(arr, start, middle, end):
    copy = [arr[i] for i in range(start, end + 1)]
    left = start
    right = middle + 1
    index = start
    while left <= middle and right <= end:
        if copy[left - start] <= copy[right - start]:
            arr[index] = copy[left - start]
            left+=1
        else:
            arr[index] = copy[right - start]
            right+=1
        index+=1
    while left <= middle:
        arr[index] = copy[left - start]
        left+=1
        index+=1
    while right <= end:
        arr[index] = copy[right - start]
        right+=1
        index+=1
if __name__ == '__main__':
    bubble_sort(generate_random_array(10000, 0, 1000000))
    select_sort(generate_random_array(10000, 0, 1000000))
    insert_sort(generate_random_array(10000, 0, 1000000))
    shell_sort(generate_random_array(10000, 0, 1000000))
    count_sort(generate_random_array(10000, 50, 100))
    quick_sort(generate_random_array(10000, 0, 1000000))
    merge_sort(generate_random_array(10000, 0, 1000000))