快速排序算法在处理不同容量数组时的数据可视化-Toy模板网

这篇具有很好参考价值的文章主要介绍了快速排序算法在处理不同容量数组时的数据可视化。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

回忆快速排序：
链接: link

#将不同数据规模数组快排时间可视化
import time
import random
import matplotlib.pyplot as plt
import numpy as np
#三值取中法取轴值
def FindPivox(nums,left,right):
     mid=(left+right)//2
     if nums[left]>nums[mid]:
         nums[left],nums[mid]=nums[mid],nums[left]
     if nums[left]>nums[right]:
         nums[left],nums[right]=nums[right],nums[left]
     if nums[mid]>nums[right]:
         nums[mid],nums[right]=nums[right],nums[mid]
     return mid

def partition(nums,left,right,pivox):
    while left<=right:
        while nums[left]<pivox:
            left+=1
        while nums[right]>pivox and right>0:
            right-=1
        nums[left],nums[right]=nums[right],nums[left]
    nums[left], nums[right] = nums[right], nums[left]
    return left

def quick_sort(nums,left=0,right=None):
    if right is None:
        right=len(nums)-1
    #1、确定恰当的轴值
    p_index1=FindPivox(nums,left,right)
    #2、轴值和右端元素交换位置，方便双指针法分割小值序列和大值序列
    nums[p_index1],nums[right]=nums[right],nums[p_index1]
    #3、双指针法分割小值序列和大值序列
    p_index2=partition(nums,left,right-1,nums[right])
    #4、将轴值元素放在小值元素序列右边，大值元素左边，其实就是左指针元素和轴值交换
    nums[p_index2],nums[right]=nums[right],nums[p_index2]
    #5、递归：（增加条件当数据规模小于时停止递归改用直接插入排序）
    if (p_index2-left)>1:#隐含了基准情形，当序列中元素为1时排序完成
        quick_sort(nums,left,p_index2-1)
    if (right-p_index2)>1:
        quick_sort(nums,p_index2+1,right)
        return nums

#数据可视化

# 生成的规模为volume的整数数组
def generateData(volume,repetitionRate):
    # :param volume:定义生成的数据规模大小，应为整数
    # :param repetitionRate: 需要生成的数据序列的重复率，其值为[0,1]的小数，0代表完全不重复，1代表全部重复
    # :return: 按照要求生成的规模为volume的整数数组
    dataSet = volume - int(repetitionRate*volume)
    if dataSet == 0:
        return [0]*volume
    data = [0]*volume
    for i in range(dataSet):
        data[i] = i
    startIndex = dataSet
    while startIndex < volume:
        for i in range(dataSet):
            data[startIndex] = random.randrange(0,dataSet)
            startIndex += 1
            if startIndex == volume:
                 break
    random.shuffle(data) # 将数据随机打乱
    return data

#运行时间
def elapsedTime(function, volumes):
    # :param function:需要计算运行函数的函数名
    # :param volumes: 记录数据规模大小的数组
    # :return: 记录运行时间的数组
    elapsedTimes = []
    for volume in volumes:
        nums = generateData(volume, 0)
        startTime = time.time_ns()
        function(nums,0,len(nums)-1)
        endTime = time.time_ns()
        elapsedTimes.append(endTime-startTime)
    return elapsedTimes

#可视化，横轴竖轴分别代表，数据规模、运行时间
def getChart(X,Y):
    fig, ax = plt.subplots()#创建一个新的图形窗口和一个坐标轴对象
    ax.plot(X, Y)
    plt.xlabel('Volume')  #指定x轴名称
    plt.ylabel('Elapsed Time')  #指定y轴名称
    plt.yticks(np.arange(0,0.5,0.1))#设置y轴间距
    plt.title('Quick Sort Elapsed Time')  #创建图表名称
    plt.show()
    plt.pause(5)
def main():
    volumes = [10*i for i in range(1,3)]#类型：列表。
    Y = elapsedTime(quick_sort,volumes)
    getChart(volumes, Y)#x:数据规模 y:快速排序所需时间

if __name__ == "__main__":
    main()