排序算法
我們通常所說的排序算法是指內(nèi)部排序算法酪夷，即數(shù)據(jù)記錄在內(nèi)存中進行排序毡代。
排序算法大致分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序葵袭，插入排序，歸并排序，堆排序欠窒，快速排序等。
另一種是非比較排序退子，時間復雜度可以達到O(n)贱迟，主要有：計數(shù)排序姐扮，基數(shù)排序，桶排序等
算法的穩(wěn)定性：冒泡衣吠，直接插入茶敏，歸并
算法的穩(wěn)定性是指若Ai=Aj,在排序之前的相對順序是Ai在Aj之前，那么進行排序之后Ai還應該在Aj之前缚俏，即算法是穩(wěn)定的
內(nèi)部排序算法：
1.冒泡排序
核心思想：
1.比較相鄰元素惊搏，如果前一個比后一個大，就把它們兩個調(diào)換位置忧换。
對每一對相鄰元素作同樣的工作恬惯，從開始第一對到結(jié)尾的最后一對。這步做完后亚茬，最后的元素會是最大的數(shù)酪耳。
2.針對所有的元素重復以上的步驟，除了最后一個刹缝。
3.持續(xù)每次對越來越少的元素重復上面的步驟碗暗，直到?jīng)]有任何一對數(shù)字需要比較。
簡單優(yōu)化冒泡排序：
2.選擇排序
核心算法：選擇排序也是一種簡單直觀的排序算法梢夯。（以從小到大的排序為例言疗。）
1、初始時在序列中找到最小元素颂砸，放到序列的起始位置作為已排序序列噪奄；
2、然后人乓，再從剩余未排序元素中繼續(xù)尋找最小元素勤篮，放到已排序序列的末尾。以此類推色罚，直到所有元素均排序完畢碰缔。
3.插入排序
插入算法用于滿足一定條件時，可以提前結(jié)束保屯，所以插入排序?qū)τ诮朴行虻男蛄衼碚f手负，效率很高。插入算法通常與其他排序算法進行組合姑尺，從而減少運行時間
核心思想：1.將元素拿出來
? ? ? ? ? ? ? ? ? ?2.將符合條件的元素后移
4.希爾排序
希爾排序是對插入排序的一個改進竟终，首先引入分組的思想，從而將算法的時間復雜度降低到O（nlogn）
5.快速排序
核心思想：
對于一個無序list切蟋，取index為0的元素作為中間數(shù)统捶，然后執(zhí)行分區(qū)函數(shù)，讓比中間數(shù)小的點都在中間數(shù)左邊，比中間數(shù)大的點都在中間數(shù)右邊喘鸟。此時得到了一個看似有序其實無序的list：
有序體現(xiàn)在此時list分成了兩個區(qū)域匆绣，左邊的都比中間數(shù)小，右邊的都比中間數(shù)大什黑。
無序體現(xiàn)在崎淳，而這兩個區(qū)域，又都是無序的list
算法步驟：
1.基準點選取：快速排序首先需要先選擇一個值作為基準點愕把，一般選擇是arr[0]拣凹，但是當數(shù)據(jù)出現(xiàn)近乎有序時，則比較復雜恨豁。因此基準點一般是隨機選取一個值嚣镜，在數(shù)學上會以很大的概率使算法的復雜度接近（O(nlogn)），極小的概率為O(n^2)
2.我們對這兩個無序的list再次調(diào)用分區(qū)函數(shù)橘蜜，此時會得到四個看似有序而又無序的list菊匿，接著調(diào)用分區(qū)函數(shù)，直到最終list長度為2時计福，再調(diào)用一次分區(qū)函數(shù)跌捆，那么一定是左邊有序并且小于右邊，因此此時所有的子列表都是有序的棒搜，那么此時一整個list也就是一個有序的list了疹蛉。
左邊的無序區(qū)域為nums[first:index-1]
右邊的無序區(qū)域為nums[index+1,last]
代碼如下：
6.歸并排序：
最易于理解的白話：首先考慮下如何將將二個有序數(shù)列合并
1活箕、這個非常簡單力麸，只要從比較二個數(shù)列的第一個數(shù)，誰小就先取誰育韩，取了后就在對應數(shù)列中刪除這個數(shù)克蚂。
2、然后再進行比較筋讨，如果有數(shù)列為空埃叭，那直接將另一個數(shù)列的數(shù)據(jù)依次取出即可。
比如悉罕，13跟24678合并赤屋。
1跟2比較，1小于2壁袄，那么list.append(1)类早。
3跟2比較，2小于3嗜逻，那么list.append(2)
3跟4比較涩僻，3小于4，那么list.append(3)
left數(shù)列已經(jīng)為空，那么就把right的數(shù)列都append到list中逆日。
核心思想：
那么歸并排序呢嵌巷，一樣的道理。但是不一樣的地方就是室抽，一開始不是兩個有序list搪哪，而是是一整個無序list，為了滿足“兩個坪圾，有序”的要求噩死，我們分兩步：
1、先把list分成left和right兩個無序的部分
2神年、把這兩個無序的部分已维，調(diào)用函數(shù)排成兩個有序的部分
這里的兩個無序的部分怎么排序成有序的部分呢。就是遞歸調(diào)用歸并排序函數(shù)了已日。
3垛耳、對兩個有序的部分，進行上面的merge操作即可飘千。
其中遞歸的地方就是堂鲜，上面的第二步中，上面的
