01

—

冒泡排序

在實(shí)現(xiàn)冒泡排序代碼之前我們先理解一下什么是冒泡排序，我們舉一個(gè)現(xiàn)實(shí)生活中的例子來(lái)幫助我們理解。

操場(chǎng)排隊(duì)我們都知道吧，現(xiàn)在有一支隊(duì)伍，有的人身高一樣有的不一樣，這個(gè)時(shí)候我們需要一個(gè)教官對(duì)這支隊(duì)伍進(jìn)行整理，使得隊(duì)伍里的人從低到高的排下去，教官想到了一種排序算法來(lái)對(duì)這支隊(duì)伍進(jìn)行身高排序。

如何理解冒泡排序

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

最后最高的人排在了隊(duì)伍的最后面，教官又從第2個(gè)人開(kāi)始往隊(duì)伍后面的方向，相鄰的2個(gè)人進(jìn)行身高對(duì)比，如果前面的人比后一個(gè)人高則兩人交換位置，最后最高的人排在了隊(duì)伍的最后面。

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

冒泡排序的實(shí)現(xiàn)

現(xiàn)在我們用C++實(shí)現(xiàn)冒泡排序算法，定義一個(gè)模板類，聲明冒泡排序算法函數(shù)。

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

冒泡排序?qū)崿F(xiàn)代碼如下：

//冒泡排序 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

—

交換排序

如何理解交換排序

前面教官使用了冒泡排序?qū)﹃?duì)伍進(jìn)行了整理，已經(jīng)按照身高從低到高的排序，但是從排序過(guò)程可以看出冒泡排序每個(gè)人互相進(jìn)行過(guò)對(duì)比，做了不必要的重復(fù)工作，類似于這種a和b對(duì)比，b和a又進(jìn)行對(duì)比。教官覺(jué)得這個(gè)排序算法效率不高，想要消除不必要的重復(fù)工作，于是又想到了一個(gè)排序算法。

教官先讓第1個(gè)個(gè)人走出隊(duì)列，從第2個(gè)人開(kāi)始第1個(gè)人依次和隊(duì)伍里剩下的人進(jìn)行對(duì)比，遇到比第1個(gè)人矮則互相交換位置，并且身高更矮的人繼續(xù)執(zhí)行剩余人的身高對(duì)比，最后對(duì)比完整個(gè)隊(duì)伍，找出了最矮的人，將最矮的人放在第1位。

接下來(lái)教官讓第2個(gè)人走出來(lái)，從第3個(gè)人開(kāi)始依次和隊(duì)伍里剩下的人進(jìn)行對(duì)比，遇到比第2個(gè)人更矮的人和第一個(gè)人的處理方式一樣，最后找到次矮的人，將次矮的人放在了第2的位置。

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

交換排序的實(shí)現(xiàn)

聲明交換排序函數(shù)

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

交換排序函數(shù)實(shí)現(xiàn)

//交換排序 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

—

插入排序

如何理解插入排序

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

教官把第1個(gè)人當(dāng)做只有1個(gè)人的隊(duì)伍并且是有序的，讓第2個(gè)人走出隊(duì)伍，和第1個(gè)人進(jìn)行對(duì)比身高，如果第2個(gè)人比第1個(gè)人矮那么第1個(gè)人就放到第2個(gè)人的位置，第2個(gè)人到第1個(gè)人的位置。進(jìn)行過(guò)這一輪對(duì)比我們就知道，第1個(gè)人和第2個(gè)人是有序排列的。

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

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

插入排序代碼實(shí)現(xiàn)

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

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）; //交換排序 };

這里我們定義一個(gè)模板類，聲明插入排序算法，插入排序算法實(shí)現(xiàn)代碼如下：

//從小到大排序 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］; //大的數(shù)據(jù)則往后挪 j--; } if（j 《 0）{ j = 0; } arr［j］ = data; i++; } }

04

—

結(jié)果驗(yàn)證

現(xiàn)在我們寫一個(gè)小程序驗(yàn)證一下算法的正確性。

int main（） { int arr［10］ = {8， 3， 21， 5， 6， 2， 3， 8， 1， 43}; Sort《int》 sort; std：：cout 《《 “插入排序結(jié)果” 《《 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 《《 “冒泡排序結(jié)果” 《《 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 《《 “交換排序結(jié)果” 《《 std：：endl; for（int e ： arr3）{ std：：cout 《《 e 《《 “ ”; } std：：cout 《《 std：：endl; return 0; }

編譯運(yùn)行輸出如下：

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

輸出結(jié)果完全正確，算法實(shí)現(xiàn)正確。

編輯：jq