漫画排序算法Python实现

75 阅读 0 评论 50 点赞

我是靠谱客的博主简单哈密瓜，最近开发中收集的这篇文章主要介绍漫画排序算法Python实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

电子书和源码下载：p3xw

冒泡排序

#冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，
#交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
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]

鸡尾酒排序

#鸡尾酒排序的元素比较和交换过程是双向的。它能发挥出优势的场景，是大部分元素已经有序的情况。
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]

快速排序

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]

堆排序

"""
二叉堆的特性是什么?
1. 最大堆的堆顶是整个堆中的最大元素。（最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。）
2. 最小堆的堆顶是整个堆中的最小元素。（最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。）

二叉堆实际存储在数组中，把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小
排序，则构建成最小堆。

那么堆排序算法就是循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
"""
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]

计数排序

#计数排序不用元素之间的比较，以数组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[c]):
            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]

桶排序

"""
创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的
区间按照比例来确定。区间跨度 = （最大值-最小值）/ （桶的数量 - 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]