Quick Sort 與 Quick Selection 衍生

Neilyo 發布于2019-08-16 10:33 / 3201人閱讀

摘要：理解最關鍵的是結束后各個指針的狀態，以及下一步遞歸的起止點。上面的模板在結束時是的狀態，但是不確定中間還有沒有一個數，如下圖今天在圖書館寫碼沒有帶板子，就先照個圖了注意里是里一定要注意這個靈活多變照這個思路的相關題

首先是記錄一個quick sort的模板（思想是遇到不符合順序的就交換，很好理解）：
public void quickSort(int[] nums, int start, int end){

if(start < end){
    int i = start;
    int j = end;
    int pivot = nums[(i + j) / 2];
    
    while(i <= j){
        while(i <= j && nums[i] < pivot){
            i++;
        }
        while(i <= j && nums[j] > pivot){
            j--;
        }
        if(i <= j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    
    quickSort(nums, start, j);
    quickSort(nums, i, end);
}

}
基于快速排序里這個pivot的思想，有一個衍生quick Select, 用來解決一些類似于求中位數啦，kth數字啦之類（第幾個第幾個可以聯想到pivot）的問題，時間復雜度也比快速排序有所降低。理解quick sort, quick select最關鍵的是結束partition后各個指針的狀態，以及下一步遞歸的起止點。上面的模板在結束時是i

注意quickSort里是（start < end）, quickSelect里一定要注意這個靈活多變
照這個思路的相關題：
[LeetCode 215] Kth Largest Element in an Array

GPU云服務器云服務器 Quick qt quick Quick BI 數據庫 quick-look-framework

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

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

Sorting

摘要：是穩定的排序，但是它需要額外的空間，時間復雜度為程序這個同上也是兩個步驟，。最壞情況的時間復雜度為但是在實際情況中，通常是排序的最佳選擇。就是有序的完全二叉樹，所有我們要先根據已有的數組來建立一個。最后由后往前形成一個有序數組。 Bubble Sort就不說了，下面簡單總結一個Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

calx 2019-08-14 14:09 評論0 收藏0
排序算法sort.js(看源碼，把它背下來吧)

摘要：對于實在不能理解的同學，聽我的吧這是死東西，那你就背下來背下來背下來。就說三遍，背完之后，還不能理解，那我也不能理解了。 sort.js JavaScript to achieve the ten common sorting algorithm library 這個小庫是對常見的十大排序算法的一個基本匯總，建議讀者直接看源碼|看源碼|看源碼。別怕，我注釋十分清晰，你要是還看不懂，給...

史占廣 2019-08-20 14:18 評論0 收藏0
[LintCode] Sort Integers II [Merge-sort, Quick-sor

Problem Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm. Example Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5]. Note 考察對Heap Sort, Q...

YorkChen 2019-08-14 14:23 評論0 收藏0
幾種排序算法及 Python 實現

摘要：因為直接插入排序在元素基本有序的情況下接近最好情況，效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。插入排序 def insert_sort(list): n = len(list) for i in range(1, n): key = list[i] for j in range(i-1, -1, -1): ...

cod7ce 2019-07-31 11:05 評論0 收藏0
2017年最受歡迎的UI框架

摘要：年馬上到尾聲了，在這里總結一下基于和這四大框架衍生的，經受過時間檢驗深受廣大開發者歡迎的框架。可以說是年最火的引擎類前端框架，以其美觀的設計和高質量的組件很快俘獲了一大批的芳心。　　前端領域最近幾年發展的特別迅速，可以說是百家爭鳴。在底層的前端框架領域中，最早是jquery稱霸互聯網，近兩年MVVM類型的框架慢慢成為主流，Vue、React和Angular三大框架并駕齊驅。可以說，目...

ernest.wang 2019-07-01 12:24 評論0 收藏0