經(jīng)典排序算法總結(jié)

排序算法是離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)學(xué)科最基本的算法，雖然知道這些排序算法的名字，但是一直沒有研究過它們的實(shí)現(xiàn)原理?，F(xiàn)在把它們收集起來，并一一親自實(shí)現(xiàn)，來加深對排序算法的理解。

1，冒泡排序：最簡單的排序算法，從第一個(gè)元素開始比較相鄰元素大小，如果前邊元素大于后邊元素則交換位置，否則將下標(biāo)移到下一個(gè)元素，一直到最后一個(gè)元素為止；然后進(jìn)行其他輪次的比較，直到?jīng)]有元素交換結(jié)束。http://blog.csdn.net/aitazhixin/article/details/62040803

另外一種改進(jìn)的冒泡排序算法為，將上一輪次比較中，最后一次元素交換的位置標(biāo)記，作為下面一輪次比較的終點(diǎn)。http://blog.csdn.net/aitazhixin/article/details/62043245

2，插入排序：假設(shè)元素m之前的所有元素已排好順序，則在排好序的子序中查找m的位置，然后插入m，得到一個(gè)增量的子序，循環(huán)下標(biāo)到最后一個(gè)元素為止。http://blog.csdn.net/aitazhixin/article/details/62042293

3，選擇排序：從未排序的序列中選擇最小的元素，與第一個(gè)元素交換位置，然后對剩余的未排序子序進(jìn)行相同的操作。

http://blog.csdn.net/aitazhixin/article/details/62043950

4，快速排序：快速排序采用分治遞歸的思想，首先選取一個(gè)參考元素（比如第一個(gè)元素），然后將剩余的元素分成兩部分：一部分所有元素都小于參考元素，一部分所有元素都大于參考元素，然后將參考元素插入到分界點(diǎn)；對于分開的兩部分，遞歸采用同樣的方法獲取分類，最終將獲取到完整排序的數(shù)列。http://blog.csdn.net/aitazhixin/article/details/62045826

5，歸并排序：基本原理是將兩個(gè)已排序的數(shù)列歸并成一個(gè)排序的數(shù)列，我采用了三元體的方式，在合并時(shí)做到整體插入。http://blog.csdn.net/aitazhixin/article/details/62053785

6，二叉排序樹：基本思想是將序列中的數(shù)讀入一個(gè)二叉樹，在讀入時(shí)遵循一定的規(guī)則：比如，如果二叉樹的一個(gè)節(jié)點(diǎn)有左子節(jié)點(diǎn)，那么左子節(jié)點(diǎn)一定比父節(jié)點(diǎn)的值小；如果一個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn)，那么右子節(jié)點(diǎn)一定比父節(jié)點(diǎn)的值大。在二叉排序樹制造完成后，通過采用中序遍歷的方法讀取二叉樹節(jié)點(diǎn)的值到序列中，就可以得到一個(gè)升序序列。http://blog.csdn.net/aitazhixin/article/details/62229996

7，堆排序：基本原理是每次構(gòu)造一個(gè)小頂堆，那么堆的根節(jié)點(diǎn)就是序列的最小值，然后利用剩余的元素再構(gòu)造一個(gè)小頂堆，獲得第二個(gè)較小的元素，遞歸運(yùn)行直到剩余1個(gè)元素返回，最終將得到升序排列的序列。http://blog.csdn.net/aitazhixin/article/details/62416238