numberlist = [1,4,7,8,9,0,2,5,6,3]
"""
冒泡排序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
"""
def bubble_sort(bumberlist):
    length = len(numberlist)
    for i in range(length):
        for j in range(1,length - i):
            if numberlist[j - 1] > numberlist[j]:
                numberlist[j],numberlist[j - 1] = numberlist[j - 1],numberlist[j]
    return numberlist

"""
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下:
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
"""
def selectSort(array):
    n = len(array)
    for i in range(n):
        minNum = array[i]
        minIndex = i
        for j in range(i+1, n):
            if array[j] < minNum:
                minIndex = j
                minNum = array[j]
        array[i], array[minIndex] = array[minIndex], array[i]
    return array

"""
插入排序
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
"""
def insert_sort(numberlist):
    for k in range(1,len(numberlist)):
        cur = numberlist[k]
        j = k
        while j > 0 and numberlist[j - 1] > cur:
            numberlist[j] = numberlist[j - 1]
            j -= 1
        numberlist[j] = cur
    return numberlist

"""
希尔排序
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，
重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。
最后整个表就只有一列了。
将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
"""
def shell_sort(numberlist):
    n = len(numberlist)
    gap = round(n / 2)
    while gap > 0:
        for i in range(gap,n):
            temp = numberlist[i]
            index = i
            while index >= gap  and numberlist[index - gap] > temp:
                numberlist[index] = numberlist[index - gap]
            numberlist[index] = temp
        gap = round(gap / 2)
    return numberlist

"""
归并排序
思路：拆拆拆到单个数字，合并合并合并
归并排序是采用分治法的一个非常典型的应用。
归并排序的思想就是先递归分解数组，再合并数组。
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，
谁小就先取谁，取了后相应的指针就往后移一位。
然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，
如果这两个数组内部数据是有序的，
那么就可以用上面合并数组的方法将这两个数组合并排序。
如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，
此时认为该小组内部已有序。然后合并排序相邻二个小组即可。
"""
def merge_sort(array):
    if len(array) <= 1: return array
    num = len(array) // 2
    left = merge_sort(array[:num])
    right = merge_sort(array[num:])
    return merge(left, right)

def merge(left, right):
    l,r = 0,0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l = l + 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

"""
快速排序
快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，
而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。
可见掌握快排的重要性。
快排特点：
每经过一趟快排，轴点元素都必然就位，也就是说，
一趟下来至少有关键字key节点在其最终位置，所以考察各个选项，看有几个元素就位即可。
逆序的数列，选择首位为key，则会退化到O（n^2），
可以随机选择一个元素作为基准元素。
"""
#python指针交换法
def quick_sort(array):
    return _quick_sort(array, 0, len(array) - 1)
def _quick_sort(array, left, right):
    if left >= right: return array
    key = array[left]
    lp = left
    rp = right
    while (lp < rp):
        while array[rp] >= key and lp < rp:
            rp -= 1
        while array[lp] <= key and lp < rp:
            lp += 1
        array[lp], array[rp] = array[rp], array[lp]
    array[left], array[lp] = array[lp], array[left]
    _quick_sort(array, left, lp - 1)
    _quick_sort(array, lp + 1, right)
    return array

"""
堆排序
"""
def MAX_Heapify(heap, HeapSize, root):  # 在堆中做结构调整使得父节点的值大于子节点

    left = 2 * root + 1
    right = left + 1
    larger = root
    if left < HeapSize and heap[larger] < heap[left]:
        larger = left
    if right < HeapSize and heap[larger] < heap[right]:  # 确定到底和左还是右节点换，先判断做节点
        larger = right
    if larger != root:  # 如果做了堆调整：则larger的值等于左节点或者右节点的，这个时候做对调值操作
        heap[larger],heap[root] = heap[root],heap[larger]
        MAX_Heapify(heap, HeapSize, larger)  # 从顶端递归往下调整，用larger是因为larger是数组索引，并且已经在比较时候更新过，而root没有更新过！

def Build_MAX_Heap(heap):  # 构造一个堆，将堆中所有数据重新排序
    HeapSize = len(heap)
    for i in range(((HeapSize - 1) - 1) // 2,-1,-1):  # 从后往前出数(z最后一个节点的父节点)  '//' got integer
        MAX_Heapify(heap,HeapSize,i)  # 这里堆的大小是固定，root是i逐步减小

def HeapSort(heap):  # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
    Build_MAX_Heap(heap)
    for i in range(len(heap) - 1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        MAX_Heapify(heap, i, 0)  # 这里堆的大小是逐步缩小，root永远是0
    return heap

"""
计数排序
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
"""
def count_sort(ary):
    max = min = 0  # min和max应该用sys.maxint
    for i in ary:
        if i < min:
            min = i
        if i > max:
            max = i 
    count = [0] * (max - min +1)
    for index in ary:
        count[index - min] += 1
    index=0
    for a in range(max - min + 1):
        for c in range(count[a]):  # 重点：有多少个就for循环多少次
            ary[index] = a + min
            index += 1
    return ary

"""
双向冒泡排序
"""
def double_bubble_sort(number_list:list) -> list:
    #列表开始的索引
    low = 0
    #列表末尾的索引
    high = len(number_list) - 1
    #开始循环，每一次排序好两个数字
    while low < high:
        #用作退出循环的标志
        flag = 0
        #正向冒泡，找到剩下数字中最大的，将其排到“末尾”
        for i in range(low,high):
            if number_list[i] > number_list[i + 1]:
                number_list[i],number_list[i + 1] = number_list[i + 1],number_list[i]
                #存在数据交换就改变flag
                flag = 1
        #不存在数据交换，即排序完成时跳出循环
        if flag == 0:
            break
        #末尾索引减少1
        high = high - 1
        #反向冒泡，找到剩下数字中最小的，将其排到“开头”
        for i in range(high,low,-1):
            if number_list[i] < number_list[i - 1]:
                number_list[i],number_list[i - 1] = number_list[i - 1],number_list[i]
        #开头索引增加1
        low += 1
    #排序完成，返回列表
    return number_list
"""
桶排序
"""
"""
基数排序
"""

if __name__ == '__main__':
    print('冒泡排序:\n' + str(bubble_sort(numberlist)))
    print('选择排序:\n' + str(selectSort(numberlist)))
    print('插入排序:\n' + str(insert_sort(numberlist)))
    print('希尔排序:\n' + str(shell_sort(numberlist)))
    print('归并排序:\n' + str(merge_sort(numberlist)))
    print('快速排序:\n' + str(quick_sort(numberlist)))
    print('堆排序:\n' + str(HeapSort(numberlist)))
    print('计数排序:\n' + str(count_sort(numberlist)))
    print('计数排序:\n' + str(double_bubble_sort([8,6,4,3,9,1,2,5,7])))
    #print(numberlist)