排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。
各種排序算法的時間復雜度與空間復雜度
1.冒泡排序
平均時間復雜度：O(n2)，空間復雜度：O(1)
原理：比較兩個相鄰的元素，將值大的元素交換至右端。
思路：依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續(xù)，直至比較最后兩個數，將小數放前，大數放后。重復第一趟步驟，直至全部排序完成。
第一趟比較完成后，最后一個數一定是數組中最大的一個數，所以第二趟比較的時候最后一個數不參與比較；
第二趟比較完成后，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最后兩個數不參與比較；
依次類推，每一趟比較次數-1；
https://www.cnblogs.com/shen-hua/p/5422676.html
2.快速排序
最差情況時間復雜度：O(n2),平均時間復雜度：O(n㏒n)，
最差空間復雜度：O(n),平均空間復雜度：O(㏒n)
原理：采用分治法，找一個基準值base，然后一趟排序后讓base左邊的數都小于base，base右邊的數都大于等于base。再分為兩個子序列的排序。如此遞歸下去。
思路：
1.假設我們對數組{7, 1, 3, 5, 13, 9, 3, 6, 11}進行快速排序。
2.首先在這個序列中找一個數作為基準數，為了方便可以取第一個數。
3.遍歷數組，將小于基準數的放置于基準數左邊，大于基準數的放置于基準數右邊。
4.此時得到類似于這種排序的數組{3, 1, 3, 5, 6, 7, 9, 13, 11}。
5.在初始狀態(tài)下7是第一個位置，現在需要把7挪到中間的某個位置k，也即k位置是兩邊數的分界點。
6.那如何做到把小于和大于基準數7的值分別放置于兩邊呢，我們采用雙指針法，從數組的兩端分別進行比對。
7.先從最右位置往左開始找直到找到一個小于基準數的值，記錄下該值的位置（記作 i）。
8.再從最左位置往右找直到找到一個大于基準數的值，記錄下該值的位置（記作 j）。
9.如果位置i<j，則交換i和j兩個位置上的值，然后繼續(xù)從(j-1)的位置往前和(i+1)的位置往后重復上面比對基準數然后交換的步驟。
10.如果執(zhí)行到i==j，表示本次比對已經結束，將最后i的位置的值與基準數做交換，此時基準數就找到了臨界點的位置k，位置k兩邊的數組都比當11.前位置k上的基準值或都更小或都更大。
12.上一次的基準值7已經把數組分為了兩半，基準值7算是已歸位（找到排序后的位置）。
13.通過相同的排序思想，分別對7兩邊的數組進行快速排序，左邊對[left, k-1]子數組排序，右邊則是[k+1, right]子數組排序。
14.利用遞歸算法，對分治后的子數組進行排序
視頻講解：https://www.bilibili.com/video/BV1at411T75o?from=search&seid=11850390336386266207
https://www.cnblogs.com/captainad/archive/2019/06/10/10999697.html
3.直接插入排序
平均時間復雜度：O(n2)
空間復雜度：O(1)
介紹時可以舉一個抽撲克牌的例子
原理：將一個記錄插入到已排序好的有序表中，從而得到一個新的，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
馬士兵講解插入排序：https://www.bilibili.com/video/BV1kb411x7dw?from=search&seid=1301897921005467603
4.希爾排序（改進版的直接插入排序，又稱為縮小增量排序）
實現有點難理解，可以介紹下實現原理
由希爾Donald Shell于1959年提出來
平均時間復雜度：希爾排序的時間復雜度和其增量序列有關系，這涉及到數學上尚未解決的難題；不過在某些序列中復雜度可以為O(n^1.3)
原理：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
增量序列或者說步長序列的選擇：
增量序列的選擇是希爾排序的重要部分。只要最終增量序列為1，任何增量序列都可以工作。目前還沒有人給出選取最好的增量序列的方法。
Donald Shell最初建議增量序列為n/2，一直對增量序列取半，直到增量序列達到1。注意，最后一個增量序列必須為1！
馬士兵講解：https://www.bilibili.com/video/BV1Pb411s7CN?from=search&seid=16607498154211701899
5.簡單選擇排序
原理：在要排序的一組數中，選出最?。ɑ蛘咦畲螅┑囊粋€數與第1個位置的數交換；然后在剩下的數當中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較完為止。
視頻講解：https://www.bilibili.com/video/BV17t411v7Ru?from=search&seid=540768407119432537
https://blog.csdn.net/wangkuifeng0118/article/details/7289594
6.堆排序
堆排序是利用堆這種數據結構而設計的一種排序算法，是一種選擇排序
堆結構：堆，又稱二叉堆，它的邏輯結構是一棵完全二叉樹，但物理結構是順序表（一維數組），可以按照層序遍歷的順序將元素放入一維數組中。
堆分為大頂堆（大根堆）、小頂堆（小根堆）
大頂堆：根節(jié)點最大，左、右孩子節(jié)點都比當前節(jié)點要小
小頂堆：根節(jié)點最小，左、右孩子節(jié)點都比當前節(jié)點要大
堆排序的步驟：
a.將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;
c.重新調整結構，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調整+交換步驟，直到整個序列有序。
關于數據結構堆的介紹：http://m.itdecent.cn/p/6b526aa481b1
