我的算法筆記—快速排序

superw 發布于2019-08-15 15:32 / 1585人閱讀

摘要：算法介紹由在年提出，因為此算法而獲得圖靈獎。它是一種遞歸算法，核心思想是先找出一個數的應該在的位置，將數列分為左右兩部分，左右兩部分分別進行排序。

算法介紹

由C.A.R.Hoare在1962年提出，因為此算法而獲得圖靈獎。它是一種遞歸算法，核心思想是：先找出一個數的應該在的位置，將數列分為左右兩部分，左右兩部分分別進行排序。

圖片示例

我們先找到 K 的位置，i 指針先向后移動，所指元素如果比K大，就停止，此時再由 j 由隊尾向前遍歷，如果 j 指向元素比K小，j 停止移動，此時將 i 和 j 指向元素對調。
比如：

此時 i 指向元素R比 K 大，j 指向元素C比K小，對調R，C。

此時 i j 根據上述規則繼續移動，一直到指針 j 超過了i ，K 和 j 對調

此時K已經在位置上了，將數列分為左右兩邊，左右再進行遞歸排序

實現代碼

//主方法
private static void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, 0, j - 1);
        sort(a, j + 1, hi);
    }

private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo ;
        int j = hi+1;
//a[lo]即為第一個元素，先將它的位置找到
        while (true){
// 找到 i ，i 小于 a[lo]的話，繼續移動
            while (less(a[++i],a[lo])){
                if(i == hi){
                    break;
                }
            }
// j 也類似
            while (less(a[lo],a[--j])){
                if(j==lo){
                    break;
                }
            }
// 兩指針擦肩而過的話，就跳出循環
            if(i>=j){
                break;
            }
// 交換 i和j
            change(a,i,j);
        }
// 交換 lo和j
        change(a,lo,j);
        return j;
    }

復雜度推導

假設 Cn 為快速排序N個數需要比較的次數。
找到第一個數所在位置，我們需要比較 N+1次。指針 i 和 j 每移動一次就需要比較一次，一共是 N-1次，加上相遇比較一次，擦肩而過還需要比較一次，所以是N+1次。
這個數會把數組分割成各種情況，會分割成(1,n-1),(2,n-2),(3,n-3).......(n-1,1)各種情況，所以Cn的表達式如下：

平均復雜度為1.39NlgN

缺點與不足

 1. 為了保證性能，快速排序前一定要打亂數組順序，正序下，快排復雜度需要1/2 
    乘以n的二次方
    

 2. 如果數組存在大量相同的數，性能也是平方級的

第一次寫博客，這是我的理解，如果有誤請指出，我會立即糾正，謝謝

GPU云服務器云服務器快速排序算法最好的快速排序算法最快速的排序算法快速排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69118.html

【算法】算法圖解筆記_算法簡介

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。在讀《算法圖解》這本書，這本書有兩個優點：手繪風格的圖，看著很讓人入戲；算法采用Python語言描述，能更好的表達算法思想。關于算法的學習有兩點心得：算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上...

tomlingtm 2019-07-31 10:10 評論0 收藏0
算法學習筆記：排序算法(二)

摘要：上一篇中已經介紹了幾個簡單的排序算法，這一篇文章我將繼續向大家介紹排序算法相關的內容，本篇的會介紹希爾排序快速排序歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。上一篇中已經介紹了幾個簡單的排序算法，這一篇文章我將繼續向大家介紹排序算法相關的內容，本篇的會介紹希爾排序、快速排序、歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。希爾排序...

William_Sang 2019-08-23 14:40 評論0 收藏0
【算法】算法圖解筆記_選擇排序

摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數據時有兩種基本方式數組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。選擇排序是下一章將介紹的快速排序的基石。內存的工作原理計算機就像是很多抽屜的集合體,每個抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 評論0 收藏0
【算法】算法圖解筆記_快速排序

摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為?？焖倥判蚝秃喜⑴判虻乃惴ㄋ俣确謩e表示為和，是算法所需的固定時間量被稱為常量。分而治之分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 評論0 收藏0
思維導圖整理大廠面試高頻數組24: 合并兩個有序數組的兩種雙指針思想, 力扣88

摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...

darkerXi 2021-11-17 09:33 評論0 收藏0