# 統(tǒng)計(jì)這個(gè)列表中數(shù)字最大的數(shù)字有幾位
def radix_sort_nums(nums):
    max = nums[0]
    for i in nums:
        if max < i:
            max = i
    times = 0
    while max > 0:
        max = int(max/10)
        times += 1
    return times

# 每個(gè)數(shù)字各個(gè)位置的數(shù)字大小，比如（123,1）則是3，（123,2）則是2
def get_num(num,n):
    return (int(num/(10**(n-1)))) % 10

# 主程序
def radix_sort(nums):
    count = 10*[None]	# 定義的數(shù)組，用于存放當(dāng)前位數(shù)的元素個(gè)數(shù)
    bucket = len(nums)*[None]	# 用于暫時(shí)存放排序結(jié)果
	# 分別從個(gè)位/十位/百位開始循環(huán)
    for pos in range(1, radix_sort_nums(nums)+1):
		# 每次排序完都要清空各個(gè)位數(shù)存放的數(shù)據(jù)統(tǒng)計(jì)
        for i in range(10):
            count[i] = 0

        for i in range(len(nums)):
			# 獲得0到9每個(gè)位數(shù)的個(gè)數(shù)
            j = get_num(nums[i], pos)
            count[j] = count[j]+1
		# 獲得相對(duì)應(yīng)位數(shù)的邊界值
        for i in range(1, 10):
            count[i] = count[i] + count[i-1]

        for i in range(len(nums)-1, -1, -1):
			# 求出相應(yīng)位數(shù)的數(shù)字
            j = get_num(nums[i], pos)
			#將元素按相應(yīng)位數(shù)的上數(shù)字的大小排序
            bucket[count[j]-1] = nums[i]
			#讓相應(yīng)位數(shù)上數(shù)字相等的元素不會(huì)放在同一位置而被替代
            count[j] = count[j]-1

		# 將暫時(shí)存儲(chǔ)在bucket的元素?cái)?shù)據(jù)返回到nums中
        for i in range(0, len(nums)):
            nums[i] = bucket[i]
    return nums

print(radix_sort([45, 32, 8, 33, 12, 22, 19, 97]))

# 歸并排序

# 這個(gè)函數(shù)主要目的是為了實(shí)現(xiàn)合并并排序
def mergearray(nums, first, mid, last, temp):
	# i, j分別是第一個(gè)組數(shù)的第一個(gè)位置，第二組數(shù)的第一個(gè)位置
    i, j, k = first, mid+1, 0
	# 當(dāng)倆邊數(shù)組都存在數(shù)的時(shí)候，依次比較對(duì)應(yīng)位置的大小
    while i <= mid and j <= last:
        if nums[i] <= nums[j]:
            temp[k] = nums[i]
            i = i+1
            k = k+1
        else:
            temp[k] = nums[j]
            j = j+1
            k = k+1
	# 第一組數(shù)還有多的數(shù)的情況
    while i <= mid:
        temp[k] = nums[i]
        i = i+1
        k = k+1
	# 第二組數(shù)還有多的情況
    while (j <= last):
        temp[k] = nums[j]
        j = j+1
        k = k+1
	# 將排列過的數(shù)組賦予nums（開始的時(shí)候只是部分有序，隨著遞歸最后變成全部有序）
    for i in range(k):
        nums[first+i] = temp[i]

# 分組，利用遞歸
def merge_sort(nums,first,last,temp):
    if first < last:
        mid = int((first + last) / 2)
		# 分出第一組數(shù)
        merge_sort(nums, first, mid, temp)
		# 分出第二組數(shù)
        merge_sort(nums, mid+1, last, temp)
		# 合并并排序
        mergearray(nums, first, mid, last, temp)

def merge_sort_array(nums):
	# 創(chuàng)建一個(gè)和想要排序數(shù)列相同數(shù)量的空列表
    temp = len(nums)*[None]
	# 利用遞歸進(jìn)行排序
    merge_sort(nums, 0, len(nums)-1, temp)


print(merge_sort_array([45, 32, 8, 33, 12, 22, 19, 97]))

def big_endian(arr, start, end):
    root = start
    child = root * 2 + 1  # 左孩子
    while child <= end:
        # 孩子比最后一個(gè)節(jié)點(diǎn)還大，也就意味著最后一個(gè)葉子節(jié)點(diǎn)了，就得跳出去一次循環(huán)，已經(jīng)調(diào)整完畢
        if child + 1 <= end and arr[child] < arr[child + 1]:
            # 為了始終讓其跟子元素的較大值比較，如果右邊大就左換右，左邊大的話就默認(rèn)
            child += 1
        if arr[root] < arr[child]:
            # 父節(jié)點(diǎn)小于子節(jié)點(diǎn)直接交換位置，同時(shí)坐標(biāo)也得換，這樣下次循環(huán)可以準(zhǔn)確判斷：是否為最底層，
            # 是不是調(diào)整完畢
            arr[root], arr[child] = arr[child], arr[root]
            root = child
            child = root * 2 + 1
        else:
            break


def heap_sort(nums):  # 無序區(qū)大根堆排序
    first = len(nums) // 2 - 1
    for start in range(first, -1, -1):
        # 從下到上，從左到右對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整，循環(huán)得到非葉子節(jié)點(diǎn)
        big_endian(nums, start, len(nums) - 1)  # 去調(diào)整所有的節(jié)點(diǎn)
    for end in range(len(nums) - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]  # 頂部尾部互換位置
        big_endian(nums, 0, end - 1)  # 重新調(diào)整子節(jié)點(diǎn)的順序，從頂開始調(diào)整
    return nums

print(heap_sort([3, 1, 4, 9, 6, 7, 5, 8, 2, 10]))

def select_sort(nums):
	# 遍歷所有的值
    for i in range(len(nums)):
		# 當(dāng)前位置初始值
        min = nums[i]
		# 與比他后面的值進(jìn)行比較，小則互換
        for j in range(i+1, len(nums)):
            if nums[j] < min:
                nums[j], min = min, nums[j]
		# 將值返回?cái)?shù)列
        nums[i] = min
    return nums

print(select_sort([45, 32, 8, 33, 12, 22, 19, 97]))

# 直接插入排序
def insert_sort(nums):
    for i in range(len(nums)-1):

        for j in range(i, -1, -1):

            if nums[j] > nums[j+1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

    return nums

print(insert_sort([45, 32, 8, 33, 12, 22, 19, 97]))

def insert_shell(nums):
    # 初始化l值，此處利用序列長(zhǎng)度的一半為其賦值
    l = int(len(nums)/2)
    # 第一層循環(huán)：依次改變l值對(duì)列表進(jìn)行分組
    while l >= 1:
    # 下面：利用直接插入排序的思想對(duì)分組數(shù)據(jù)進(jìn)行排序
        for i in range(len(nums) - 1):

            for j in range(i, -1, -1):

                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
    # while循環(huán)條件折半
        l = int(l/2)
    return nums

# 實(shí)現(xiàn)快速排序方法的函數(shù)
def quick_sort_num(nums,start,end):
    if start < end:
    	# 定義基準(zhǔn)值為第一個(gè)數(shù)
        i, j, pivot = start, end, nums[start]
        while i < j:
        	# 將基準(zhǔn)數(shù)右邊的數(shù)中比基準(zhǔn)數(shù)小的放到左邊
            while i < j and nums[j] >= pivot:
                j = j-1
            if i < j:
                nums[i] = nums[j]
                i = i+1
            # 將基準(zhǔn)數(shù)左邊的數(shù)中比基準(zhǔn)數(shù)大的數(shù)放到右邊
            while i < j and nums[i] < pivot:
                i = i+1
            if i < j:
                nums[j] = nums[i]
                j = j-1
        nums[i] = pivot
        # 分別將基準(zhǔn)數(shù)左邊的數(shù)列和右邊的數(shù)列進(jìn)行遞歸
        quick_sort_num(nums, start, i-1)
        quick_sort_num(nums, i+1, end)
    return nums

# 快速排序主體函數(shù)
def quick_sort(nums):
    start = 0
    end = len(nums)-1
    nums = quick_sort_num(nums, start, end)
    return nums

print(quick_sort([45, 32, 8, 33, 12, 22, 19, 97]))

def bubble_sort(nums):
	# 交換的輪數(shù)
    for i in range(len(nums) - 1):
    	# 每一輪交換
        for j in range(len(nums) - i - 1):
        	# 比較值，并根據(jù)大小進(jìn)行互換
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

    return nums

print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))

import random
lis = []
for i in range(10000):
    i = random.randint(0,500)
    lis.append(i)

print(lis)

冒泡排序法：11.535502672195435

直接插入排序法：12.057243585586548

希爾排序法：86.3020749092102（大概是我的方法不大好吧，我差點(diǎn)以為他排不出來了）

基數(shù)排序法：0.051932334899902344（老大哥就是牛皮）

歸并排序法：0.08577108383178711（233）

快速排序：0.04795527458190918

堆排序：0.09175491333007812