【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
在上面一篇博客當中，我們發現普通查找和排序查找的性能差別很大。作為一個100萬的數據，如果使用普通的查找方法，那麼每一個數據查找平均下來就要幾十萬次，那麼二分法的查找呢，20多次就可以搞定。這中間的差別是非常明顯的。既然排序有這麼好的效果，那麼這篇博客中，我們就對排序算做一個總結。
按照我個人的理解，排序可以分為兩種：一種是非遞歸排序，它主要按照非遞歸的方法對數據進行排序，也就是說主要數據的移位和循環來完成；另外一種就是遞歸方法，我們在排列當前數據的時候首先把子數據排列有序，然後才會排列當前的數據。這種不斷遞歸調用的方法就是遞歸排序。
非遞歸排序的方法很多，這裡主要介紹冒泡排序、插入排序、希爾排序；遞歸的方法也不少，這裡介紹的方法是快速排序、歸並排序和堆排序。排序的內容很多，本篇博客主要介紹非遞歸排序，遞歸排序的內容主要在下一節內容解決。
（1）冒泡排序
冒泡排序的內容並不復雜。假設有n個數據需要排序，那麼我們需要確定n個從大到小的數據，每一次都挑選第n大的數據是多少，並且放大相應的位置。直到所有的數據都排列整齊了，那麼我們的排序就結束了。
void bubble_sort(int array[], int length)
{
int inner = 0, outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(outer = length-1; outer >= 1; outer --){
for(inner = 0; inner < outer; inner ++){
if(array[inner] > array[inner + 1]){
median = array[inner];
array[inner] = array[inner + 1];
array[inner + 1] = median;
}
}
}
}
void bubble_sort(int array[], int length)
{
int inner = 0, outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(outer = length-1; outer >= 1; outer --){
for(inner = 0; inner < outer; inner ++){
if(array[inner] > array[inner + 1]){
median = array[inner];
array[inner] = array[inner + 1];
array[inner + 1] = median;
}
}
}
} 那麼這個程序有沒有什麼改進的地方呢？當然存在，如果發現在一次遍歷循環之中，如果沒有發生移位的現象，那麼是不是可以判斷這個排序可以結束了呢？朋友們可以好好思考一下這個問題？
void bubble_sort(int array[], int length)
{
int inner = 0, outer = 0;
int median = 0;
int flag = 1;
if(NULL == array || 0 == length)
return;
for(outer = length-1; outer >= 1 && flag; outer --){
flag = 0;
for(inner = 0; inner < outer; inner ++){
if(array[inner] > array[inner + 1]){
median = array[inner];
array[inner] = array[inner + 1];
array[inner + 1] = median;
if(flag == 0)
flag = 1;
}
}
}
}
void bubble_sort(int array[], int length)
{
int inner = 0, outer = 0;
int median = 0;
int flag = 1;
if(NULL == array || 0 == length)
return;
for(outer = length-1; outer >= 1 && flag; outer --){
flag = 0;
for(inner = 0; inner < outer; inner ++){
if(array[inner] > array[inner + 1]){
median = array[inner];
array[inner] = array[inner + 1];
array[inner + 1] = median;
if(flag == 0)
flag = 1;
}
}
}
}
（2） 插入排序
插入排序的意思就是說，我們把數據分成兩個部分，一部分是已經排好序的數據，一部分是當前還沒有完成排序的數據。那麼這麼說來的話，排序的過程是不是就是把沒有排序的數據逐個插入到已經排好序的隊列中的過程呢。大家可以自己先試一下，然後再看看我的代碼對不對？
void insert_sort(int array[], int length)
{
int inner = 0;
int outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(outer = 1; outer <length; outer ++){
for(inner = outer; inner >= 1; inner --){
if(array[inner] < array[inner -1]){
median = array[inner];
array[inner] = array[inner -1];
array[inner -1] = median;
}
}
}
}
void insert_sort(int array[], int length)
{
int inner = 0;
int outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(outer = 1; outer <length; outer ++){
for(inner = outer; inner >= 1; inner --){
if(array[inner] < array[inner -1]){
median = array[inner];
array[inner] = array[inner -1];
array[inner -1] = median;
}
}
}
} 那麼插入排序有沒有像冒泡排序那樣的改進方法呢？其實沒有。因為每一次插入排序的位置都是局部比較的結果，而冒泡排序每一次的內容都是全局最優的。這從數據比較的次數就可以看出來。
（3）希爾排序
希爾排序，我個人認為可以看成是冒泡排序的變種。它的基本思想是：首先按照一個序列遞減的方法逐漸進行排序。比如說有10個數據，我們按照序列5、3、1的順序進行排序。首先是5，那麼我們對1和6、2和7、3和8、4和9、5和10進行排列；第二輪是3，那麼對數據1、4、7、10排列，再對2、5、8進行排列，以及3、6、9排列；第三輪就和冒泡排序一樣了，以此對每個數據進行排列。它的優勢就是讓整個隊列基本有序，減少數據移動的次數，從而降低算法的計算復雜度。
void shell_sort(int array[], int length, int step)
{
int inner = 0;
int outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(; step >= 1; step -=2){
for(int index = 0; index < step; index ++){
if((length -1) < (index + step))
continue;
else{
outer = index + step;
while( (outer + step) <= (length - 1))
outer += step;
}
for(; outer >= (index + step); outer -= step){
for(inner = index; inner <= outer - step; inner += step){
if(array[inner] >= array[inner + step]){
median = array[inner];
array[inner] = array[inner + step];
array[inner + step] = median;
}
}
}
}
}
}
void shell_sort(int array[], int length, int step)
{
int inner = 0;
int outer = 0;
int median = 0;
if(NULL == array || 0 == length)
return;
for(; step >= 1; step -=2){
for(int index = 0; index < step; index ++){
if((length -1) < (index + step))
continue;
else{
outer = index + step;
while( (outer + step) <= (length - 1))
outer += step;
}
for(; outer >= (index + step); outer -= step){
for(inner = index; inner <= outer - step; inner += step){
if(array[inner] >= array[inner + step]){
median = array[inner];
array[inner] = array[inner + step];
array[inner + step] = median;
}
}
}
}
}
}
總結：
（1）上面的排序都是非遞歸程序，理解上不難，但是細節問題需要注意，特別是長度的問題
（2）代碼編寫的時候務必注意測試用例的設計
（3）如果可能的情況下，多使用已經驗證的代碼和函數
【預告： 下一篇博客介紹快速排序的內容】
