01

—

冒泡排序

在實現冒泡排序代碼之前我們先理解一下什么是冒泡排序，我們舉一個現實生活中的例子來幫助我們理解。

操場排隊我們都知道吧，現在有一支隊伍，有的人身高一樣有的不一樣，這個時候我們需要一個教官對這支隊伍進行整理，使得隊伍里的人從低到高的排下去，教官想到了一種排序算法來對這支隊伍進行身高排序。

如何理解冒泡排序

教官立馬想到了一個排序算法，從第1個人開始往隊伍后面的方向相鄰的兩個人進行身高對比，如果前面的人比后一個人高則兩人交換位置。

最后最高的人排在了隊伍的最后面，教官又從第2個人開始往隊伍后面的方向，相鄰的2個人進行身高對比，如果前面的人比后一個人高則兩人交換位置，最后最高的人排在了隊伍的最后面。

由于前面的排序過程已經選出了隊伍里身高最高的人，所以后面的排序過程不對已經排好序的進行對比，最后教官重復上面的步驟最終將隊伍按身高從低到高的排好序。教官所用的排序算法正是冒泡排序算法，時間復雜度是O（n^2）。

冒泡排序的實現

現在我們用C++實現冒泡排序算法，定義一個模板類，聲明冒泡排序算法函數。

template《typename T》 class Sort{ public： void bubble_sort（T *arr， int size）; //冒泡排序 };

冒泡排序實現代碼如下：

//冒泡排序 template《typename T》 void Sort《T》：：bubble_sort（T *arr， int size） { if（arr == nullptr || size 《= 0）{ return; } T temp; for（int i = 0; i 《 size; i++）{ for（int j = 0; j 《 size - i; j++）{ if（arr［j］ 》 arr［j + 1］）{ temp = arr［j］; arr［j］ = arr［j + 1］; arr［j + 1］ = temp; } } } }

02

—

交換排序

如何理解交換排序

前面教官使用了冒泡排序對隊伍進行了整理，已經按照身高從低到高的排序，但是從排序過程可以看出冒泡排序每個人互相進行過對比，做了不必要的重復工作，類似于這種a和b對比，b和a又進行對比。教官覺得這個排序算法效率不高，想要消除不必要的重復工作，于是又想到了一個排序算法。

教官先讓第1個個人走出隊列，從第2個人開始第1個人依次和隊伍里剩下的人進行對比，遇到比第1個人矮則互相交換位置，并且身高更矮的人繼續執行剩余人的身高對比，最后對比完整個隊伍，找出了最矮的人，將最矮的人放在第1位。

接下來教官讓第2個人走出來，從第3個人開始依次和隊伍里剩下的人進行對比，遇到比第2個人更矮的人和第一個人的處理方式一樣，最后找到次矮的人，將次矮的人放在了第2的位置。

最后教官重復上面的步驟，依次讓第3、4、5.。。。。.n-1個人走出隊列依次和隊伍里剩下的人進行身高對比，放在合適的位置。這種排序算法稱為交換排序，第1個人進行了（n-1）次對比，第2個人進行了（n-2）次對比。。。。。。第n-1個人進行了一次對比，所以時間復雜度是O（n^2）。

交換排序的實現

聲明交換排序函數

template《typename T》 class Sort{ public： void bubble_sort（T *arr， int size）; //冒泡排序 void swap_sort（T *arr， int size）; //交換排序 };

交換排序函數實現

//交換排序 template《typename T》 void Sort《T》：：swap_sort（T *arr， int size） { if（arr == nullptr || size 《= 0）{ return; } T temp; for（int i = 0; i 《 size - 1; i++）{ for（int j = i + 1; j 《 size; j++）{ if（arr［i］ 》 arr［j］）{ temp = arr［i］; arr［i］ = arr［j］; arr［j］ = temp; } } } }

03

—

插入排序

如何理解插入排序

教官還是覺得算法不理想，效率不夠高，無論是冒泡排序和交換排序在隊伍里原本就是有序的情況下都要進行對比，那么有沒有一種排序算法在隊伍原本就是有序的情況下更快呢？教官最后想了很久終于想到了一種效率更高的排序算法。

教官把第1個人當做只有1個人的隊伍并且是有序的，讓第2個人走出隊伍，和第1個人進行對比身高，如果第2個人比第1個人矮那么第1個人就放到第2個人的位置，第2個人到第1個人的位置。進行過這一輪對比我們就知道，第1個人和第2個人是有序排列的。

同樣的，教官又叫第3個人走出隊列，從第2個人開始依次往前進行身高對比，比第3個人身高更高的人就往后挪一個位置，直到遇到身高比第3個人矮的人則停止對比，將第3個人排在這個人的身后。

最后教官依次讓第4、5、6.。。。。的人走出隊伍和上面的步驟一樣依次和前面的進行身高對比，找到合適的位置就插入，直到所有人從低到高的排序。時間復雜度是O（N^2），但是如果隊伍原本就是從低到高的排列，那么時間復雜度是O（N）。

插入排序代碼實現

教官所用的身高排序算法正是插入排序算法，現在我們用C++代碼實現插入排序算法，插入排序函數聲明如下。

template《typename T》 class Sort{ public： void insert_sort（T *arr， int size）; //插入排序 void bubble_sort（T *arr， int size）; //冒泡排序 void swap_sort（T *arr， int size）; //交換排序 };

這里我們定義一個模板類，聲明插入排序算法，插入排序算法實現代碼如下：

//從小到大排序 template《typename T》 void Sort《T》：：insert_sort（T *arr， int size）{ if（arr == nullptr || size 《= 0）{ return; } int i = 1; int j = 0; while（i 《 size）{ T data = arr［i］; j = i - 1; while（j 》= 0 && arr［j］ 》 data）{ arr［j + 1］ = arr［j］; //大的數據則往后挪 j--; } if（j 《 0）{ j = 0; } arr［j］ = data; i++; } }

04

—

結果驗證

現在我們寫一個小程序驗證一下算法的正確性。

int main（） { int arr［10］ = {8， 3， 21， 5， 6， 2， 3， 8， 1， 43}; Sort《int》 sort; std：：cout 《《 “插入排序結果” 《《 std：：endl; sort.insert_sort（arr， 10）; //插入排序 for（int e ： arr）{ std：：cout 《《 e 《《 “ ”; } std：：cout 《《 std：：endl; int arr2［10］ = {8， 32， 56， 5， 7， 8， 98， 78， 6， 7}; sort.bubble_sort（arr2， 10）; //冒泡排序 std：：cout 《《 “冒泡排序結果” 《《 std：：endl; for（int e ： arr2）{ std：：cout 《《 e 《《 “ ”; } std：：cout 《《 std：：endl; int arr3［10］ = {8， 4， 2， 3， 5， 6， 8， 3， 10， 50}; sort.swap_sort（arr3， 10）; //交換排序 std：：cout 《《 “交換排序結果” 《《 std：：endl; for（int e ： arr3）{ std：：cout 《《 e 《《 “ ”; } std：：cout 《《 std：：endl; return 0; }

編譯運行輸出如下：

插入排序結果 1 3 6 8 21 21 21 21 43 43 冒泡排序結果 0 5 6 7 7 8 8 32 56 78 交換排序結果 2 3 3 4 5 6 8 8 10 50

輸出結果完全正確，算法實現正確。

編輯：jq