第python數據結構的排序算法（1）算法思想

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

（2）python實現代碼

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）算法思想

它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂

（2）python實現代碼

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)

#不斷調整堆：根與最后一個元素

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

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

al-=1

heapify(a,0)

returna

四、歸并排序

（1）算法思想

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

（2）python實現代碼

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、計數排序（字典計數-還原）

（1）算法思想

計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

（2）python實現代碼

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）算法思想

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

（2）python實現代碼

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、基數排序

（1）算法思想

基數排序將數據按位進行分桶，然后將桶中的數據合并。每次分桶只關注其中一位數據，其他位的數據不管，最大的數據有多少位，就進行多少次分桶和合并。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。

（2）python實現代碼

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