# -*- coding: utf-8 -*-
from __future__ import print_function
import random


def func(a, b, reversed):
    return a < b if reversed else a > b


def insertSort(unsorted_list, reversed=False):
    '''
    直接插入排序
    把 n 个待排序的元素看成一个有序表和一个无序表，
    开始时有序表中只有一个元素，无序表中有 n-1 个元素。
    排序过程即每次从无序表中取出第一个元素，
    将它插入到有序表中，使之成为新的有序表，重复 n-1 次完成整个排序过程。
    '''
    print("raw: ", unsorted_list)

    for i in range(1, len(unsorted_list)):
        j = i-1
        cmp = unsorted_list[i]

        while j > -1 and func(unsorted_list[j], cmp, reversed):
            unsorted_list[j+1], unsorted_list[j] = unsorted_list[j], cmp
            j -= 1
        print("NO.%d:" % i, unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def shellSort(unsorted_list, reversed=False):
    '''
    希尔排序是一种插入排序算法，又称作缩小增量排序。是对直接插入排序算法的改进。其基本思想是： 
    先取一个小于 n 的整数作为第一个增量，把全部数据分成个组。所有距离为的倍数的记录放在同一个组中。
    先在各组内进行直接插入排序；
    然后，取第二个增量重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。
    该方法实质上是一种分组插入方法。
    1 2 3 4 5 6 7 8 9 10 11
    -----------
      -----------
        -----------
    '''
    print("raw: ", unsorted_list)
    n = len(unsorted_list)/2
    num = 1
    while n:
        for ni in range(n):
            group = range(ni, len(unsorted_list), n)
            for i in range(1, len(group)):
                j = i-1
                cmp = unsorted_list[group[i]]
                while j > -1 and func(unsorted_list[group[j]], cmp, reversed):
                    unsorted_list[group[j+1]], unsorted_list[group[j]] = unsorted_list[group[j]], cmp
                    j -= 1

        print("NO.%d:" % num, unsorted_list)
        n /= 2
        num += 1
    print("last:", unsorted_list)
    return unsorted_list


def selectSort(unsorted_list, reversed=False):
    '''
    每一趟从待排序的数据元素中选出最小（最大）的元素，
    顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。
    一共需要 n-1 趟
    '''
    print("raw: ", unsorted_list)
    for loc in range(len(unsorted_list)-1):
        for i in range(loc, len(unsorted_list)):
            if func(unsorted_list[loc], unsorted_list[i], reversed):
                unsorted_list[i], unsorted_list[loc] = unsorted_list[loc], unsorted_list[i]
        print("NO.%d:" % loc, unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def heapSort(unsorted_list, reversed=False):
    '''
    堆排序涉及到的概念
    - 堆排序是利用 堆进行排序的
    - 堆是一种完全二叉树
    - 堆有两种类型: 大根堆 小根堆
    - 两种类型的概念如下：
        - 大根堆：每个结点的值都大于或等于左右孩子结点
        - 小根堆：每个结点的值都小于或等于左右孩子结点

    首先将待排序的数组构造出一个大根堆
    取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，
    然后把剩下的元素再构造出一个大根堆。
    重复第二步，直到这个大根堆的长度为 1，此时完成排序。

    例子：
     1  2   3  4  5  6  7  8  9  10
    [3, 4, 10, 6, 8, 2, 5, 1, 7, 9]

            3
       4        10
     6   8    2    5
    1 7 9 x  x x  x x

    规律：
    - 如何找到 6 这个节点：(length-1)/2 => (10-1)/2=4
    - https://www.jianshu.com/p/d174f1862601
    '''

    def heap_adjust(L, start, end):
        temp = L[start]
        i = start
        j = 2 * i
        while j <= end:
            if (j < end) and func(L[j+1], L[j], reversed):
                j += 1
            if func(L[j], temp, reversed):
                L[i], i, j = L[j], j, 2*j
            else:
                break
        L[i] = temp

    print("raw: ", unsorted_list)
    unsorted_list.insert(0, 0)
    L_length = len(unsorted_list) - 1

    first_Sort_count = L_length / 2
    for i in range(first_Sort_count):
        heap_adjust(unsorted_list, first_Sort_count - i, L_length)

    print("Heap:", unsorted_list[1:])
    for i in range(L_length - 1):
        unsorted_list[1], unsorted_list[L_length -
                                        i] = unsorted_list[L_length - i], unsorted_list[1]
        heap_adjust(unsorted_list, 1, L_length - i - 1)
        print("No.%d:" % i, unsorted_list[1:])

    unsorted_list.pop(0)
    print("last:", unsorted_list)
    return unsorted_list


def bubbleSort(unsorted_list, reversed=False):
    '''
    S1：从待排序序列的起始位置开始，从前往后依次比较各个位置和其后一位置的大小并执行 S2。 
    S2：如果当前位置的值大于其后一位置的值，就把他俩的值交换
       （完成一次全序列比较后，序列最后位置的值即此序列最大值，所以其不需要再参与冒泡）。 
    S3：将序列的最后位置从待排序序列中移除。若移除后的待排序序列不为空则继续执行 S1，否则冒泡结束。
    '''
    print("raw: ", unsorted_list)
    num = 0
    while len(unsorted_list)-num:
        for i in range(0, len(unsorted_list)-num-1):
            if func(unsorted_list[i], unsorted_list[i+1], reversed):
                unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]

        print("No.%d:" % num, unsorted_list)
        num += 1

    print("last:", unsorted_list)


def quickSort(unsorted_list, base_loc=0, reversed=False):
    '''
    快速排序是对冒泡排序的一种改进。
    基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
    其中一部分的所有数据都比另外一部分的所有数据都要小，
    然后再按此方法对这两部分数据分别进行快速排序，
    整个排序过程可以递归进行，以此实现整个数据变成有序序列。
    '''
    print("raw: ", unsorted_list)
    num = [0]

    def _sort(l, r):
        if l < r:
            if num[0]:
                print("No.%d:" % num[0], unsorted_list)
            num[0] += 1
            if base_loc:
                q = partition_final(unsorted_list, l, r)
            else:
                q = partition_first(unsorted_list, l, r)
            _sort(l, q - 1)
            _sort(q + 1, r)

    def partition_final(unsorted_list, l, r):
        x = unsorted_list[r]
        i = l - 1
        for j in range(l, r):
            if x > unsorted_list[j]:
                i += 1
                unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
        unsorted_list[i+1], unsorted_list[r] = unsorted_list[r], unsorted_list[i+1]
        return i+1

    def partition_first(unsorted_list, l, r):
        x = unsorted_list[l]
        i = r + 1
        for j in range(r, l, -1):
            if x < unsorted_list[j]:
                i -= 1
                unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
        unsorted_list[i-1], unsorted_list[l] = unsorted_list[l], unsorted_list[i-1]
        return i-1

    _sort(0, len(unsorted_list)-1)
    print("last:", unsorted_list)


def mergeSort(unsorted_list, reversed=False):
    '''
    合并两个已排序好的列表，产生一个新的已排序好的列表
    归并排序的算法我们通常用递归实现。
    先把待排序区间[s,t]以中点二分，接着把左边子区间排序，
    再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
    '''
    print("raw: ", unsorted_list)

    def _sort(unsorted_list):
        if len(unsorted_list) <= 1:
            return unsorted_list

        mid = len(unsorted_list) / 2
        left = _sort(unsorted_list[:mid])
        right = _sort(unsorted_list[mid:])
        result = merge(left, right)
        return result

    def merge(left, right):
        result = []  # 新的已排序好的列表

        left = left[::-1]
        right = right[::-1]

        while left and right:
            left_num = left.pop()
            right_num = right.pop()

            if func(right_num, left_num, reversed):
                result.append(left_num)
                right.append(right_num)
            else:
                result.append(right_num)
                left.append(left_num)

        return result+left[::-1]+right[::-1]

    unsorted_list = _sort(unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def bucketSort(unsorted_list, reversed=False):
    '''
    桶排序
    '''
    print("raw: ", unsorted_list)
    buckets = [0] * ((max(unsorted_list)-min(unsorted_list))+1)
    for num in unsorted_list:
        buckets[num-min(unsorted_list)] += 1

    unsorted_list = sum([[i+min(unsorted_list)]*num for i, num in enumerate(buckets)], [])
    print("last:", unsorted_list)


def radixSort(unsorted_list, reversed=False):
    '''
    将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
    然后，从最低位开始，依次进行一次排序。
    这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
    '''
    import math

    for i in range(int(math.log10(max(unsorted_list)))+1):
        bucket = [[] for _ in range(10)]
        for val in unsorted_list:
            bucket[int(val % (10 ** (i+1)) / (10 ** i))].append(val)

        unsorted_list = sum(bucket, [])

    if reversed:
        unsorted_list = unsorted_list[::-1]

    print(unsorted_list)
    return unsorted_list

unsorted_list = range(10, 0, -1)
random.shuffle(unsorted_list)

# insertSort(unsorted_list)
# shellSort(unsorted_list)
# selectSort(unsorted_list)
# heapSort(unsorted_list)
# bubbleSort(unsorted_list)
# quickSort(unsorted_list)
# mergeSort(unsorted_list)
# bucketSort(unsorted_list)
# radixSort(unsorted_list)