排序有内部排序和外部排序，内部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要通路外存。
各種排序算法的時間複雜度與空間複雜度
1.冒泡排序
平均時間複雜度：O(n²)，空間複雜度：O(1)
原理：比較兩個相鄰的元素，将值大的元素交換至右端。
思路：依次比較相鄰的兩個數，将小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，将小數放前，大數放後。然後比較第2個數和第3個數，将小數放前，大數放後，如此繼續，直至比較最後兩個數，将小數放前，大數放後。重複第一趟步驟，直至全部排序完成。
第一趟比較完成後，最後一個數一定是數組中最大的一個數，是以第二趟比較的時候最後一個數不參與比較；
第二趟比較完成後，倒數第二個數也一定是數組中第二大的數，是以第三趟比較的時候最後兩個數不參與比較；
依次類推，每一趟比較次數-1；
https://www.cnblogs.com/shen-hua/p/5422676.html
2.快速排序
最差情況時間複雜度：O(n²),平均時間複雜度：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.在初始狀态下7是第一個位置，現在需要把7挪到中間的某個位置k，也即k位置是兩邊數的分界點。
6.那如何做到把小于和大于基準數7的值分别放置于兩邊呢，我們采用雙指針法，從數組的兩端分别進行比對。
7.先從最右位置往左開始找直到找到一個小于基準數的值，記錄下該值的位置（記作 i）。
8.再從最左位置往右找直到找到一個大于基準數的值，記錄下該值的位置（記作 j）。
9.如果位置i<j，則交換i和j兩個位置上的值，然後繼續從(j-1)的位置往前和(i+1)的位置往後重複上面比對基準數然後交換的步驟。
10.如果執行到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(n²)
空間複雜度：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個位置的數交換；然後在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最後一個數）比較完為止。
視訊講解：https://www.bilibili.com/video/BV17t411v7Ru?from=search&seid=540768407119432537
https://blog.csdn.net/wangkuifeng0118/article/details/7289594
6.堆排序
堆排序是利用堆這種資料結構而設計的一種排序算法，是一種選擇排序
堆結構：堆，又稱二叉堆，它的邏輯結構是一棵完全二叉樹，但實體結構是順序表（一維數組），可以按照層序周遊的順序将元素放入一維數組中。
堆分為大頂堆（大根堆）、小頂堆（小根堆）
大頂堆：根節點最大，左、右孩子節點都比目前節點要小
小頂堆：根節點最小，左、右孩子節點都比目前節點要大
堆排序的步驟：
a.将無需序列建構成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
b.将堆頂元素與末尾元素交換，将最大元素"沉"到數組末端;
c.重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與目前末尾元素，反複執行調整+交換步驟，直到整個序列有序。
關于資料結構堆的介紹：https://www.jianshu.com/p/6b526aa481b1
堆排序：https://www.cnblogs.com/chengxiao/p/6129630.html