1 基本概念

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

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

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

2 選擇排序

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

3 插入排序

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

4 希爾排序

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

5 冒泡排序

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

6 快速排序

幾個(gè)做法：

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

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

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

思路：

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

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