python中用def实现自动排序_漫画排序算法Python实现
冒泡排序
冒泡排序的思想，我們要把相鄰的元素兩兩比較，當一個元素大于右側(cè)相鄰元素時，
交換它們的位置;當一個元素小于或等于右側(cè)相鄰元素時，位置不變。
def bubbleSort(list):
range返回一個序列的數(shù) 不指定返回具體值 len值長度
for i in range(len(list) - 1):
Python里true、false賦值首字母大寫
isSorted = True
for j in range(len(list) - i - 1 ):
if(float(list[j]) > float(list[j + 1])):
print(list)
fist = list[j]
list[j] = list[j + 1]
list[j + 1] = fist
isSorted = False
當沒有發(fā)生位置交換時，說明有序跳出大循環(huán)
if(isSorted):
break
return list
加上isSorted只是優(yōu)化了大循環(huán)，記錄位置優(yōu)化了比較次數(shù)的循環(huán)
def optBubbleSort(list):
記錄最后一個發(fā)生位置交換的位置
lastExchangeIndex = 0
sortBorder = len(list) - 1
for i in range(len(list) - 1):
isSorted = True
for j in range(sortBorder):
if(list[j] > list[j + 1]):
fist = list[j]
list[j] = list[j + 1]
list[j + 1] = fist
isSorted = False
lastExchangeIndex = j#位置數(shù)最大的位置變換
sortBorder = lastExchangeIndex
當沒有發(fā)生位置交換時，說明有序跳出大循環(huán)
if(isSorted):
break
return list
冒泡排序測試
text = [5,8,6,3,9,2,1,7]
bubbleSort(text)
[1, 2, 3, 5, 6, 7, 8, 9]
優(yōu)化冒泡排序測試
text = [4,3,2,1,5,6,7,8]
optBubbleSort(text)
[1, 2, 3, 4, 5, 6, 7, 8]
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
雞尾酒排序
雞尾酒排序的元素比較和交換過程是雙向的。它能發(fā)揮出優(yōu)勢的場景，是大部分元素已經(jīng)有序的情況。
def cocktailSort(list):
for i in range(int(len(list) / 2)):
isSorted = True
for j in range(len(list) - i - 1 ):
if(list[j] > list[j + 1]):
fist = list[j]
list[j] = list[j + 1]
list[j + 1] = fist
isSorted = False
當沒有發(fā)生位置交換時，說明有序跳出大循環(huán)
if(isSorted):
break
isSorted = True
wj = len(list) - i - 1
while(wj > i):
if(list[wj] < list[wj-1]):
tmp = list[wj]
list[wj] = list[wj-1]
list[wj-1] = tmp
因為有元素進行交換，所以不是有序的，標記變?yōu)閒alse
isSorted = False
wj -= 1
if(isSorted):
break
return list
雞尾酒排序測試
text = [2,3,4,59,6,7,8,1]
cocktailSort(text)
[1, 2, 3, 4, 6, 7, 8, 59]
1234567891011121314151617181920212223242526272829303132333435363738
from queue import LifoQueue
"""
冒泡排序在每一輪中只把1個元素冒泡到數(shù)列的一端，而快速排序則在每一
輪挑選一個基準元素，并讓其他比它大的元素移動到數(shù)列一邊，比它小的
元素移動到數(shù)列的另一邊，從而把數(shù)列拆解成兩個部分。
平均時間復雜度是O(nlogn)。
"""
快速排序遞歸實現(xiàn)
def quickSort(list,startIndex,endIndex):
if(startIndex >= endIndex):
return
pivotIndex = partition(list,startIndex,endIndex)
print(list)
quickSort(list, startIndex, pivotIndex - 1)
quickSort(list, pivotIndex + 1, endIndex)
"""
每一次循環(huán)，都會讓棧頂元素出棧，通過partition方法進行分治，并且按照基準元素的位
置分成左右兩部分，左右兩部分再分別入棧。當棧為空時，說明排序已經(jīng)完畢，退出循環(huán)。
"""
快速排序棧實現(xiàn)(絕大多數(shù)的遞歸邏輯，都可以用棧的方式來代替)
def stackQuickSort(list,startIndex,endIndex):
stack = LifoQueue()
param = {"startIndex":startIndex,"endIndex":endIndex}#字典 key value
stack.put(param)
while (not stack.empty()):
p = stack.get()
pivotIndex = partition(list,p["startIndex"],p["endIndex"])
if(p["startIndex"] < pivotIndex - 1):
leftParam = {"startIndex":startIndex,"endIndex":pivotIndex - 1}
stack.put(leftParam)
if(pivotIndex + 1 < p["endIndex"]):
rightParam = {"startIndex":pivotIndex + 1,"endIndex":endIndex}
stack.put(rightParam)
def partition(list,startIndex,endIndex):
pivot = list[startIndex]#把首元素作為基準元素
mark = startIndex
i = startIndex + 1
while(i <= endIndex):
if(list[i] < pivot):
mark += 1#交換位置次數(shù)
p = list[mark]
list[mark] = list[i]
list[i] = p
i += 1
list[startIndex] = list[mark]
list[mark] = pivot
return mark
快速排序遞歸測試
text = [4,7,3,5,6,2,8,1]
quickSort(text,0,len(text) - 1)
print(text)
[1, 3, 2, 4, 6, 7, 8, 5]
[1, 3, 2, 4, 6, 7, 8, 5]
[1, 2, 3, 4, 6, 7, 8, 5]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
快速排序棧實現(xiàn)測試
text = [4,7,3,5,6,2,8,1]
stackQuickSort(text,0,len(text) - 1)
print(text)
[1, 2, 3, 4, 5, 6, 7, 8]
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
堆排序
"""
二叉堆的特性是什么?最大堆的堆頂是整個堆中的最大元素。(最大堆的任何一個父節(jié)點的值，都大于或等于它左、右孩子節(jié)點的值。)
最小堆的堆頂是整個堆中的最小元素。(最小堆的任何一個父節(jié)點的值，都小于或等于它左、右孩子節(jié)點的值。)
二叉堆實際存儲在數(shù)組中，把無序數(shù)組構(gòu)建成二叉堆。需要從小到大排序，則構(gòu)建成最大堆;需要從大到小
排序，則構(gòu)建成最小堆。
那么堆排序算法就是循環(huán)刪除堆頂元素，替換到二叉堆的末尾，調(diào)整堆產(chǎn)生新的堆頂。
"""
def heapSort(arr):
無序數(shù)組創(chuàng)建最大堆
i = len(arr) / 2
while( i >= 1):
downAdjust(arr,i,len(arr))
i -= 1
print("最大堆：",arr)
排序
j = (len(arr) - 1 )
while(j > 0):
temp1 = arr[j]
arr[j] = arr[0]
arr[0] = temp1
downAdjust(arr, 0, j)
j-=1
def downAdjust(arr,parentIndex,length):
parentIndex = int(parentIndex)
length = int(length)
temp = arr[parentIndex]
childIndex = parentIndex * 2 + 1
while(childIndex < length):
if(childIndex + 1 < length and arr[childIndex] < arr[childIndex + 1]):#改成>號則是最小堆
childIndex += 1
if(temp >= arr[childIndex]):#改成<號則是最小堆
break
arr[parentIndex] = arr[childIndex]
parentIndex = childIndex
childIndex = 2 * childIndex + 1
arr[parentIndex] = temp
堆排序?qū)崿F(xiàn)測試
text = [4,7,3,5,6,2,1]
heapSort(text)
print(text)
最大堆： [4, 7, 3, 5, 6, 2, 1]
[1, 2, 3, 5, 6, 7, 4]
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
計數(shù)排序
計數(shù)排序不用元素之間的比較，以數(shù)組index自動排序
def countSort(arr):
找出無序數(shù)組的最大的值
arrMax = arr[0]
for a in arr:
if(arrMax < a):
arrMax = a
創(chuàng)建一個以無序數(shù)組最大值為長度的數(shù)組
countArray = [0 for x in range(0,arrMax + 1)]
遍歷無序數(shù)組統(tǒng)計值出現(xiàn)的次數(shù)
for i in range(len(arr)):
countArray[arr[i]] += 1
此時countArray的值為arr值出現(xiàn)的次數(shù)，countArray的index為arr的值
index = 0
sortedArray = [0 for x in range(0,len(arr))]
for c in range(len(countArray)):
for c1 in range(countArray[c]):
sortedArray[index] = c
index+=1
return sortedArray
計數(shù)實現(xiàn)測試
text = [4,7,3,5,6,2,1]
countSort(text)
[1, 2, 3, 4, 5, 6, 7]
計數(shù)排序的優(yōu)化(節(jié)約空間不再是以最大值創(chuàng)建數(shù)組;穩(wěn)定排序：相同的值下順序不變)
def countSort(arr):
arrMax = arr[0]
arrMin = arr[0]
for a in arr:
if(arrMax < a):
arrMax = a
if(arrMin > a):
arrMin = a
創(chuàng)建一個以無序數(shù)組,長度為最大與最小的差值
countArray = [0 for x in range(0,arrMax - arrMin + 1)]
for i in range(len(arr)):
countArray[arr[i] - arrMin] += 1
統(tǒng)計數(shù)組做變形，后面的元素等于前面的元素之和
for j in range(len(countArray) - 1):
countArray[j + 1] += countArray[j]
sortedArray = [0 for x in range(0,len(arr))]
倒序遍歷原始數(shù)列，從統(tǒng)計數(shù)組找到正確位置，輸出到結(jié)果數(shù)組(countArray存的值是順序)
index = len(arr) - 1
while(index >= 0):
sortedArray[countArray[arr[index] - arrMin] - 1] = arr[index]
countArray[arr[index]-arrMin] -= 1
index -= 1
return sortedArray
text = [4,7,3,5,3,2,1]
countSort(text)
[1, 2, 3, 3, 4, 5, 7]
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
桶排序
"""
創(chuàng)建的桶數(shù)量等于原始數(shù)列的元素數(shù)量，除最后一個桶只包含數(shù)列最大值外，前面各個桶的
區(qū)間按照比例來確定。區(qū)間跨度 = (最大值-最小值)/ (桶的數(shù)量 - 1)
"""
def bucketSort(arr):
arrMax = arr[0]
arrMin = arr[0]
for a in arr:
if(arrMax < a):
arrMax = a
if(arrMin > a):
arrMin = a
d = arrMax - arrMin
bucketNum = len(arr)
初始化桶
blist = {}
for i in range(len(arr)):
bb = []
blist[i] = bb
for a in arr:
num = (int)((a - arrMin) * (bucketNum - 1) / d)
blist[num].append(a)
排序每個桶里的值
for b in blist:
ccc = blist[b]
ccc.sort()
blist[b] = ccc
sortArr = []
for n in blist:
for l in blist[n]:
sortArr.append(l)
return sortArr
text = [4.5,0.84,3.25,2.18,0.5]
bucketSort(text)
[0.5, 0.84, 2.18, 3.25, 4.5]
總結(jié)
以上是生活随笔為你收集整理的python中用def实现自动排序_漫画排序算法Python实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python安装成功第三方库但impor
- 下一篇： 访问服务器 request.gethea