#!/usr/bin/env python
# @Desc    : 各種排序算法

# 插入排序
def InserteSort(arr):
    """插入直到1"""
    if not arr:
        return []
    for i in range(len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    print(arr)

# 選擇排序
def SelectSort(arr):
    if not arr:
        return []
    for start in range(len(arr)):
        amin = start
        for i in range(start, len(arr)):
            if arr[i] < arr[amin]:
                amin = i
        arr[amin], arr[start] = arr[start], arr[amin]
    print(arr)

# 冒泡排序
def BubblingSort(arr):
    """在尾部進行選擇排序"""
    if not arr:
        return []
    for end in range(len(arr)-1, -1, -1):
        flag = True
        for i in range(end):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                flag = False
        if flag:
            print('--', arr)
    print(arr)

# 快速排序 遞歸 space(n)
def QuickSort_rec(arr):
    if not arr:
        return []
    target = arr[-1]
    left = [x for x in arr if x < target]
    mid = [x for x in arr if x == target]
    right = [x for x in arr if x > target]
    return QuickSort_rec(left) + mid + QuickSort_rec(right)

# 原地快排, 需要用到partition函數(shù)
def QuickSort(arr, left, right):
    if left < right:
        L, R = partition(arr, left, right)
        QuickSort(arr, left, L-1)
        QuickSort(arr, R+1, right)
# space O(1)
def partition(arr, left, right):
    cur = left
    target = right
    while left < right:
        if arr[cur] > arr[target]:
            right -= 1
            arr[cur], arr[right] = arr[right], arr[cur]
        elif arr[cur] == arr[target]:
            cur += 1
        elif arr[cur] < arr[target]:
            arr[cur], arr[left] = arr[left], arr[cur]
            cur += 1
            left += 1
    arr[target], arr[right] = arr[right], arr[target]
    return left, right

# 歸并排序 O(nlogn) space O(n)
def mergeSort(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    result = []
    while left and right:
        if left[0] > right[0]:
            result.append(right.pop(0))
        else:
            result.append(left.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

# !!!堆排序
# 大的向上跑
def heapCreate(arr, idx):
    """組建大根堆"""
    while arr[idx] > arr[int((idx - 1) / 2)]:
        arr[idx], arr[int((idx - 1) / 2)] = arr[int((idx - 1) / 2)], arr[idx]
        idx = int((idx - 1) / 2)
# 大的向下跑
def heapify(arr, idx, size):
    """找到最大的放在上面用于交換,放到序列尾部"""
    left = idx * 2 + 1
    while left < size:
        # 左右誰最大
        largest = left + 1 if left + 1 < size and arr[left+1] > arr[left] else left
        # 孩子和父親誰大
        largest = largest if arr[largest] > arr[idx] else idx
        if largest == idx:
            break
        # 交換
        arr[idx], arr[largest] = arr[largest], arr[idx]
        idx = largest
        left = idx * 2 + 1
def heapSort(arr):
    # O(n)
    for i in range(len(arr)):
        heapCreate(arr, i)
    print("HeapInsert:", arr)
    size = len(arr) - 1
    # O(logn)
    while size > 0:
        arr[0], arr[size] = arr[size], arr[0]
        size -= 1
        heapify(arr, 0, size)
    print(arr)

if __name__ == '__main__':
    import random
    a = [7, 5, 4, 3, 2, 1]
    random.shuffle(a)
    print('raw:', a)
    heapSort(a)