最近在慕課網(wǎng)上學(xué)習(xí)了O（n2）時間復(fù)雜度的相關(guān)算法蹋绽，總算是對這些算法的優(yōu)缺點有了詳細(xì)的特點。其實對于任何的算法，沒有優(yōu)點和缺點携茂，而是有相應(yīng)的特點。所以我們應(yīng)該結(jié)合不同的排序環(huán)境來選擇不同的排序算法诅岩，從而達(dá)到在實現(xiàn)時間和執(zhí)行效率上的平衡讳苦。這是因為，越是簡單的排序算法吩谦，實現(xiàn)起來肯定是越容易鸳谜，而且出現(xiàn)BUG的概率也不會太大。相反式廷，復(fù)雜算法可能效率更高咐扭，但是出現(xiàn)問題的可能性也會更大。下面滑废，我就結(jié)合O（n2）時間復(fù)雜度的四個經(jīng)典排序算法蝗肪，為您詳細(xì)講解這四個算法的特點。
選擇排序
定義：選擇排序（Selection sort）是一種簡單直觀的排序算法蠕趁。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最醒ι痢（或最大）的一個元素，存放在序列的起始位置俺陋，直到全部待排序的數(shù)據(jù)元素排完豁延。
圖示說明：
源碼實現(xiàn)：
template
void selectionSort(Tarr[],int n)
{
??????for(int i = 0; i < n; i++)
??????{
????????????int minIndex = i;
????????????for(int j = i; j < n; j++)
????????????{
??????????????????if(arr[minIndex] >= arr[j])
??????????????????{
????????????????????????minIndex = j;
??????????????????}
????????????}
????????????if(minIndex != i)
????????????{
??????????????????swap(&arr[minIndex], &arr[i]);
????????????}
??????}
}
分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進(jìn)行兩次循環(huán)腊状，而且最關(guān)鍵的是內(nèi)層循環(huán)在每一次執(zhí)行時都是全部執(zhí)行完的术浪。那我們有沒有辦法讓內(nèi)層循環(huán)不用每次都執(zhí)行完呢？方法肯定是有的寿酌，這就是冒泡排序。
冒泡排序
定義：冒泡排序（Bubble Sort）硕蛹，是一種計算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法醇疼。它重復(fù)地走訪過要排序的元素列，一次比較兩個相鄰的元素法焰，如果他們的順序（如從大到小秧荆、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換埃仪，也就是說該元素已經(jīng)排序完成乙濒。
圖示說明：
源碼實現(xiàn)：
template
void bubbleSort(Tarr[],intn){
??????for(int i = 0; i < n; i++)
??????{
????????????intflag= 0;
????????????for(intj = 0; j < n-i-1; j++)
????????????{
??????????????????if(arr[j] > arr[j + 1])
??????????????????{
????????????????????????swap(arr[j], arr[j+1]);
????????????????????????flag= 1;
??????????????????}
????????????}
????????????if(!flag)
????????????{
??????????????????break;
????????????}
??????}
??????return;
}
分析：從圖示和源碼可以看出來，從執(zhí)行次數(shù)上來說，冒泡排序是比選擇排序的循環(huán)次數(shù)更少的颁股。那是不是就可以說么库，如果待排序的數(shù)組中元素比較合適，冒泡排序在時間復(fù)雜度上是不是會比選擇排序更好呢甘有？真的是這樣的嗎诉儒？
其實不是的，經(jīng)過多次測試驗證亏掀，冒泡排序基本上是比選擇排序的時間復(fù)雜度要差的忱反，這是為什么呢？從源碼中我們可以很明顯的看出來滤愕，雖然冒泡排序是比選擇排序執(zhí)行次數(shù)少了温算，但是交換的次數(shù)明顯增多了，而如果你對計算機(jī)程序指令的實現(xiàn)原理只要有一個基本的認(rèn)識间影，就應(yīng)該知道交換動作比賦值動作是需要更多指令操作的注竿。所以說，最終冒泡排序大部分情況下宇智，比選擇排序的時間復(fù)雜度都要高蔓搞。
既然交換動作這么消耗資源，那有沒有一種方法随橘，即能夠減少內(nèi)層循環(huán)的執(zhí)行次數(shù)喂分，又可以減少甚至是無需交換操作呢？這就要請出插入排序了机蔗。
插入排序
定義：插入排序（Insertion?Sort）的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中蒲祈，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)萝嘁，即每步將一個待排序的記錄梆掸，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止牙言。
圖示說明：
源碼實現(xiàn)：
template
void insertionSortX(Tarr[],int n)
{
??????for(int i = 1; i < n; i++)
??????{
????????????Te =arr[i];
????????????int j;
????????????for(j = i; j > 0 && (arr[j - 1] > e); j--)
????????????{
??????????????????arr[j] =arr[j -1];
????????????}
????????????arr[j] = e;
??????}
}
分析：從圖示和源碼可以看出來酸钦，插入排序（優(yōu)化后的）是沒有交換操作的，而且對于內(nèi)層循環(huán)來說咱枉，如果待排序的元素是比較大的值卑硫，那內(nèi)層循環(huán)執(zhí)行的次數(shù)會非常的少。因此蚕断，如果原始數(shù)據(jù)基本上是有序的欢伏，那使用插入排序的效率會非常的高。在O（n2）級別的排序算法還可以再優(yōu)化嗎亿乳？如果可以從哪里優(yōu)化呢硝拧？下面我們來介紹希爾排序，正是這個排序算法的提出，使得排序算法打破了O（n2）時間復(fù)雜度的禁錮障陶。
希爾排序
定義：希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）滋恬，是直接插入排序算法的一種更高效的改進(jìn)版本。該算法的基本思想是：把記錄按下標(biāo)的一定增量分組咸这，對每組使用直接插入排序算法排序夷恍；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多媳维，當(dāng)增量減至1時酿雪，整個文件恰被分成一組，排序算法便終止侄刽。
對于希爾排序來說指黎，最關(guān)鍵的就是增量該如何選取。這個增量該怎么確定州丹，這還真是個數(shù)學(xué)難題醋安，至今沒有解答。但是通過大量的實驗墓毒，還是有個經(jīng)驗值的吓揪。我們的例子給出的增量選取公式是：h = 3 *?h + 1，下面請看圖示說明所计。
圖示說明：
源碼實現(xiàn)：
template
void shellSort(Tarr[],int n){
??????int h = 1;
??????while(h < n / 3)
??????{
????????????h = 3 * h + 1;
??????}
??????while(h >= 1){
????????????for(int i = h; i < n; i++)
????????????{
??????????????????Te = arr[i];
??????????????????int j;
??????????????????for(j = i; j >= h && (e <= arr[j - h]); j -= h){
????????????????????????arr[j] = arr[j -h];
??????????????????}
??????????????????arr[j] = e;
????????????}
????????????h = h / 3;
??????}
??????return;
}
分析：從插入排序中我們知道柠辞，插入排在待排序數(shù)組基本有序時，插入排序的算法效率會非常高主胧，所以我們可以這樣認(rèn)為叭首，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時踪栋，在對全體進(jìn)行一次直接插入排序焙格。
而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當(dāng)h值大的時候夷都，數(shù)據(jù)項每一趟排序需要移動元素的個數(shù)很少眷唉，但數(shù)據(jù)項移動的距離很長。這是非常有效率的囤官。而當(dāng)h減小時厢破，每一趟排序需要移動的元素的個數(shù)增多，但是此時數(shù)據(jù)項已經(jīng)接近于它們排序后最終的位置治拿，這對于插入排序可以更有效率。正是這兩種情況的結(jié)合才使希爾排序效率那么高笆焰。
對于增量的選取劫谅，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2捏检，簡單地把每一趟排序分成了兩半荞驴。但是，這被證明并不是最好的數(shù)列贯城。盡管對于大多數(shù)的數(shù)據(jù)來說這個方法還是比插入排序效果好熊楼，但是這種方法有時會使運(yùn)行時間降到O(N2)，這并不比插入排序的效率更高能犯。間隔序列中的數(shù)字互質(zhì)通常被認(rèn)為很重要：也就是說鲫骗，除了1之外它們沒有公約數(shù)。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果踩晶。希爾最初以N/2為間隔的低效性就是歸咎于它沒有遵守這個準(zhǔn)則执泰。
總結(jié)：上面就是四種經(jīng)典O（n2）級別排序算法的相關(guān)說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的渡蜻，因為使用場景基本沒有术吝。而對于插入排序和希爾排序來說，在待排序數(shù)據(jù)基本有序的情況下茸苇，使用場景還是有的排苍，比如一些日志文件中存儲的日志，可能大部分的日志記錄都是基于時間排序学密，只是在某些極端情況下導(dǎo)致一些日志晚存儲了導(dǎo)致時間不一致淘衙。
我是徐建航，這是我寫的第31篇文章则果，歡迎你加入007社群幔翰，七天寫一篇，一起寫七年西壮，七年之后一起去南極遗增。
