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

快速排序

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

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]刪除
最新教學 更多>
  • 如何使用Regex在PHP中有效地提取括號內的文本
    如何使用Regex在PHP中有效地提取括號內的文本
    php:在括號內提取文本在處理括號內的文本時,找到最有效的解決方案是必不可少的。一種方法是利用PHP的字符串操作函數,如下所示: 作為替代 $ text ='忽略除此之外的一切(text)'; preg_match('#((。 &&& [Regex使用模式來搜索特...
    程式設計 發佈於2025-04-05
  • 如何使用不同數量列的聯合數據庫表?
    如何使用不同數量列的聯合數據庫表?
    合併列數不同的表 當嘗試合併列數不同的數據庫表時,可能會遇到挑戰。一種直接的方法是在列數較少的表中,為缺失的列追加空值。 例如,考慮兩個表,表 A 和表 B,其中表 A 的列數多於表 B。為了合併這些表,同時處理表 B 中缺失的列,請按照以下步驟操作: 確定表 B 中缺失的列,並將它們添加到表的...
    程式設計 發佈於2025-04-05
  • 如何從PHP中的Unicode字符串中有效地產生對URL友好的sl。
    如何從PHP中的Unicode字符串中有效地產生對URL友好的sl。
    為有效的slug生成首先,該函數用指定的分隔符替換所有非字母或數字字符。此步驟可確保slug遵守URL慣例。隨後,它採用ICONV函數將文本簡化為us-ascii兼容格式,從而允許更廣泛的字符集合兼容性。 接下來,該函數使用正則表達式刪除了不需要的字符,例如特殊字符和空格。此步驟可確保slug僅包...
    程式設計 發佈於2025-04-05
  • 如何在php中使用捲髮發送原始帖子請求?
    如何在php中使用捲髮發送原始帖子請求?
    如何使用php 創建請求來發送原始帖子請求,開始使用curl_init()開始初始化curl session。然後,配置以下選項: curlopt_url:請求 [要發送的原始數據指定內容類型,為原始的帖子請求指定身體的內容類型很重要。在這種情況下,它是文本/平原。要執行此操作,請使用包含以下標頭...
    程式設計 發佈於2025-04-05
  • 如何正確使用與PDO參數的查詢一樣?
    如何正確使用與PDO參數的查詢一樣?
    在pdo 中使用類似QUERIES在PDO中的Queries時,您可能會遇到類似疑問中描述的問題:此查詢也可能不會返回結果,即使$ var1和$ var2包含有效的搜索詞。錯誤在於不正確包含%符號。 通過將變量包含在$ params數組中的%符號中,您確保將%字符正確替換到查詢中。沒有此修改,PD...
    程式設計 發佈於2025-04-05
  • 如何從PHP中的數組中提取隨機元素?
    如何從PHP中的數組中提取隨機元素?
    從陣列中的隨機選擇,可以輕鬆從數組中獲取隨機項目。考慮以下數組:; 從此數組中檢索一個隨機項目,利用array_rand( array_rand()函數從數組返回一個隨機鍵。通過將$項目數組索引使用此鍵,我們可以從數組中訪問一個隨機元素。這種方法為選擇隨機項目提供了一種直接且可靠的方法。
    程式設計 發佈於2025-04-05
  • 如何有效地轉換PHP中的時區?
    如何有效地轉換PHP中的時區?
    在PHP 利用dateTime對象和functions DateTime對象及其相應的功能別名為時區轉換提供方便的方法。例如: //定義用戶的時區 date_default_timezone_set('歐洲/倫敦'); //創建DateTime對象 $ dateTime = ne...
    程式設計 發佈於2025-04-05
  • 如何使用替換指令在GO MOD中解析模塊路徑差異?
    如何使用替換指令在GO MOD中解析模塊路徑差異?
    在使用GO MOD時,在GO MOD 中克服模塊路徑差異時,可能會遇到衝突,其中3個Party Package將另一個PAXPANCE帶有導入式套件之間的另一個軟件包,並在導入式套件之間導入另一個軟件包。如迴聲消息所證明的那樣: go.etcd.io/bbolt [&&&&&&&&&&&&&&&&...
    程式設計 發佈於2025-04-05
  • 如何限制動態大小的父元素中元素的滾動範圍?
    如何限制動態大小的父元素中元素的滾動範圍?
    在交互式接口中實現垂直滾動元素的CSS高度限制問題:考慮一個佈局,其中我們具有與用戶垂直滾動一起移動的可滾動地圖div,同時與固定的固定sidebar保持一致。但是,地圖的滾動無限期擴展,超過了視口的高度,阻止用戶訪問頁面頁腳。 映射{} 因此。我們不使用jQuery的“ .aimimate...
    程式設計 發佈於2025-04-05
  • Java是否允許多種返回類型:仔細研究通用方法?
    Java是否允許多種返回類型:仔細研究通用方法?
    在Java中的多個返回類型:一種誤解類型:在Java編程中揭示,在Java編程中,Peculiar方法簽名可能會出現,可能會出現,使開發人員陷入困境,使開發人員陷入困境。 getResult(string s); ,其中foo是自定義類。該方法聲明似乎擁有兩種返回類型:列表和E。但這確實是如此嗎...
    程式設計 發佈於2025-04-05
  • 如何將來自三個MySQL表的數據組合到新表中?
    如何將來自三個MySQL表的數據組合到新表中?
    mysql:從三個表和列的新表創建新表 答案:為了實現這一目標,您可以利用一個3-way Join。 選擇p。 *,d.content作為年齡 來自人為p的人 加入d.person_id = p.id上的d的詳細信息 加入T.Id = d.detail_id的分類法 其中t.taxonomy ...
    程式設計 發佈於2025-04-05
  • 為什麼使用Firefox後退按鈕時JavaScript執行停止?
    為什麼使用Firefox後退按鈕時JavaScript執行停止?
    導航歷史記錄問題:JavaScript使用Firefox Back Back 此行為是由瀏覽器緩存JavaScript資源引起的。要解決此問題並確保在後續頁面訪問中執行腳本,Firefox用戶應設置一個空功能。 警報'); }; alert('inline Alert')...
    程式設計 發佈於2025-04-05
  • 如何克服PHP的功能重新定義限制?
    如何克服PHP的功能重新定義限制?
    克服PHP的函數重新定義限制在PHP中,多次定義一個相同名稱的函數是一個no-no。嘗試這樣做,如提供的代碼段所示,將導致可怕的“不能重新列出”錯誤。 但是,PHP工具腰帶中有一個隱藏的寶石:runkit擴展。它使您能夠靈活地重新定義函數。 runkit_function_renction_...
    程式設計 發佈於2025-04-05
  • 如何解決由於Android的內容安全策略而拒絕加載腳本... \”錯誤?
    如何解決由於Android的內容安全策略而拒絕加載腳本... \”錯誤?
    Unveiling the Mystery: Content Security Policy Directive ErrorsEncountering the enigmatic error "Refused to load the script..." when deployi...
    程式設計 發佈於2025-04-05
  • 如何使用Python的請求和假用戶代理繞過網站塊?
    如何使用Python的請求和假用戶代理繞過網站塊?
    如何使用Python的請求模擬瀏覽器行為,以及偽造的用戶代理提供了一個用戶 - 代理標頭一個有效方法是提供有效的用戶式header,以提供有效的用戶 - 設置,該標題可以通過browser和Acterner Systems the equestersystermery和操作系統。通過模仿像Chro...
    程式設計 發佈於2025-04-05

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

Copyright© 2022 湘ICP备2022001581号-3