插入排序

插入排序非常類似于整撲克牌。在開始摸牌時(shí)厦凤，左手是空的鼻吮，牌面朝下放在桌上。接著较鼓，一次從桌上摸起一張牌椎木，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置博烂，要將它與手中已有的牌從右到左地進(jìn)行比較香椎。無論什么時(shí)候，左手中的牌都是排好序的禽篱。
??如果輸入數(shù)組已經(jīng)是排好序的話畜伐，插入排序出現(xiàn)最佳情況，其運(yùn)行時(shí)間是輸入規(guī)模的一個線性函數(shù)躺率。如果輸入數(shù)組是逆序排列的烤礁，將出現(xiàn)最壞情況。平均情況與最壞情況一樣肥照，其時(shí)間代價(jià)是Θ(n2)脚仔。??也許你沒有意識到，但其實(shí)你的思考過程是這樣的：現(xiàn)在抓到一張7舆绎，把它和手里的牌從右到左依次比較鲤脏，7比10小，應(yīng)該再往左插吕朵，7比5大猎醇，好，就插這里努溃。為什么比較了10和5就可以確定7的位置硫嘶？為什么不用再比較左邊的4和2呢？因?yàn)檫@里有一個重要的前提：手里的牌已經(jīng)是排好序的∥嗨埃現(xiàn)在我插了7之后沦疾，手里的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入第队。編程對一個數(shù)組進(jìn)行插入排序也是同樣道理哮塞，但和插入撲克牌有一點(diǎn)不同，不可能在兩個相鄰的存儲單元之間再插入一個單元凳谦，因此要將插入點(diǎn)之后的數(shù)據(jù)依次往后移動一個單元忆畅。
插入排序類似于整理撲克牌，從無序列中選擇一個值插入到有序列中

冒泡排序

*** 冒泡排序法的基本思想：（以升序?yàn)槔┖衝個元素的數(shù)組原則上要進(jìn)行n-1次排序尸执。對于每一躺的排序家凯，從第一個數(shù)開始缓醋，依次比較前一個數(shù)與后一個數(shù)的大小。如果前一個數(shù)比后一個數(shù)大绊诲，則進(jìn)行交換送粱。這樣一輪過后，最大的數(shù)將會出現(xiàn)稱為最末位的數(shù)組元素驯镊。第二輪則去掉最后一個數(shù)葫督，對前n-1個數(shù)再按照上面的步驟找出最大數(shù)竭鞍，該數(shù)將稱為倒數(shù)第二的數(shù)組元素......n-1輪過后板惑，就完成了排序。***

快速排序

*** 快速排序是冒泡排序的一種改進(jìn)偎快，快速排序以一個基準(zhǔn)值冯乘，將無序列分成兩部分（左邊小于基準(zhǔn)值，右邊大于基準(zhǔn)值）晒夹，然后遞歸裆馒。***
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用丐怯，再加上快速排序思想----分治法也確實(shí)實(shí)用喷好，因此很多軟件公司的筆試面試，包括像騰訊读跷，微軟等知名IT公司都喜歡考這個梗搅，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影效览。

選擇排序

選擇排序：比如在一個長度為N的無序數(shù)組中无切，在第一趟遍歷N個數(shù)據(jù)，找出其中最小的數(shù)值與第一個元素交換丐枉，第二趟遍歷剩下的N-1個數(shù)據(jù)哆键，找出其中最小的數(shù)值與第二個元素交換......第N-1趟遍歷剩下的2個數(shù)據(jù)，找出其中最小的數(shù)值與第N-1個元素交換瘦锹，至此選擇排序完成籍嘹。
選擇排序是根據(jù)找到無序數(shù)列中的最大或最小值插入到有序序列尾部來排序

地精排序

雖然沒寫過這個排序,但是個人感覺這個排序很有意思也很快速
號稱最簡單的排序算法,只有一層循環(huán),默認(rèn)情況下前進(jìn)冒泡,一旦遇到冒泡的情況發(fā)生就往回冒,直到把這個數(shù)字放好為止

直接看它排序的過程,待排數(shù)組[6 2 4 1 5 9]

先設(shè)計(jì)一個標(biāo)識i=0然后從頭開始判斷,什么時(shí)候(i < 6)不成立,什么時(shí)候排序結(jié)束,

所以,如何控制i的值是這個算法的關(guān)鍵

例如待排數(shù)組:

[6 2 4 1 5 9]

[0 1 2 3 4 5]

看一下具體的排序過程

[ i = 0 ]時(shí)啥也不干,先讓i自增1,達(dá)到值為1才開始真正的比較

交換前[6 2 4 1 5 9][ i = 0]

交換后[6 2 4 1 5 9][ i = 1]



[ i = 1 ]比較6和2,發(fā)生交換,只要發(fā)生交換i就減1

  交換前[6 2 4 1 5 9][ i = 1]

交換后[2 6 4 1 5 9][ i = 0]



[ i = 0 ]又成0了,啥也不干,自增變成1再說

交換前[2 6 4 1 5 9][ i = 0]

交換后[2 6 4 1 5 9][ i = 1]



[ i = 1 ]再比較2和6,不交換,只要不要換就自增1

交換前[2 6 4 1 5 9][ i = 1]

交換后[2 6 4 1 5 9][ i = 2]



[ i = 2 ]比較6和4,發(fā)生交換,只要交換就減1

交換前[2 6 4 1 5 9][ i = 2]

交換后[2 4 6 1 5 9][ i = 1]



[ i = 1 ]比較2和4,不交換,只要不交換就自增1

交換前[2 4 6 1 5 9][ i = 1]

交換后[2 4 6 1 5 9][ i = 2]



[ i = 2 ]比較4和6,不交換,只要不交換就自增1

交換前[2 4 6 1 5 9][ i = 2]

交換后[2 4 6 1 5 9][ i = 3]



[ i = 3 ]比較6和1,交換,只要交換就減1

交換前[2 4 6 1 5 9][ i = 3]

交換后[2 4 1 6 5 9][ i = 2]



[ i = 2 ]比較4和1,交換,只要交換就減1

交換前[2 4 1 6 5 9][ i = 2]

交換后[2 1 4 6 5 9][ i = 1]



[ i = 1 ]比較2和1,交換,只要交換就減1

交換前[2 1 4 6 5 9][ i = 1]

交換后[1 2 4 6 5 9][ i = 0]



[ i = 0 ]時(shí)啥也不干,先讓i自增1,達(dá)到值為1才開始真正的比較

交換前[1 2 4 6 5 9][ i = 0]

交換后[1 2 4 6 5 9][ i = 1]

[ i = 1]比較1和2,不交換,只要不交換就自增1

[ i = 2]比較2和4,不交換,只要不交換就自增1

[ i = 3]比較4和6,不交換,只要不交換就自增1

[ i = 4]比較6和5,交換,只要交換就減1

交換前[1 2 4 6 5 9][ i = 4]

交換后[1 2 4 5 6 9][ i = 3]

[ i = 3]比較4和5,不交換,只要不交換就自增1

[ i = 4]比較5和6,不交換,只要不交換就自增1

[ i = 5]比較6和9,不交換,只要不交換就自增1

[ i = 6]表達(dá)式(i < n)不成立,排序結(jié)束,

順序輸出結(jié)果即可:[ 1 2 4 5 6 9]
***************************************************************
    static void gnome_sort(int[] unsorted)
    {
        int i = 0;
        while (i < unsorted.Length)
        {
            if (i == 0 || unsorted[i - 1] <= unsorted[i])
            {
                i++;
            }
            else
            {
                int tmp = unsorted[i];
                unsorted[i] = unsorted[i - 1];
                unsorted[i - 1] = tmp;
                i--;
            }
        }
    }

兩個經(jīng)典文章

1 [排序算法]:http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
2[排序動畫]:https://www.toptal.com/developers/sorting-algorithms/