#! /usr/bin/env python
# -*- coding: utf-8 -*-
# __author__ = "Q1mi"
# Email: master@liwenzhou.com

"""
冒泡排序
"""

import random
import time

def get_list(arg):
    """
    获得一个有指定个数的1000以内数字的列表
    :param arg: 期望获得的列表内数字的个数
    :return:
    """
    list_tmp = []
    for i in range(arg):
        list_tmp.append(random.randrange(100000))
    return list_tmp

def bubble_sort(arg):
    n = 0
    for i in range(len(arg)-1):
        n += 1
        for j in range(i+1, len(arg)):
            n += 1
            if arg[i] < arg[j]:
                arg[i], arg[j] = arg[j], arg[i]
    print("此次循环：{} 次。".format(n))
    return arg

if __name__ == "__main__":
    l1 = get_list(50000)
    start_time = time.time()
    l2 = bubble_sort(l1)
    end_time = time.time()
    print("此次耗时：{} 秒。".format(end_time-start_time))

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# __author__ = "Q1mi"
# Email: master@liwenzhou.com

"""
选择排序
"""

import random
import time

def get_list(arg):
    """
    获得一个有指定个数的1000以内数字的列表
    :param arg: 期望获得的列表内数字的个数
    :return:
    """
    list_tmp = []
    for i in range(arg):
        list_tmp.append(random.randrange(100000))
    return list_tmp

def selection_sort(arg):
    n = 0
    for i in range(len(arg)-1):
        n += 1
        index = i
        for j in range(i+1, len(arg)):
            n += 1
            # 从i之后的元素中找最小的，然后和arg[i]交换
            if arg[index] > arg[j]:
                index = j
        arg[i], arg[index] = arg[index], arg[i]
    print("此次循环：{} 次。".format(n))
    return arg

if __name__ == "__main__":
    l1 = get_list(50000)
    start_time = time.time()
    l2 = selection_sort(l1)
    end_time = time.time()
    print("此次耗时：{} 秒。".format(end_time-start_time))

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# __author__ = "Q1mi"
# Email: master@liwenzhou.com

"""
插入排序
"""

import random
import time

def get_list(arg):
    """
    获得一个有指定个数的1000以内数字的列表
    :param arg: 期望获得的列表内数字的个数
    :return:
    """
    list_tmp = []
    for i in range(arg):
        list_tmp.append(random.randrange(100000))
    return list_tmp

def insertion_sort(arg):
    n = 0
    for i in range(1, len(arg)):
        n += 1
        # 记下当前的索引
        index = i
        # 记下当前值
        current_value = arg[i]
        # 如果索引大于0，并且它前面已经排序了的列表的最后一个值比当前值大
        while index > 0 and arg[index-1] > current_value:
            # 就把它之前已经排序了的列表的值往后移一位
            arg[index] = arg[index-1]
            # 接着在已经排序的列表往前取值比较
            index -= 1
            n += 1
        # 如果索引=0或者当前的已经排序了的列表中索引为index-1的值比当前值小
        # 那么就把current_value放到index位置
        arg[index] = current_value
    print("此次循环：{} 次。".format(n))
    return arg

if __name__ == "__main__":
    l1 = get_list(50000)
    start_time = time.time()
    l2 = insertion_sort(l1)
    end_time = time.time()
    print("此次耗时：{} 秒。".format(end_time-start_time))

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# __author__ = "Q1mi"
# Email: master@liwenzhou.com

"""
快速排序
"""

import random
import time

def get_list(arg):
    """
    获得一个有指定个数的1000以内数字的列表
    :param arg: 期望获得的列表内数字的个数
    :return:
    """
    list_tmp = []
    for i in range(arg):
        list_tmp.append(random.randrange(1000000))
    return list_tmp

def quick_sort(original_list, start, end):
    """

    :param original_list: 待排序的列表
    :param start: 第一个元素的索引
    :param end: 最后一个元素的索引
    :return:
    """
    # 参数输错直接退出
    if start >= end:
        return
    # 取一个key值
    value_key = original_list[start]

    left = start
    right = end

    while left < right:
        # 先从右往左比较
        while left < right and original_list[right] > value_key:
            right -= 1
        # 把最前面的值跟这个比key小的值互换
        # 把最左边的值换成从右往左找到的那个比key小的那个值
        original_list[left], original_list[right] = original_list[right], original_list[left]
        #
        while left < right and original_list[left] <= value_key:
            left += 1
        # 如果从左往右找到了比key大的数
        original_list[left], original_list[right] = original_list[right], original_list[left]
    quick_sort(original_list, start, left-1)
    quick_sort(original_list, right+1, end)

if __name__ == "__main__":
    l1 = get_list(500000)
    start_time = time.time()
    quick_sort(l1, 0, len(l1)-1)
    end_time = time.time()
    print("此次耗时：{} 秒。".format(end_time-start_time))

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# __author__ = "Q1mi"
# Email: master@liwenzhou.com

"""
堆排序
"""

import random
import time

def get_list(arg):
    """
    获得一个有指定个数的1000以内数字的列表
    :param arg: 期望获得的列表内数字的个数
    :return:
    """
    list_tmp = []
    for i in range(arg):
        list_tmp.append(random.randrange(1000000))
    return list_tmp

def sift_down(lst, start, end):
    """

    :param lst: 待排序的数组
    :param start: 开始排序的节点
    :param end: 末节点
    :return: 调整为最大堆结构
    """
    root = start
    while True:
        child = 2 * root + 1  # 默认设置左子节点为最大子节点
        # 子节点越界就跳出
        if child > end:
            break
        # 如果右子节点没越界，并且右子节点的值比左子节点大
        if child + 1 <= end and lst[child] < lst[child+1]:
            # 设置右子节点为最大子节点
            child += 1
        # 如果根节点的数小于值大的那个子节点
        if lst[root] < lst[child]:
            # 互换位置
            lst[root], lst[child] = lst[child], lst[root]
            # 设置正在调整的节点为root
            root = child
        # 无需调整就退出
        else:
            break

def heap_sort(lst):
    for i in range(len(lst)//2, -1, -1):
        sift_down(lst, i, len(lst)-1)
    for j in range(len(lst)-1, 0, -1):
        lst[0], lst[j] = lst[j], lst[0]
        sift_down(lst, 0, j-1)
    return lst

if __name__ == "__main__":
    list_demo = get_list(500000)
    start_time = time.time()
    heap_sort(list_demo)
    end_time = time.time()
    print("此次耗时：{} 秒。".format(end_time-start_time))