关于python:漫画排序算法Python实现

冒泡排序

def bubbleSort(list):

for i in range(len(list) – 1):

isSorted = True

for j in range(len(list) – i – 1 ):

if(float(list[j]) > float(list[j + 1])):

fist = list[j]

list[j] = list[j + 1]

list[j + 1] = fist

isSorted = False

if(isSorted):

break

return list

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

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, 2, 3, 4, 6, 7, 8, 5]

[1, 2, 3, 4, 5, 6, 8, 7]

[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

计数排序

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

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))]

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]

关于python:漫画排序算法Python实现

冒泡排序的思维，咱们要把相邻的元素两两比拟，当一个元素大于右侧相邻元素时，

替换它们的地位; 当一个元素小于或等于右侧相邻元素时，地位不变。

range 返回一个序列的数不指定返回具体值 len 值长度

Python 里 true、false 赋值首字母大写

print(list)

当没有产生地位替换时，阐明有序跳出大循环

加上 isSorted 只是优化了大循环，记录地位优化了比拟次数的循环

记录最初一个产生地位替换的地位

当没有产生地位替换时，阐明有序跳出大循环

冒泡排序测试

优化冒泡排序测试

鸡尾酒排序的元素比拟和替换过程是双向的。它能施展出劣势的场景，是大部分元素曾经有序的状况。

当没有产生地位替换时，阐明有序跳出大循环

因为有元素进行替换，所以不是有序的，标记变为 false

鸡尾酒排序测试

疾速排序递归实现

疾速排序栈实现(绝大多数的递归逻辑，都能够用栈的形式来代替)

疾速排序递归测试

疾速排序栈实现测试

无序数组创立最大堆

排序

堆排序实现测试

计数排序不必元素之间的比拟，以数组 index 主动排序

找出无序数组的最大的值

创立一个以无序数组最大值为长度的数组

遍历无序数组统计值呈现的次数

此时 countArray 的值为 arr 值呈现的次数，countArray 的 index 为 arr 的值

计数实现测试

计数排序的优化(节约空间不再是以最大值创立数组; 稳固排序：雷同的值下程序不变)

创立一个以无序数组, 长度为最大与最小的差值

统计数组做变形，前面的元素等于后面的元素之和

倒序遍历原始数列，从统计数组找到正确地位，输入到后果数组(countArray 存的值是程序)

初始化桶

排序每个桶里的值

冒泡排序的思维，咱们要把相邻的元素两两比拟，当一个元素大于右侧相邻元素时，

替换它们的地位; 当一个元素小于或等于右侧相邻元素时，地位不变。

range 返回一个序列的数 不指定返回具体值 len 值长度

Python 里 true、false 赋值首字母大写

print(list)

当没有产生地位替换时，阐明有序跳出大循环

加上 isSorted 只是优化了大循环，记录地位优化了比拟次数的循环

记录最初一个产生地位替换的地位

当没有产生地位替换时，阐明有序跳出大循环

冒泡排序测试

优化冒泡排序测试

鸡尾酒排序的元素比拟和替换过程是双向的。它能施展出劣势的场景，是大部分元素曾经有序的状况。

当没有产生地位替换时，阐明有序跳出大循环

因为有元素进行替换，所以不是有序的，标记变为 false

鸡尾酒排序测试

疾速排序递归实现

疾速排序栈实现(绝大多数的递归逻辑，都能够用栈的形式来代替)

疾速排序递归测试

疾速排序栈实现测试

无序数组创立最大堆

排序

堆排序实现测试

计数排序不必元素之间的比拟，以数组 index 主动排序

找出无序数组的最大的值

创立一个以无序数组最大值为长度的数组

遍历无序数组统计值呈现的次数

此时 countArray 的值为 arr 值呈现的次数，countArray 的 index 为 arr 的值

计数实现测试

计数排序的优化(节约空间不再是以最大值创立数组; 稳固排序：雷同的值下程序不变)

创立一个以无序数组, 长度为最大与最小的差值

统计数组做变形，前面的元素等于后面的元素之和

倒序遍历原始数列，从统计数组找到正确地位，输入到后果数组(countArray 存的值是程序)

初始化桶

排序每个桶里的值

range 返回一个序列的数不指定返回具体值 len 值长度