排序是數據結構中比較重要的一種基礎算法，排序也會考驗對線性表和鏈表、樹的靈活運用，本篇文章我們重點講述下常見的3種基礎排序冒泡排序、插入排序、選擇排序，下一篇會重點講述實際工作中用的比較多的快速排序和歸併排序。
排序算法基礎
排序算法執行效率一般從以下幾方面進行衡量：
1）最好情況、最壞情況、平均情況下的時間複雜度
對於待排序數據有的接近有序，有的完全無序，會導致部分算法執行效率上有很大的差異，所以我們在選擇算法的時候除了要考慮算法的平均時間複雜度還要參考在實際業務場景下待排數據的實際有序性，和各類排序算法在實際業務場景下的待排數據的時間複雜度來選擇合適的算法。
2）比較次數和交換次數
在考慮排序算法的時候，因為基於比較的排序算法會涉及到元素大小比較和元素的交換，所以要把比較次數和交換次數也考慮進去。
3）排序算法的穩定性
僅用效率判斷一額排序算法好壞還是不夠的，還要看算法的穩定性，什麼是算法的穩定性？如果待排序中存在值相等的元素，經過排序後，相等元素之間原有的先後順序不變，這就說明算法是穩定的。
算法的穩定性在很多多次排序場景下是非常有效的，例如我們需要對一個用戶類先按照用戶的年齡排序，再按照用戶的姓名排序，如果使用的不是穩定算法那麼在按照年齡排完序後還需要對相等值再分別進行內部排序，這將非常麻煩，如果是穩定的排序算法，那麼處理起來將非常容易，只需要用穩定排序算法對數據進行兩次排序就行了，因為排序屬性相等的數據在排序前後相對順序不會變的。
冒泡排序
冒泡排序一般是我們在學習排序算法遇到的第一個排序算法，也是最簡單的一種排序算法，冒泡排序的核心思路是相鄰兩個元素之間的比較，不滿足大小關係則交換一次，冒泡排序至少讓一個元素移動到它應該在的位置，重複n次完成排序。對於冒泡排序比較形象的解釋就是水裡的氣泡，一堆氣泡，含空氣多的氣泡會從下面慢慢往上升。冒泡排序屬於原地排序，只需要一個額外的臨時空間所以空間複雜度為O(1)，在待排序數據是有序的情況下最好的時間複雜度為O(n)，平均時間複雜度為O(n^2)。
public void bubbleSort(int nums[]){
int temp;
for(int i=0;i
for(int j=0;j
來自簡書作者monkey01
聯繫作者longtestyan
