Python八大排序怎么實(shí)現(xiàn)

這篇文章主要介紹了Python八大排序怎么實(shí)現(xiàn)的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Python八大排序怎么實(shí)現(xiàn)文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

1.基數(shù)排序

基數(shù)排序的基本思想是先將數(shù)字按照個(gè)位數(shù)上數(shù)字的大小進(jìn)行排序，排序之后再將已經(jīng)排過(guò)序的數(shù)字再按照十位數(shù)上數(shù)字的大小進(jìn)行排序，依次推類(lèi)

# 統(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è)位/十位/百位開(kāi)始循環(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]))

2.歸并排序

歸并排序其實(shí)是將原數(shù)列分為很多個(gè)小數(shù)列將其排序，在小數(shù)列排序完之后，再將各個(gè)小數(shù)列進(jìn)行排序，最后得到一個(gè)全部有序的數(shù)列

# 歸并排序

# 這個(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
	# 將排列過(guò)的數(shù)組賦予nums（開(kāi)始的時(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]))

3.堆排序

堆排序利用了二叉樹(shù)的結(jié)構(gòu)，使子節(jié)點(diǎn)的值一直小于根節(jié)點(diǎn)

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):  # 無(wú)序區(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)的順序，從頂開(kāi)始調(diào)整
    return nums

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

4.簡(jiǎn)單選擇排序

簡(jiǎn)單選擇排序的方法則是將所選值與剩下值中比他小的值進(jìn)行比較

比如選取第一個(gè)值，往后找到比他小的值就與其對(duì)調(diào)，對(duì)調(diào)后的值再接下去進(jìn)行比較，直至找到最小的值，隨后再第二個(gè)值……直至循環(huán)到倒數(shù)第二個(gè)值.

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]))

5.直接插入排序

首先遍歷所有元素，隨后從第一個(gè)數(shù)開(kāi)始將數(shù)列從后往前遍歷，如果后面的數(shù)小于前面的數(shù)，則互換位置，依次推類(lèi)，直到遍歷完成

# 直接插入排序
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]))

6.希爾排序

希爾排序其實(shí)就相當(dāng)于對(duì)直接插入排序的升級(jí)版，每次都選取一半的長(zhǎng)度，隨后利用直接插入法進(jìn)行排序，從而更快的獲得結(jié)果

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

7.快速排序

快速排序首先得選取一個(gè)基準(zhǔn)值，這個(gè)代碼用第一個(gè)數(shù)作為基準(zhǔn)值，將比基準(zhǔn)值小的值放到左邊，比基準(zhǔn)值大的值放到右邊，隨后再將左邊后右邊按照上述方法進(jìn)行排序，直到完全正確為止

# 實(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]))

8.冒泡排序

冒泡排序是最簡(jiǎn)單的排序，依次將左右倆個(gè)元素進(jìn)行比較，每次比較完最后的一個(gè)數(shù)必定是最大的，依次推類(lèi)，直到全部元素都比較玩

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]))

9.時(shí)間測(cè)試

我們先創(chuàng)建一個(gè)列表，列表中有10000條數(shù)據(jù)，隨后用相同的數(shù)據(jù)進(jìn)行測(cè)試

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

print(lis)

創(chuàng)出來(lái)的數(shù)據(jù)就不進(jìn)行展示了。。

隨后我們進(jìn)行測(cè)試：

冒泡排序法：11.535502672195435

直接插入排序法：12.057243585586548

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

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

歸并排序法：0.08577108383178711（233）

快速排序：0.04795527458190918

堆排序：0.09175491333007812

根據(jù)自己的測(cè)試，基數(shù)排序，歸并排序，快速排序，和堆排序速度很快，感覺(jué)隨著代碼量的增長(zhǎng)時(shí)間增長(zhǎng)很慢，其余的幾個(gè)則不盡如人意了。

關(guān)于“Python八大排序怎么實(shí)現(xiàn)”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“Python八大排序怎么實(shí)現(xiàn)”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。