概述
排序分為內(nèi)部排序和外部排序，內(nèi)部排序是待排序的元素全部放在內(nèi)存，并在內(nèi)存中調(diào)整它們的順序。外部排序是部分元素放到內(nèi)存中，在內(nèi)外存間調(diào)整元素的順序。我們通常說的八大排序直接插入排序、希爾排序、簡單選擇排序、冒泡排序、快速排序、堆排序、歸并排序、基數(shù)排序都是內(nèi)部排序，下面來具體介紹這八種排序的如何用JAVA實現(xiàn)，以及它們所需的時間復(fù)雜度和空間復(fù)雜度。
直接插入排序
基本思想：將一個待排序的元素插入到已經(jīng)排好序的序列中，如果待排序的元素與有序序列的中的某個元素相等，則把待排序元素插到該元素后面。
算法實現(xiàn)：
時間復(fù)雜度：
直接插入排序是穩(wěn)定的排序，其時間復(fù)雜度是O(n^2)。
說明：穩(wěn)定的排序是指相等的元素經(jīng)過排序后，其相對位置沒有發(fā)生改變。
說明：如果待排序的元素是正序（從小到大排列），每插入一個元素只需比較一次，這樣時間復(fù)雜度就是O(n)。反之，如果待排序的元素是逆序（從大到小排列），當(dāng)插入第i個元素時，需要比較i次，這樣時間復(fù)雜度是O(n^2)。
希爾排序
基本思想：
希爾排序?qū)嵸|(zhì)上是一種分組插入排序，其先將整個待排元素序列分割成若干個子序列（由距離為d的元素組成）分別進(jìn)行直接插入排序，然后依次減少距離d再進(jìn)行排序，當(dāng)距離為1時，再對全體元素進(jìn)行一次直接插入排序。
算法實現(xiàn)：
時間復(fù)雜度：
希爾排序中相同的元素可能在各自組的插入排序中移動，最后其穩(wěn)定性會被打亂，所以希爾排序是不穩(wěn)定的，其時間復(fù)雜度是O(nlogn)。
簡單選擇排序
基本思想：
在n個待排序的元素中找取最小的元素與第一個元素交換位置，然后在n-1個元素中找取最小的元素與第二元素交換位置，直到n=1為止。
算法實現(xiàn):
時間復(fù)雜度:
簡單選擇排序是不穩(wěn)定的排序，其時間復(fù)雜度是O(n^2)。
不穩(wěn)定說明：
假設(shè)待排元素序列是：6，4，6，7，2，9，第一次排序后，序列變成了2，4，6，7，6，9，我們可以發(fā)現(xiàn)，經(jīng)過一次排序后，位置一的6調(diào)整到位置三的6的后面，所以簡單選擇排序是不穩(wěn)定的排序。
冒泡排序
基本思想：
從待排序元素的倒數(shù)第一位開始向前遍歷，如果當(dāng)前元素比前面元素小，則交換位置。這樣一次遍歷下來，最小的元素冒泡到第一個位置了，然后，從倒數(shù)第二位、第三位...開始向前遍歷，重復(fù)上面的過程，直到元素有序。
算法實現(xiàn):
時間復(fù)雜度:
冒泡排序是穩(wěn)定的排序，時間復(fù)雜度是O(n^2)
快速排序
基本思想:
選擇一個基準(zhǔn)元素（通常選擇第一個元素或者最后一個元素），通過一次排序?qū)⒋判蛄蟹譃閮刹糠郑徊糠侄急然鶞?zhǔn)元素小，另一部分都比基準(zhǔn)元素大，然后再按此方法對這兩組數(shù)據(jù)分別進(jìn)行快速排序，直到待排序列有序。
算法實現(xiàn):
時間復(fù)雜度:
快速排序是不穩(wěn)定排序，時間復(fù)雜度是O(nlogn)
堆排序
基本思想:
堆的概念：
n個元素的序列{k1，k2，…,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時，稱之為堆。
情形1：ki <= k2i 且ki <= k2i+1 （最小堆）
情形2：ki >= k2i 且ki >= k2i+1 （最大堆）
其中i=1,2,…,n/2向下取整;
堆排序：
把待排序的序列看作是一棵順序存儲的二叉樹，調(diào)整它們的存儲順序，使之成為一個最大堆，這時堆的根節(jié)點數(shù)最大。然后，將根節(jié)點與堆的最后一個節(jié)點交換，并對前面n-1個數(shù)重新調(diào)整使之成為堆，依此類推，最后得到有n個節(jié)點的有序序列。
從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆結(jié)果。
說明：若想得到升序序列，則建立最大堆，若想得到降序序列，則建立最小堆。
算法實現(xiàn):
時間復(fù)雜度：
堆排序是不穩(wěn)定的排序，其時間復(fù)雜度是O(nlogn)。
歸并排序
基本思想：
是把待排序序列分為若干個子序列，每個子序列是有序的，然后再把有序子序列合并為整體有序序列。
算法實現(xiàn)：
時間復(fù)雜度:
歸并排序是穩(wěn)定的排序，其時間復(fù)雜度為O(nlogn)。
字基數(shù)排序
基本思想：
將所有待排序列(正整數(shù))統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后 ，從最低位開始，依次進(jìn)行一次排序。這樣，從最低位一直到最高位排序完成以后， 數(shù)列就變成一個有序序列。
算法實現(xiàn)：
時間復(fù)雜度:
基數(shù)排序是穩(wěn)定的排序，其時間復(fù)雜度為O(d(n+r))，d為位數(shù)，r為基數(shù)范圍。
