python數(shù)據(jù)結(jié)構(gòu)的排序算法

第python數(shù)據(jù)結(jié)構(gòu)的排序算法（1）算法思想

第1趟，在待排序記錄r1~r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2~r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i]~r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢

（2）python實(shí)現(xiàn)代碼

defselect_sort(slist):

foriinrange(len(slist)-1):

x=i

forjinrange(i,len(slist)):

ifslist[j]slist[x]:

x=j

slist[i],slist[x]=slist[x],slist[i]

returnslist

2、堆排序（利用最大堆和最小堆的特性）

（1）算法思想

它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂

（2）python實(shí)現(xiàn)代碼

importmath

defheap_sort(a):

al=len(a)

defheapify(a,i):

left=2*i+1

right=2*i+2

largest=i

ifleftalanda[left]a[largest]:

largest=left

ifrightalanda[right]a[largest]:

largest=right

iflargest!=i:

a[i],a[largest]=a[largest],a[i]

heapify(a,largest)

#建堆

foriinrange(math.floor(len(a)/2),-1,-1):

heapify(a,i)

#不斷調(diào)整堆：根與最后一個(gè)元素

foriinrange(len(a)-1,0,-1):

a[0],a[i]=a[i],a[0]

al-=1

heapify(a,0)

returna

四、歸并排序

（1）算法思想

采用分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并

（2）python實(shí)現(xiàn)代碼

defmerge_sort(a):

if(len(a)2):

returna

middle=len(a)//2

left,right=a[0:middle],a[middle:]

returnmerge(merge_sort(left),merge_sort(right))

defmerge(left,right):

result=[]

whileleftandright:

ifleft[0]=right[0]:

result.append(left.pop(0));

else:

result.append(right.pop(0));

whileleft:

result.append(left.pop(0));

whileright:

result.append(right.pop(0));

returnresult

五、其他排序

1、計(jì)數(shù)排序（字典計(jì)數(shù)-還原）

（1）算法思想

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

（2）python實(shí)現(xiàn)代碼

defcountingSort(arr,maxValue):

bucketLen=maxValue+1

bucket=[0]*bucketLen

sortedIndex=0

arrLen=len(arr)

foriinrange(arrLen):

ifnotbucket[arr[i]]:

bucket[arr[i]]=0

bucket[arr[i]]+=1

forjinrange(bucketLen):

whilebucket[j]0:

arr[sortedIndex]=j

sortedIndex+=1

bucket[j]-=1

returnarr

2、桶排序（鏈表）

（1）算法思想

為了節(jié)省空間和時(shí)間，我們需要指定要排序的數(shù)據(jù)中最小以及最大的數(shù)字的值。將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）

（2）python實(shí)現(xiàn)代碼

defbucketSort(nums):

bucket=[0]*(max(nums)-min(nums)+1)

foriinrange(len(nums)):

bucket[nums[i]-min(nums)]+=1

tmp=[]

foriinrange(len(bucket)):

ifbucket[i]!=0:

tmp+=[min(nums)+i]*bucket[i]

returntmp

3、基數(shù)排序

（1）算法思想

基數(shù)排序?qū)?shù)據(jù)按位進(jìn)行分桶，然后將桶中的數(shù)據(jù)合并。每次分桶只關(guān)注其中一位數(shù)據(jù)，其他位的數(shù)據(jù)不管，最大的數(shù)據(jù)有多少位，就進(jìn)行多少次分桶和合并。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

（2）python實(shí)現(xiàn)代碼

defradix_sort(array):

bucket,digit=[[]],0

whilelen(bucket[0])!=len(array):

bucket=[[],[],[],[],[],[],[],[],[],[]]

foriinrange(len(array)):

num=(array[i]//10**digit)%10

bucket[num].append(array[i])

array.cle