使用Python快排统计次数的问题

问题描述

问 题

1，刚刚被问懵了。我都害怕。请问如下代码中的count是不是记录了全部的次数。使用了一个全局变量count来记录比较的次数。争论的重点在于两个if是否要算入计数中。我认为这个属于开始执行和结束执行的条件。请教以下。

# -*- coding:utf-8 -*-

import logging, copy
"""
    快速排序

"""
def quicksort(mylist, first, last):
    if first < last:
        piovt = partition(mylist, first, last)

        quicksort(mylist, first, piovt-1)
        quicksort(mylist, piovt+1, last)
    return mylist,
def partition(mylist, first, last):
    global count
    pivotValue = mylist[first]
    left = first + 1
    right = last
    done = False
    while not done:
        count = count+1
        while left <= right and mylist[left] <= pivotValue:
            count = count + 1
            left = left + 1
        while mylist[right] >= pivotValue and right >= left:
            count = count+1
            right = right - 1

        if right < left:
            done = True
        else:
            temp = mylist[left]
            mylist[left] = mylist[right]
            mylist[right] = temp
    temp = mylist[first]
    mylist[first] = mylist[right]
    mylist[right] = temp
    return right

if __name__ == '__main__':
    count = 0

    logging.basicConfig(
        level=logging.DEBUG, format='%(asctime)s-%(levelname)s => %(message)s')
    
    myListinit=[7,2,5,1,29,6,4,19,11]
    mylist = copy.deepcopy(myListinit)
    isIn = quicksort(mylist, 0, len(mylist)-1)
    if isIn :
        logging.debug(
            '\nbefore:%s\nafter:%s\n%d' %(myListinit, isIn, count))

解决方案

你的代码是对的， if first < last: 不用加 这算是执行前的条件， if right < left:你上面已经加过一次 不管它进没进if

这篇关于使用Python快排统计次数的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！