亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

python 實(shí)現(xiàn)快速排序

Enlightenment / 2970人閱讀

摘要：排序算法之快速排序快速排序快排的思想首先任意選取一個(gè)數(shù)據(jù)通常選用數(shù)組的第一個(gè)數(shù)作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一趟快速排序。

Python排序算法之快速排序
快速排序（quickSort）
快排的思想：首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一趟快速排序。

百度百科給的算法：

一趟快速排序的算法是：

1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換；
4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換；
5）重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。

時(shí)間復(fù)雜度：O(nlgn)

# QuickSort by Alvin


def QuickSort(myList, start, end):
    # 判斷l(xiāng)ow是否小于high,如果為false,直接返回
    if start < end:
        i, j = start, end
        # 設(shè)置基準(zhǔn)數(shù)
        base = myList[i]

        while i < j:
            # 如果列表后邊的數(shù),比基準(zhǔn)數(shù)大或相等,則前移一位直到有比基準(zhǔn)數(shù)小的數(shù)出現(xiàn)
            while (i < j) and (myList[j] >= base):
                j = j - 1

            # 同樣的方式比較前半?yún)^(qū)
            while (i < j) and (myList[i] <= base):
                i = i + 1

            myList[i], myList[j] = myList[j], myList[i]
        # 做完第一輪比較之后,列表被分成了兩個(gè)半?yún)^(qū),并且i=j,需要將這個(gè)數(shù)設(shè)置回base
        myList[i] = base

        # 遞歸前后半?yún)^(qū)
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49, 38, 65, 97, 76, 13, 27, 49]
print("Quick Sort: ")
QuickSort(myList, 0, len(myList)-1)
print(myList)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/44983.html

相關(guān)文章

  • Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

    摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號(hào)。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚 學(xué)會(huì)了Python基礎(chǔ)知識(shí)，想進(jìn)階一下，那就來(lái)點(diǎn)算法吧！畢竟編程語(yǔ)言只...

    zxhaaa 評(píng)論0 收藏0

  • python-八大算法

    摘要：排序算法總結(jié)排序算法平均時(shí)間復(fù)雜度冒泡排序選擇排序插入排序希爾排序快速排序歸并排序堆排序基數(shù)排序一冒泡排序基本思想兩個(gè)數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來(lái)。 排序算法總結(jié) 排序算法 平均時(shí)間復(fù)雜度 冒泡排序O(n2) 選擇排序O(n2) 插入排序O(n2) 希爾排序O(n1.5) 快速排序O(N*logN) 歸并排序O(N*logN) 堆排序O(N*logN) 基數(shù)排序O(d(n+...

    aboutU 評(píng)論0 收藏0

  • 八大排序算法的Python實(shí)現(xiàn)

    摘要：是穩(wěn)定的排序方法。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。算法實(shí)現(xiàn)選擇排序堆排序描述堆排序是指利用堆積樹(shù)堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。 1、插入排序 描述 插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定...

    princekin 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見(jiàn)排序算法

    摘要：這是一個(gè)簡(jiǎn)單的遞歸函數(shù)，你可以使用它來(lái)生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問(wèn)題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見(jiàn)操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問(wèn)題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問(wèn)題 ...

    wuyumin 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見(jiàn)排序算法

    摘要：這是一個(gè)簡(jiǎn)單的遞歸函數(shù)，你可以使用它來(lái)生成數(shù)列中指定序號(hào)的數(shù)值這個(gè)函數(shù)的問(wèn)題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計(jì)算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見(jiàn)操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問(wèn)題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問(wèn)題 ...

    Carson 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<