【C++信息學(xué)奧賽培訓】數據排序之快速排序(QuickSort)詳解以及實例解析

2021-04-10 05:03:34

資訊專題 / C++信息學(xué)奧賽培訓 00

一、快速排序算法介紹:

快速排序(QuickSort)是排除穩定性因素後(hòu)最常用的排序。

快速排序是由東尼·霍爾所發(fā)展的一種(zhǒng)排序算法。在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這(zhè)種(zhǒng)狀況并不常見。事(shì)實上,快速排序通常明顯比其他 Ο(nlogn) 算法更快,因爲它的内部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分爲兩(liǎng)個子串行(sub-lists)。快速排序又是一種(zhǒng)分而治之思想在排序算法上的典型應用。本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起(qǐ)的是簡單粗暴,因爲一聽到這(zhè)個名字你就(jiù)知道(dào)它存在的意義,就(jiù)是快,而且效率高!它是處理大數據最快的排序算法之一了。雖然 Worst Case 的時(shí)間複雜度達到了 O(n2),但是人家就(jiù)是優秀,在大多數情況下都(dōu)比平均時(shí)間複雜度爲 O(n logn) 的排序算法表現要更好(hǎo)。

快速排序的最壞運行情況是 O(n2),比如說(shuō)順序數列的快排。但它的平攤期望時(shí)間是 O(nlogn),且 O(nlogn) 記号中隐含的常數因子很小,比複雜度穩定等于 O(nlogn) 的歸并排序要小很多。所以,對(duì)絕大多數順序性較弱的随機數列而言,快速排序總是優于歸并排序。

二、快速排序算法步驟:

1.從數列中挑出一個元素作爲基準(pivot)。

2.重新排列數列,把所有的比基準小的數放在基準前面(miàn),反之放在後(hòu)面(miàn)(一樣大的數可放到任意一邊)完成(chéng)操作後(hòu)基準就(jiù)處在分區的中間位置。這(zhè)個稱爲分區(partition)操作。

3.通過(guò)遞歸(recursive)調用把小于基準元素和大于基準元素的子序列進(jìn)行排序。

三、快速排序算法可視化演示:

C++信息學(xué)奧賽數據排序中快速排序算法可視化演示

六、快速排序算法實例解析(信息學(xué)奧賽一本通例題)

來源:淄博信息學(xué)奧賽培訓 / 編輯:NOIP/NOI輔導

上一篇:【C++信息學(xué)奧賽培訓】數據排序之插入排序(InsertionSort)詳解以及實例解析

下一篇:【C++信息學(xué)奧賽培訓】數據排序之冒泡排序(Bubble Sort)詳解以及實例解析

返回列表

延展閱讀

更多相關案例,更多借鑒,更多優化!

16年時(shí)間,圻谷深入100多個細分行業,從建築、建材、裝修、到工程、服飾、電子電器...資深的行業産品營銷經(jīng)驗與專業的推廣運營能(néng)力,給您更好(hǎo)保障!

文章點評

點評文章,寫評論得積分,赢禮品!

  • 暫無【C++信息學(xué)奧賽培訓】數據排序之快速排序(QuickSort)詳解以及實例解析點評 + 登錄後(hòu)點評
  • Contact Us

    多一份參考,總有益處。

    聯系QIGOO,免費獲得專屬《策劃方案》及報價。

    走過(guò)十六年曆程的互聯網整合營銷機構,以技術與思想,提升您網站的廣度傳播與深度。

    咨詢問題或預約面(miàn)談,可以通過(guò)以下方式聯系我們。

    網站首頁

    圻谷案例

    建站方案

    網站建設

    電商平台

    系統開(kāi)發(fā)

    資訊專題

    了解圻谷

    聯系圻谷

    淄博網站建設微信

    關于我們 | 聯系我們

    © 2019 圻谷網絡 All Rights Reserved.

    技術支持:圻谷網絡

    關注圻谷網絡獲得全面(miàn)的咨詢服務!
    淄博營銷型網站建設
    微信号:15589330185