
數據結構與算法之排序
堆排序、快速排序、希爾排序、直接選擇排序不是穩(wěn)定的排序算法,而基數排序、冒泡排序、直接插入排序、折半插入排序、鏈表插入排序、歸并排序是穩(wěn)定的排序算法。
直接插入排序 T(n) = O(n^2)
直接插入排序「Insertion Sort」的基本思想是:每次將一個待排序的記錄,按其關鍵字大小插入到前面已經排好序的子序列中的適當位置,直到全部記錄插入完成為止。
設數組為a[0…n-1]:
1. 初始時,a[0]自成1個有序區(qū),無序區(qū)為a[1..n-1]。令i=1。
2. 將a[i]并入當前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間。
3. i++并重復第二步直到i==n-1。排序完成。
折半插入排序 T(n) = O(n^2)
折半插入排序是對直接插入排序的簡單改進,對于折半插入排序而言,當需要插入第i個元素時,它不會逐個進行比較每個元素,而是:
1. 計算0~i-1索引的中間點,也就是用i索引處的元素和(0+i-1)/2索引處的元素進行比較,如果i索引處的元素值大,就直接在(0+i-1)/2~i-1半個范圍內進行搜索;反之在0~(0+i-1)/2半個范圍內搜索,這就是所謂的折半
2. 在半個范圍內搜索時,按照1的方法不斷地進行折半搜索,這樣就可以將搜索范圍縮小到1/2、1/4、1/8…,從而快速的確定插入位置
鏈表插入排序 T(n) = O(n^2)
鏈表插入排序的基本思想是:假設前 n-1個節(jié)點有序,取最后節(jié)點,沿鏈表依次查找比較,直到合適位置,修改「本節(jié)點」和「待插入節(jié)點」的指針。
1. 沿頭節(jié)點遍歷鏈表,比較此節(jié)點、待插入節(jié)點、后繼節(jié)點的大小關系,直到:此節(jié)點 < 待插入節(jié)點 < 后繼節(jié)點。
2. 令「此節(jié)點」指向「待插入節(jié)點」,「待插入節(jié)點」指向「后繼節(jié)點」。
Shell 排序(希爾排序) T(n) = O(n^1.5)
希爾排序的實質就是分組插入排序,該方法又稱縮小增量排序。該方法的基本思想是:
1. 先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成的)分別進行直接插入排序
2. 然后依次縮減增量再進行排序,待整個序列中的元素基本有序(增量足夠小,1)時,再對全體元素進行一次直接插入排序
冒泡排序 T(n) = O(n^2)
冒泡排序的基本思想是,對相鄰的元素進行兩兩比較,順序相反則進行交換,這樣,每一趟會將最小或最大的元素“浮”到頂端,最終達到完全有序。
快速排序 范圍T(n) = O(n*lg n) ~ O(n^2) | 平均T(n) = O(n*lg n)
快速排序采用了分治(遞歸)的方法,該方法的基本思想是:
先從數列中取出一個數作為基準數
分區(qū)過程,將比這個數大的數全放到它的右邊,小于或等于它的數全放到它的左邊
再對左右區(qū)間重復第二步,直到各區(qū)間只有一個數
直接選擇排序 T(n) = O(n^2)
直接選擇排序(Straight Select Sorting) 也是一種簡單的排序方法,它的基本思想是:
1. 從R[0]~R[n-1]中選取最小值,與R[0]交換
2. 從R{1}~R[n-1]中選取最小值,與R[1]交換
3. 第i次從R[i-1]~R[n-1]中選取最小值,與R[i-1]交換
堆選擇排序 T(n) = O(n*log2n)
堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法,它是選擇排序的一種。堆分為大根堆和小根堆,下圖為小根堆:
「如圖所示依次類推」
歸并排序 T(n) = O(n*log2n)
歸并排序是建立在歸并操作上的一種有效的排序算法,采用了分治思想。如下圖的二路歸并:
基數排序
基數排序(radix sort)屬于「分配式排序」,有點類似 「桶排」。
1. 分配10個桶,桶編號為0-9,以個位數數字為桶編號依次入桶,將桶里的數字順序取出來
2. 再次入桶,不過這次以十位數的數字為準,進入相應的桶,同一桶內有序
3. 再次取出,排序完成
數據分析咨詢請掃描二維碼
若不方便掃碼,搜微信號:CDAshujufenxi
LSTM 模型輸入長度選擇技巧:提升序列建模效能的關鍵? 在循環(huán)神經網絡(RNN)家族中,長短期記憶網絡(LSTM)憑借其解決長序列 ...
2025-07-11CDA 數據分析師報考條件詳解與準備指南? ? 在數據驅動決策的時代浪潮下,CDA 數據分析師認證愈發(fā)受到矚目,成為眾多有志投身數 ...
2025-07-11數據透視表中兩列相乘合計的實用指南? 在數據分析的日常工作中,數據透視表憑借其強大的數據匯總和分析功能,成為了 Excel 用戶 ...
2025-07-11尊敬的考生: 您好! 我們誠摯通知您,CDA Level I和 Level II考試大綱將于 2025年7月25日 實施重大更新。 此次更新旨在確保認 ...
2025-07-10BI 大數據分析師:連接數據與業(yè)務的價值轉化者? ? 在大數據與商業(yè)智能(Business Intelligence,簡稱 BI)深度融合的時代,BI ...
2025-07-10SQL 在預測分析中的應用:從數據查詢到趨勢預判? ? 在數據驅動決策的時代,預測分析作為挖掘數據潛在價值的核心手段,正被廣泛 ...
2025-07-10數據查詢結束后:分析師的收尾工作與價值深化? ? 在數據分析的全流程中,“query end”(查詢結束)并非工作的終點,而是將數 ...
2025-07-10CDA 數據分析師考試:從報考到取證的全攻略? 在數字經濟蓬勃發(fā)展的今天,數據分析師已成為各行業(yè)爭搶的核心人才,而 CDA(Certi ...
2025-07-09【CDA干貨】單樣本趨勢性檢驗:捕捉數據背后的時間軌跡? 在數據分析的版圖中,單樣本趨勢性檢驗如同一位耐心的偵探,專注于從單 ...
2025-07-09year_month數據類型:時間維度的精準切片? ? 在數據的世界里,時間是最不可或缺的維度之一,而year_month數據類型就像一把精準 ...
2025-07-09CDA 備考干貨:Python 在數據分析中的核心應用與實戰(zhàn)技巧? ? 在 CDA 數據分析師認證考試中,Python 作為數據處理與分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 檢驗:數據趨勢與突變分析的有力工具? ? ? 在數據分析的廣袤領域中,準確捕捉數據的趨勢變化以及識別 ...
2025-07-08備戰(zhàn) CDA 數據分析師考試:需要多久?如何規(guī)劃? CDA(Certified Data Analyst)數據分析師認證作為國內權威的數據分析能力認證 ...
2025-07-08LSTM 輸出不確定的成因、影響與應對策略? 長短期記憶網絡(LSTM)作為循環(huán)神經網絡(RNN)的一種變體,憑借獨特的門控機制,在 ...
2025-07-07統(tǒng)計學方法在市場調研數據中的深度應用? 市場調研是企業(yè)洞察市場動態(tài)、了解消費者需求的重要途徑,而統(tǒng)計學方法則是市場調研數 ...
2025-07-07CDA數據分析師證書考試全攻略? 在數字化浪潮席卷全球的當下,數據已成為企業(yè)決策、行業(yè)發(fā)展的核心驅動力,數據分析師也因此成為 ...
2025-07-07剖析 CDA 數據分析師考試題型:解鎖高效備考與答題策略? CDA(Certified Data Analyst)數據分析師考試作為衡量數據專業(yè)能力的 ...
2025-07-04SQL Server 字符串截取轉日期:解鎖數據處理的關鍵技能? 在數據處理與分析工作中,數據格式的規(guī)范性是保證后續(xù)分析準確性的基礎 ...
2025-07-04CDA 數據分析師視角:從數據迷霧中探尋商業(yè)真相? 在數字化浪潮席卷全球的今天,數據已成為企業(yè)決策的核心驅動力,CDA(Certifie ...
2025-07-04CDA 數據分析師:開啟數據職業(yè)發(fā)展新征程? ? 在數據成為核心生產要素的今天,數據分析師的職業(yè)價值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03