- 排序算法的穩(wěn)定性：就是相同值的兩個(gè)元素會(huì)不會(huì)改變它們的次序闽铐，不改變就是穩(wěn)定源譬，改變了就是不穩(wěn)定睬捶。
選擇排序
基本思想：從首個(gè)開始屈藐，過濾整個(gè)數(shù)據(jù)找到第一小和首位進(jìn)行交換奶赠。下一輪從第二個(gè)開始找到第二小和第二位交換……
冒泡排序
基本思想：相鄰兩數(shù)比較鱼填，交換，大的放后面毅戈。
和選擇排序的不同在于：相鄰的進(jìn)行比較苹丸、交換……
插入排序
簡(jiǎn)單排序中最好用的一種。
基本思想：（可以類比于打撲克牌時(shí)在自己手里整理牌）前方的是已排好序的部分（起初數(shù)量為 1 個(gè)）苇经，后面的逐個(gè)插入到前方已排好序的部分（插入的位置之后的有序的位置順序后移）赘理。
希爾排序
改進(jìn)的插入排序。
基本思想：以固定間隔對(duì)應(yīng)的值先排序（插排）扇单；縮小間隔直到間隔為 1商模。
優(yōu)點(diǎn)主要在：間隔大時(shí)移動(dòng)的個(gè)數(shù)少；間隔小時(shí)移動(dòng)的距離短令花。
歸并排序
基本思想：（分塊遞歸）f(n) 為數(shù)組分兩半阻桅，分別對(duì)兩半進(jìn)行排序（同樣用 f(n)），最后將兩半整合（二路歸并）兼都。
時(shí)間復(fù)雜度： N 個(gè)數(shù)大概分 logN 次，每個(gè)小組排序時(shí)間大概為 N稽寒，所以是 O(NlogN)
空間復(fù)雜度：因?yàn)槭褂昧司歪尫帕税绫蹋詢H O(N)
一般語(yǔ)言的對(duì)象排序都是歸并排序（如 java、python）。對(duì)象排序一般要求穩(wěn)定慎王。
快速排序
快排中經(jīng)典的叫“單軸快排”蚓土，改進(jìn)的叫“雙軸快排”。軸（pivot）赖淤。
基本思想：以軸為中心蜀漆，將比軸小的排前面，大的分后面咱旱；（遞歸）將軸外兩部分再次按軸進(jìn)行分……直到軸兩邊的元素少于 1 個(gè)确丢。
實(shí)現(xiàn)方式有優(yōu)有劣，關(guān)鍵在于找中軸的兩側(cè)塊的方法（哪個(gè)是軸可以任意選）：
- 從一側(cè)出發(fā)吐限，小于軸的掠過鲜侥，大于軸的放后面，最后將軸放在合適的位置（和最后一個(gè)小于等于軸的進(jìn)行交換）诸典。
- 從兩側(cè)出發(fā)（略過軸）描函，前側(cè)找小于軸的，后側(cè)找大于軸的狐粱，兩者都找到不符合的舀寓，交換一下，繼續(xù)找肌蜻，最后將軸放在合適的位置基公。
時(shí)間復(fù)雜度：每分一次需要遍歷 N 次，分的次數(shù)為 logN 次（每次分兩半嘛）宋欺，所以時(shí)間復(fù)雜度為 N*logN轰豆。
空間復(fù)雜度：因?yàn)槊糠值囊徊糠侄夹枰R時(shí)變量，所以為 logN
- 雙軸快排：兩個(gè)軸齿诞，分三部分酸休。
工業(yè)上的數(shù)組排序（Array.sort() 內(nèi)部實(shí)現(xiàn)，提前預(yù)判）
- 一小塊一小塊排得比較好祷杈，歸并
- 數(shù)組短斑司，插入
- 然后考慮快排
- 取 5 個(gè)數(shù)，相等但汞，單軸
- 不相等宿刮，雙軸
計(jì)數(shù)排序
非比較排序；桶思想的一種私蕾。桶排序都是非比較的排序僵缺。
適用范圍：數(shù)組元素的個(gè)數(shù)比較大，但值都比較小踩叭。如員工年齡磕潮。
基本思想：數(shù)組的下標(biāo)做為要排序的值翠胰，數(shù)組元素值作為個(gè)數(shù)。
空間復(fù)雜度： N+K自脯，N 是排序結(jié)果數(shù)組之景，K 為桶的個(gè)數(shù)。
時(shí)間復(fù)雜度：N+K膏潮，N 為元素加加的次數(shù)锻狗，就是元素的個(gè)數(shù)；K 為返回結(jié)果時(shí)對(duì)桶的遍歷焕参。
計(jì)數(shù)排序變成穩(wěn)定的：需要再遍歷原數(shù)組轻纪，按序生成目標(biāo)數(shù)組。
基數(shù)排序
非比較排序龟糕；桶排序的一種桐磁。基數(shù)排序本質(zhì)是一種多關(guān)鍵字的排序讲岁。
基本思想：
- 先按個(gè)位數(shù)進(jìn)行排序我擂，一樣的放一個(gè)桶中，再按順序取出（桶按由小到大排序）缓艳；
- 再按十位數(shù)進(jìn)行排序校摩，一樣的放一個(gè)桶中，再按順序取出阶淘；
- 再按高一位的繼續(xù)重復(fù)上一步衙吩，不足的位數(shù)按此位為 0 計(jì)，直到取到最高位……
- 由于放入和取出是有順序的溪窒，所以在最后取出后結(jié)果是由小到大排好序的坤塞。
空間復(fù)雜度： 可以做到 O(N)。（靠編程技巧）
時(shí)間復(fù)雜度： 就是一次一次復(fù)制澈蚌。O(N*K)摹芙，N 為數(shù)據(jù)量的個(gè)數(shù)，K 為建一系列桶的次數(shù)宛瞄，也就是數(shù)據(jù)的位數(shù)浮禾。
總結(jié)：
- 本質(zhì)是一種多關(guān)鍵字的排序
- 有低位優(yōu)先和高位優(yōu)先兩種
- LSD（Least Significant Digit first）低位優(yōu)先，如上份汗。
- MSD（Least Significant Digit first） 高位優(yōu)先盈电。遞歸的思想（我自己的容器的思想）。
桶排序
基本思想：通過分桶杯活，進(jìn)行排序匆帚，桶內(nèi)再單獨(dú)排序。最后按順序輸出轩猩。
普通的桶算法排序不常用卷扮，只有特殊場(chǎng)景才有用荡澎。原因：
- 桶內(nèi)還需要排序
- 不好分桶
- 桶不好用數(shù)據(jù)存
- 若用 ArrayList（go 里是 slice）會(huì)有數(shù)據(jù)空間增長(zhǎng)的問題均践。
- 若用鏈表晤锹，鏈表的排序特別麻煩，相當(dāng)于冒泡思想彤委。
它的時(shí)間復(fù)雜度和空間復(fù)雜度也相當(dāng)麻煩鞭铆。
