共计 5815 个字符，预计需要花费 15 分钟才能阅读完成。
冒泡排序
冒泡排序的思维，咱们要把相邻的元素两两比拟，当一个元素大于右侧相邻元素时，
替换它们的地位; 当一个元素小于或等于右侧相邻元素时，地位不变。
def bubbleSort(list):
range 返回一个序列的数 不指定返回具体值 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
当没有产生地位替换时，阐明有序跳出大循环
if(isSorted):
break
return list
加上 isSorted 只是优化了大循环，记录地位优化了比拟次数的循环
def optBubbleSort(list):
记录最初一个产生地位替换的地位
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# 地位数最大的地位变换
sortBorder = lastExchangeIndex
当没有产生地位替换时，阐明有序跳出大循环
if(isSorted):
break
return list
冒泡排序测试
text = [5,8,6,3,9,2,1,7]
bubbleSort(text)
[1, 2, 3, 5, 6, 7, 8, 9]
优化冒泡排序测试
text = [4,3,2,1,5,6,7,8]
optBubbleSort(text)
[1, 2, 3, 4, 5, 6, 7, 8]
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
鸡尾酒排序
鸡尾酒排序的元素比拟和替换过程是双向的。它能施展出劣势的场景，是大部分元素曾经有序的状况。
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
当没有产生地位替换时，阐明有序跳出大循环
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
因为有元素进行替换，所以不是有序的，标记变为 false
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
疾速排序
外汇经纪商比照 https://www.fx61.com/brokerlist
from queue import LifoQueue
“””
冒泡排序在每一轮中只把 1 个元素冒泡到数列的一端，而疾速排序则在每一
轮筛选一个基准元素，并让其余比它大的元素挪动到数列一边，比它小的
元素挪动到数列的另一边，从而把数列拆解成两个局部。
均匀工夫复杂度是 O(nlogn)。
“””
疾速排序递归实现
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)
“””
每一次循环，都会让栈顶元素出栈，通过 partition 办法进行分治，并且依照基准元素的位
置分成左右两局部，左右两局部再别离入栈。当栈为空时，阐明排序曾经结束，退出循环。
“””
疾速排序栈实现(绝大多数的递归逻辑，都能够用栈的形式来代替)
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# 替换地位次数
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]
疾速排序栈实现测试
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
堆排序
“””
二叉堆的个性是什么?
- 最大堆的堆顶是整个堆中的最大元素。(最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。)
- 最小堆的堆顶是整个堆中的最小元素。(最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。)
二叉堆理论存储在数组中，把无序数组构建成二叉堆。须要从小到大排序，则构建成最大堆; 须要从大到小
排序，则构建成最小堆。
那么堆排序算法就是循环删除堆顶元素，替换到二叉堆的开端，调整堆产生新的堆顶。
“””
def heapSort(arr):
无序数组创立最大堆
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
堆排序实现测试
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
计数排序
计数排序不必元素之间的比拟，以数组 index 主动排序
def countSort(arr):
找出无序数组的最大的值
arrMax = arr[0]
for a in arr:
if(arrMax < a):
arrMax = a
创立一个以无序数组最大值为长度的数组
countArray = [0 for x in range(0,arrMax + 1)]
遍历无序数组统计值呈现的次数
for i in range(len(arr)):
countArray[arr[i]] += 1
此时 countArray 的值为 arr 值呈现的次数，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):
sortedArray[index] = c
index+=1
return sortedArray
计数实现测试
text = [4,7,3,5,6,2,1]
countSort(text)
[1, 2, 3, 4, 5, 6, 7]
计数排序的优化(节约空间不再是以最大值创立数组; 稳固排序：雷同的值下程序不变)
def countSort(arr):
arrMax = arr[0]
arrMin = arr[0]
for a in arr:
if(arrMax < a):
arrMax = a
if(arrMin > a):
arrMin = a
创立一个以无序数组, 长度为最大与最小的差值
countArray = [0 for x in range(0,arrMax – arrMin + 1)]
for i in range(len(arr)):
countArray[arr[i] – arrMin] += 1
统计数组做变形，前面的元素等于后面的元素之和
for j in range(len(countArray) – 1):
countArray[j + 1] += countArray[j]
sortedArray = [0 for x in range(0,len(arr))]
倒序遍历原始数列，从统计数组找到正确地位，输入到后果数组(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
桶排序
“””
创立的桶数量等于原始数列的元素数量，除最初一个桶只蕴含数列最大值外，后面各个桶的
区间依照比例来确定。区间跨度 = (最大值 - 最小值)/ (桶的数量 – 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]
