」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 快速排序

快速排序

發佈於2024-08-06
瀏覽:432

Quick Sort

快速排序算法

快速排序是最著名的排序算法之一,因为它是用标准库中的多种编程语言实现的。为什么这么用这个算法?
由于速度快,快速排序算法是最快的排序算法之一,时间复杂度为 O(n * log n),其中 n 是数组的大小,log 是对数底数 2。

它是如何工作的?

理解快速排序算法所需的主要概念是分而治之策略。
分而治之的战略是一个著名的军事术语,它过去的意思是,要征服一个大国,你应该首先让这个国家分裂,通常是由于内部冲突或内战,然后你去横扫整个国家。忙碌的。
好的,但是这个概念如何转化为计算机科学呢?分而治之,在算法中,意味着他通过解决更小的问题来解决问题,这与数学归纳法的概念非常相似,其中,我们建立f(1),然后我们建立f(n),然后,我们证明 f(n - 1) 是有效的,通过这样做,我们可以证明一个概念。
分治问题的工作方式相同,首先我们解决最简单的问题,通常称为基本情况,然后,我们制定递归情况,最后,我们将问题分解为最简单的问题,因为我们知道如何解决这些问题。

算法

我将展示 C 语言的实现,然后我将逐行解释它是如何工作的,因为这是一个相当复杂的想法。

#include 
#include 
#include 

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index   1, high);
}

所以该算法的主要思想很简单,将数组将列表分为两部分,其中所有元素都小于主元,另一部分所有元素都大于主元。
然后,递归地将这个算法应用于零件本身,直到零件没有元素,在这种情况下,我们可以确定它已正确排序。

在快速排序算法中选择主元有一个重要的细微差别,如果我们选择不好的主元,我们最终会得到一个可怕的复杂性,因为每次我们将数组分成两个数组时,我们最终都会得到小的数组,在这种情况下,我们将有 n 次递归调用,并且必须遍历 n 个元素,因此快速排序的最坏情况是 O(n*n),这非常糟糕,所以我们需要小心选择一个主元,一个好的方法是选择一个随机数,通过这样做,我们很确定会得到中间情况,即 O(n * log n), log n 因为在平均情况下,我们将分裂将数组分成两个数组,其中元素为初始数组的一半,并且由于我们必须遍历所有元素,因此存在因子 n.

版本聲明 本文轉載於:https://dev.to/gustrb/quick-sort-1dkg如有侵犯,請聯絡[email protected]刪除
最新教學 更多>
  • Python中嵌套函數與閉包的區別是什麼
    Python中嵌套函數與閉包的區別是什麼
    嵌套函數與python 在python中的嵌套函數不被考慮閉合,因為它們不符合以下要求:不訪問局部範圍scliables to incling scliables在封裝範圍外執行範圍的局部範圍。 make_printer(msg): DEF打印機(): 打印(味精) ...
    程式設計 發佈於2025-04-26
  • 如何解決由於Android的內容安全策略而拒絕加載腳本... \”錯誤?
    如何解決由於Android的內容安全策略而拒絕加載腳本... \”錯誤?
    Unveiling the Mystery: Content Security Policy Directive ErrorsEncountering the enigmatic error "Refused to load the script..." when deployi...
    程式設計 發佈於2025-04-26
  • 可以在純CS中將多個粘性元素彼此堆疊在一起嗎?
    可以在純CS中將多個粘性元素彼此堆疊在一起嗎?
    [2这里: https://webthemez.com/demo/sticky-multi-header-scroll/index.html </main> <section> { display:grid; grid-template-...
    程式設計 發佈於2025-04-26
  • MySQL中如何高效地根據兩個條件INSERT或UPDATE行?
    MySQL中如何高效地根據兩個條件INSERT或UPDATE行?
    在兩個條件下插入或更新或更新 solution:的答案在於mysql的插入中...在重複鍵更新語法上。如果不存在匹配行或更新現有行,則此功能強大的功能可以通過插入新行來進行有效的數據操作。如果違反了唯一的密鑰約束。 實現所需的行為,該表必須具有唯一的鍵定義(在這種情況下為'名稱'...
    程式設計 發佈於2025-04-26
  • 我可以將加密從McRypt遷移到OpenSSL,並使用OpenSSL遷移MCRYPT加密數據?
    我可以將加密從McRypt遷移到OpenSSL,並使用OpenSSL遷移MCRYPT加密數據?
    將我的加密庫從mcrypt升級到openssl 問題:是否可以將我的加密庫從McRypt升級到OpenSSL?如果是這樣,如何? 答案:是的,可以將您的Encryption庫從McRypt升級到OpenSSL。 可以使用openssl。 附加說明: [openssl_decrypt()函數要求...
    程式設計 發佈於2025-04-26
  • 如何在GO編譯器中自定義編譯優化?
    如何在GO編譯器中自定義編譯優化?
    在GO編譯器中自定義編譯優化 GO中的默認編譯過程遵循特定的優化策略。 However, users may need to adjust these optimizations for specific requirements.Optimization Control in Go Compi...
    程式設計 發佈於2025-04-26
  • 在Java中如何為PNG文件添加坐標軸和標籤?
    在Java中如何為PNG文件添加坐標軸和標籤?
    如何用java 在現有png映像中添加軸和標籤的axes和labels如何註釋png文件可能具有挑戰性。與其嘗試可能導致錯誤和不一致的修改,不如建議在圖表創建過程中集成註釋。 使用JFReechArt import java.awt.color; 導入java.awt.eventqueue; 導...
    程式設計 發佈於2025-04-26
  • 如何使用Python理解有效地創建字典?
    如何使用Python理解有效地創建字典?
    在python中,詞典綜合提供了一種生成新詞典的簡潔方法。儘管它們與列表綜合相似,但存在一些顯著差異。 與問題所暗示的不同,您無法為鑰匙創建字典理解。您必須明確指定鍵和值。 For example:d = {n: n**2 for n in range(5)}This creates a dict...
    程式設計 發佈於2025-04-26
  • Python中何時用"try"而非"if"檢測變量值?
    Python中何時用"try"而非"if"檢測變量值?
    使用“ try“ vs.” if”來測試python 在python中的變量值,在某些情況下,您可能需要在處理之前檢查變量是否具有值。在使用“如果”或“ try”構建體之間決定。 “ if” constructs result = function() 如果結果: 對於結果: ...
    程式設計 發佈於2025-04-26
  • 如何實時捕獲和流媒體以進行聊天機器人命令執行?
    如何實時捕獲和流媒體以進行聊天機器人命令執行?
    在開發能夠執行命令的chatbots的領域中,實時從命令執行實時捕獲Stdout,一個常見的需求是能夠檢索和顯示標準輸出(stdout)在cath cath cant cant cant cant cant cant cant cant interfaces in Chate cant inter...
    程式設計 發佈於2025-04-26
  • 為什麼PHP的DateTime :: Modify('+1個月')會產生意外的結果?
    為什麼PHP的DateTime :: Modify('+1個月')會產生意外的結果?
    使用php dateTime修改月份:發現預期的行為在使用PHP的DateTime類時,添加或減去幾個月可能並不總是會產生預期的結果。正如文檔所警告的那樣,“當心”這些操作的“不像看起來那樣直觀。 考慮文檔中給出的示例:這是內部發生的事情: 現在在3月3日添加另一個月,因為2月在2001年只有2...
    程式設計 發佈於2025-04-26
  • 在Ubuntu/linux上安裝mysql-python時,如何修復\“ mysql_config \”錯誤?
    在Ubuntu/linux上安裝mysql-python時,如何修復\“ mysql_config \”錯誤?
    mysql-python安裝錯誤:“ mysql_config找不到”“ 由於缺少MySQL開發庫而出現此錯誤。解決此問題,建議在Ubuntu上使用該分發的存儲庫。使用以下命令安裝Python-MysqldB: sudo apt-get安裝python-mysqldb sudo pip in...
    程式設計 發佈於2025-04-26
  • 如何正確使用與PDO參數的查詢一樣?
    如何正確使用與PDO參數的查詢一樣?
    在pdo 中使用類似QUERIES在PDO中的Queries時,您可能會遇到類似疑問中描述的問題:此查詢也可能不會返回結果,即使$ var1和$ var2包含有效的搜索詞。錯誤在於不正確包含%符號。 通過將變量包含在$ params數組中的%符號中,您確保將%字符正確替換到查詢中。沒有此修改,PD...
    程式設計 發佈於2025-04-26
  • 解決MySQL錯誤1153:數據包超出'max_allowed_packet'限制
    解決MySQL錯誤1153:數據包超出'max_allowed_packet'限制
    mysql錯誤1153:故障排除比“ max_allowed_pa​​cket” bytes 更大的數據包,用於面對陰謀mysql錯誤1153,同時導入數據capase doft a Database dust?讓我們深入研究罪魁禍首並探索解決方案以糾正此問題。 理解錯誤此錯誤表明在導入過程中...
    程式設計 發佈於2025-04-26
  • 如何在其容器中為DIV創建平滑的左右CSS動畫?
    如何在其容器中為DIV創建平滑的左右CSS動畫?
    通用CSS動畫,用於左右運動 ,我們將探索創建一個通用的CSS動畫,以向左和右移動DIV,從而到達其容器的邊緣。該動畫可以應用於具有絕對定位的任何div,無論其未知長度如何。 問題:使用左直接導致瞬時消失 更加流暢的解決方案:混合轉換和左 [並實現平穩的,線性的運動,我們介紹了線性的轉換。...
    程式設計 發佈於2025-04-26

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3