1 基本概念

排序是處理數(shù)據(jù)的一種最常見的操作，所謂排序就是將數(shù)據(jù)按某字段規(guī)律排列，所謂的字段就是數(shù)據(jù)節(jié)點(diǎn)的其中一個屬性。比如一個班級的學(xué)生，其字段就有學(xué)號、姓名、班級、分?jǐn)?shù)等等，我們既可以針對學(xué)號排序，也可以針對分?jǐn)?shù)排序。

• 穩(wěn)定性 在一組無序數(shù)據(jù)中，若兩個待排序字段一致的數(shù)據(jù)，在排序前后相對位置不變，則稱排序算法是穩(wěn)定的，否則是不穩(wěn)定的。（應(yīng)該是原先有序的在排序中會不會出現(xiàn)改變）

• 內(nèi)排序與外排序 如果待排序數(shù)據(jù)量不大，可以一次性全部裝進(jìn)內(nèi)存進(jìn)行處理，則稱為內(nèi)排序，若數(shù)據(jù)量大到無法一次性全部裝進(jìn)內(nèi)存，而需要將數(shù)據(jù)暫存外存，分批次讀入內(nèi)存進(jìn)行處理，則稱為外排序。

2 選擇排序

遍歷兩層，復(fù)雜度較高

3 插入排序

減少隊(duì)列和構(gòu)建新的隊(duì)列，新的隊(duì)列插入算法可以優(yōu)化。

4 希爾排序

插入排序的升級版，一開始分成幾組，每組內(nèi)部排序，逐步減少分組數(shù)量。

5 冒泡排序

復(fù)雜度比選擇排序好一些

6 快速排序

幾個做法：

兩端往中間走：在l>k>r時交換；

挖坑移樹法：也是兩端往中間走，將Key位騰出來，存放L和R碰到的大和小的數(shù)據(jù)，

前后指針（交換小的在前）：如圖，重點(diǎn)講，是前面兩種做法的進(jìn)化版，目前也是用的比較多的。

思路：

大原則（跟前面一樣）：用一個Key來分割所有數(shù)據(jù)成為“<K<”，然后繼續(xù)前后分別遞歸繼續(xù)；

分割時：用一個cur游標(biāo)，從頭找到尾，找出小的數(shù)據(jù)放到“后面隊(duì)列”，用一個Prev（后面隊(duì)列的車頭）來推動大的數(shù)據(jù)將cur發(fā)現(xiàn)的小數(shù)交換到后面。