list 排序_十個必知的排序算法|Python執行個體系列

十大排序:

1.冒泡排序2.選擇排序3.插入排序4.希爾排序5.歸并排序6.快速排序7.堆排序8.計數排序9.桶排序10.基數排序

完整代碼和注釋如下

# -*- coding: UTF-8 -*-#Space: https://github.com/Tri-x/exercise#Space: https://space.bilibili.com/187492698#Author: Trix#Description: 十大經典排序算法#Python的排序算法用的是Tim Sort 一種源自歸并排序和插入排序的穩定高效的排序算法 也許以後會單獨做一期視訊來介紹該算法#也許以後會做一期視訊來介紹一些奇葩的排序算法 比如 睡眠排序、猴子排序、面條排序、珠排序from random import randint#随機整數from time import process_time#計時nums_lists=[[]for n in range(4)]#随機建立四個無序數列 用來粗略地測試每種排序算法的用時for n in range(500):#數列長度為500nums_lists[0].append(randint(-400,400))#随機範圍(-400,400)for n in range(1000):nums_lists[1].append(randint(-8000,8000))for n in range(5001):nums_lists[2].append(randint(-2000,2000))for n in range(10000):nums_lists[3].append(randint(-9000,9000))#由于建立的随機數列太長,就不列印排序前和排序後的結果了def bubble_sort(num_list):#冒泡排序 該算法名字的由來是因為越小的值會慢慢"浮"到數列的頂端#循環周遊數列,一次比較兩個相鄰的值,如果後者值大于前者值,就把他們的位置互相交換for n in range(len(num_list)-1):#因為最後一次已經順序正确了是以循環次數-1for m in range(len(num_list)-1-n):#循環每結束一次 這一次循環中最大的值會移動到上一次循環中最大值的前一位 數列中後面的值已經有序 是以次數-nif num_list[m]>num_list[m+1]:#大小比較num_list[m+1],num_list[m]=num_list[m],num_list[m+1]#位置交換return num_listdef select_sort(num_list):#選擇排序 選擇最小值#每次循環在數列中找到最小值,放到上一次循環找到的最小值的後一位,第一次放在首位for n in range(len(num_list)-1):#因為最後一次已經順序正确了是以循環次數-1min_index=n#設最小值為索引為n的值for m in range(n,len(num_list)):#n值前已完成排序if num_list[m]=1:#控制步長範圍#以下為插入排序的内容 并對插入排序進行了改進for n in range(gap,len(num_list)):while (n-gap)>=0:#控制比較範圍if num_list[n]基準值,exchange_index不變,exchange_index仍為0n=3時,掃描值6>基準值,exchange_index不變,exchange_index仍為0n=4時,掃描值3每個左右子節點的完全二叉樹#這樣每次建構後索引[0]為最大值,在第n次結束,就把[0]和[-n]位置互換 在[0:-n-1]的範圍内進行下次的完全二叉樹建構list_len=len(num_list)#擷取數列長度for n in range(list_len//2,-1,-1):#list_len//2為父節點索引的規律 //表示除法向下取整 n∈[list_len//2,-1),n∈Z range(start,stop,step) step為-1時為從後往前周遊heapify(num_list,list_len,n)#數列完全二叉樹的初始化 建構每個父節點>每個左右子節點的完全二叉樹for n in range(list_len-1,0,-1):#n∈[list_len-1,0),n∈Znum_list[0],num_list[n]=num_list[n],num_list[0]#對上一次建構完成的二叉樹 首尾值互換list_len-=1#限定這一次構造完全二叉樹的範圍heapify(num_list,list_len,0)#由于已經初始化完成 可以直接從首項開始 在不包含上次最大值的範圍内進行構造完全二叉樹return num_listdef heapify(num_list,list_len,parent_index):#建構父節點>左右子節點的完全二叉樹#第n排有n^(n-1),從左到右填充數值,可以得到父節點索引和左右子節點索引的規律left_index=2*parent_index+1#對于每個父節點索引 左節點索引的規律right_index=left_index+1#對于每個父節點索引 右節點索引的規律max_index=parent_index#假設父節點比左右子節點值都大 預設最大值的索引為父節點索引if left_indexnum_list[max_index]:#如果在清單範圍内 左節點值>父節點值max_index=left_index#父節點和左節點的索引互換if right_indexnum_list[max_index]:#右節點同理max_index=right_indexif max_index!=parent_index:#如果現在的父節點索引不等于一開始的假設的最大值的索引 說明父節點和它的某一節點需要互換索引值num_list[parent_index],num_list[max_index]=num_list[max_index],num_list[parent_index]heapify(num_list,list_len,max_index)#遞歸建構整個數列的完全二叉樹def count_sort(num_list):#計數排序 數數#找出數列中最大值和最小值 建立min~max這麼多個0用來統計數列中每個值出現的次數,再從最小值依次排放到最大值max_num=max(num_list)#找到最大值min_num=min(num_list)#找到最小值neg_list=[]#負數數列pos_list=[]#非負數數列for num in num_list:#對負數和非負數分别處理if num<0:neg_list.append(num)#向負數數列添加負數if num>=0:pos_list.append(num)#向非負數數列添加非負數if len(neg_list)!=0:#如果有負數neg_counts_list=[0 for n in range(min_num,0)]#建立最小值這麼多個0來累計每個負數出現的次數for n in range(len(neg_list)):#對于負數數列中的每個值neg_counts_list[neg_list[n]]+=1neg_index=0#初始排序索引為0for n in range(-len(neg_counts_list),0):#對于計數清單中的每一項while neg_counts_list[n]>0:#不為0就說明有計數 為0說明沒有計數neg_list[neg_index]=n#依次排放數值neg_index+=1#每次排放後index+1neg_counts_list[n]-=1#每次排放後數值所對應的計數-1if len(pos_list)!=0:#如果有非負數pos_counts_list=[0 for n in range(max_num+1)]#建立max+1這麼多個0來累計每個非負數出現的次數 因為是以每個值為索引 是以要max+1個0for n in range(len(pos_list)):#對于數列中的每個非負值pos_counts_list[pos_list[n]]+=1#計數清單索引和數列的值一一對應pos_index=0#初始排序索引為0for n in range(len(pos_counts_list)):#對于計數清單中的每一項while pos_counts_list[n]>0:#不為0就說明有計數 為0說明沒有計數pos_list[pos_index]=n#依次排放數值pos_index+=1#每次排放後index+1pos_counts_list[n]-=1#每次排放後數值所對應的計數-1result_list=neg_list+pos_list#負數數列和非負數數列結合return result_listdef bucket_sort(num_list):#桶排序 計數排序的改進版#找出數列中最大值和最小值 建立min~max這麼多個桶用來統計數列中每個值出現的次數,再從第一個桶傾倒到最後一個桶bucket_list=[0 for n in range(max(num_list)-min(num_list)+1)]#建立min~max這麼多個桶for n in range(len(num_list)):#對于目前值bucket_list[num_list[n]-min(num_list)]+=1#添加到值對應的桶内 即對應桶計數+1result_list=[]#結果清單for n in range(len(bucket_list)):#對于每個桶if bucket_list[n]!=0:#如果桶内有數result_list+=[n+min(num_list)]*bucket_list[n]#直接把桶裡的所有數倒出來return result_listdef radix_sort(num_list):#基數排序 比較位數上的值#比較每一位上的數字大小 當每一位比較完成排序也就完成pos_list=[]#負數數列neg_list=[]#非負數數列for num in num_list:#對負數和非負數分别處理if num<0:neg_list.append(num)if num>=0:pos_list.append(num)if len(neg_list)!=0:#如果有負數neg_num_digit=0#初始位數while neg_num_digit