回憶快速排序：
鏈接: link

#將不同數(shù)據(jù)規(guī)模數(shù)組快排時(shí)間可視化
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、確定恰當(dāng)?shù)妮S值
    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、將軸值元素放在小值元素序列右邊，大值元素左邊，其實(shí)就是左指針元素和軸值交換
    nums[p_index2],nums[right]=nums[right],nums[p_index2]
    #5、遞歸：（增加條件當(dāng)數(shù)據(jù)規(guī)模小于時(shí)停止遞歸改用直接插入排序）
    if (p_index2-left)>1:#隱含了基準(zhǔn)情形，當(dāng)序列中元素為1時(shí)排序完成
        quick_sort(nums,left,p_index2-1)
    if (right-p_index2)>1:
        quick_sort(nums,p_index2+1,right)
        return nums

#數(shù)據(jù)可視化

# 生成的規(guī)模為volume的整數(shù)數(shù)組
def generateData(volume,repetitionRate):
    # :param volume:定義生成的數(shù)據(jù)規(guī)模大小，應(yīng)為整數(shù)
    # :param repetitionRate: 需要生成的數(shù)據(jù)序列的重復(fù)率，其值為[0,1]的小數(shù)，0代表完全不重復(fù)，1代表全部重復(fù)
    # :return: 按照要求生成的規(guī)模為volume的整數(shù)數(shù)組
    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) # 將數(shù)據(jù)隨機(jī)打亂
    return data

#運(yùn)行時(shí)間
def elapsedTime(function, volumes):
    # :param function:需要計(jì)算運(yùn)行函數(shù)的函數(shù)名
    # :param volumes: 記錄數(shù)據(jù)規(guī)模大小的數(shù)組
    # :return: 記錄運(yùn)行時(shí)間的數(shù)組
    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

#可視化，橫軸豎軸分別代表，數(shù)據(jù)規(guī)模、運(yùn)行時(shí)間
def getChart(X,Y):
    fig, ax = plt.subplots()#創(chuàng)建一個(gè)新的圖形窗口和一個(gè)坐標(biāo)軸對(duì)象
    ax.plot(X, Y)
    plt.xlabel('Volume')  #指定x軸名稱
    plt.ylabel('Elapsed Time')  #指定y軸名稱
    plt.yticks(np.arange(0,0.5,0.1))#設(shè)置y軸間距
    plt.title('Quick Sort Elapsed Time')  #創(chuàng)建圖表名稱
    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:數(shù)據(jù)規(guī)模 y:快速排序所需時(shí)間

if __name__ == "__main__":
    main()

輸出結(jié)果：

要想得到處理大規(guī)模數(shù)組所需的時(shí)間，可以修改
volumes參數(shù)
eg

volumes = [100*i for i in range(1,101)]

這樣就能得到快排在處理數(shù)據(jù)規(guī)模從100、200…10000的數(shù)組所需的時(shí)間啦文章來源地址http://www.zghlxwxcb.cn/news/detail-846733.html

到了這里，關(guān)于快速排序算法在處理不同容量數(shù)組時(shí)的數(shù)據(jù)可視化的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！