在上面一篇博客當(dāng)中，我們發(fā)現(xiàn)普通查找和排序查找的性能差別很大。作為一個(gè)100萬(wàn)的數(shù)據(jù)，如果使用普通的查找方法，那么每一個(gè)數(shù)據(jù)查找平均下來(lái)就要幾十萬(wàn)次，那么二分法的查找呢，20多次就可以搞定。這中間的差別是非常明顯的。既然排序有這么好的效果，那么這篇博客中，我們就對(duì)排序算做一個(gè)總結(jié)。

按照我個(gè)人的理解，排序可以分為兩種：一種是非遞歸排序，它主要按照非遞歸的方法對(duì)數(shù)據(jù)進(jìn)行排序，也就是說(shuō)主要數(shù)據(jù)的移位和循環(huán)來(lái)完成；另外一種就是遞歸方法，我們?cè)谂帕挟?dāng)前數(shù)據(jù)的時(shí)候首先把子數(shù)據(jù)排列有序，然后才會(huì)排列當(dāng)前的數(shù)據(jù)。這種不斷遞歸調(diào)用的方法就是遞歸排序。

非遞歸排序的方法很多，這里主要介紹冒泡排序、插入排序、希爾排序；遞歸的方法也不少，這里介紹的方法是快速排序、歸并排序和堆排序。排序的內(nèi)容很多，本篇博客主要介紹非遞歸排序，遞歸排序的內(nèi)容主要在下一節(jié)內(nèi)容解決。

（1）冒泡排序

冒泡排序的內(nèi)容并不復(fù)雜。假設(shè)有n個(gè)數(shù)據(jù)需要排序，那么我們需要確定n個(gè)從大到小的數(shù)據(jù)，每一次都挑選第n大的數(shù)據(jù)是多少，并且放大相應(yīng)的位置。直到所有的數(shù)據(jù)都排列整齊了，那么我們的排序就結(jié)束了。

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;
            }
        }
    }
}

那么這個(gè)程序有沒(méi)有什么改進(jìn)的地方呢？當(dāng)然存在，如果發(fā)現(xiàn)在一次遍歷循環(huán)之中，如果沒(méi)有發(fā)生移位的現(xiàn)象，那么是不是可以判斷這個(gè)排序可以結(jié)束了呢？朋友們可以好好思考一下這個(gè)問(wèn)題？

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） 插入排序

插入排序的意思就是說(shuō)，我們把數(shù)據(jù)分成兩個(gè)部分，一部分是已經(jīng)排好序的數(shù)據(jù)，一部分是當(dāng)前還沒(méi)有完成排序的數(shù)據(jù)。那么這么說(shuō)來(lái)的話，排序的過(guò)程是不是就是把沒(méi)有排序的數(shù)據(jù)逐個(gè)插入到已經(jīng)排好序的隊(duì)列中的過(guò)程呢。大家可以自己先試一下，然后再看看我的代碼對(duì)不對(duì)？

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 = 1; inner --){
            if(array[inner] < array[inner -1]){
                median = array[inner];
                array[inner] = array[inner -1];
                array[inner -1] = median;
            }else{
                break;
            }
        }
    }
}

那么插入排序有沒(méi)有像冒泡排序那樣的改進(jìn)方法呢？其實(shí)沒(méi)有。因?yàn)槊恳淮尾迦肱判虻奈恢枚际蔷植勘容^的結(jié)果，而冒泡排序每一次的內(nèi)容都是全局最優(yōu)的。這從數(shù)據(jù)比較的次數(shù)就可以看出來(lái)。

（3）希爾排序

希爾排序，我個(gè)人認(rèn)為可以看成是冒泡排序的變種。它的基本思想是：首先按照一個(gè)序列遞減的方法逐漸進(jìn)行排序。比如說(shuō)有10個(gè)數(shù)據(jù)，我們按照序列5、3、1的順序進(jìn)行排序。首先是5，那么我們對(duì)1和6、2和7、3和8、4和9、5和10進(jìn)行排列；第二輪是3，那么對(duì)數(shù)據(jù)1、4、7、10排列，再對(duì)2、5、8進(jìn)行排列，以及3、6、9排列；第三輪就和冒泡排序一樣了，以此對(duì)每個(gè)數(shù)據(jù)進(jìn)行排列。它的優(yōu)勢(shì)就是讓整個(gè)隊(duì)列基本有序，減少數(shù)據(jù)移動(dòng)的次數(shù)，從而降低算法的計(jì)算復(fù)雜度。

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;
                    }
                }
            }
        }
    }
}

總結(jié)：

（1）上面的排序都是非遞歸程序，理解上不難，但是細(xì)節(jié)問(wèn)題需要注意，特別是長(zhǎng)度的問(wèn)題

（2）代碼編寫(xiě)的時(shí)候務(wù)必注意測(cè)試用例的設(shè)計(jì)

（3）如果可能的情況下，多使用已經(jīng)驗(yàn)證的代碼和函數(shù)