冒泡排序(Bubble Sort)

冒泡排序是一種極其簡單的排序算法，也是我所學(xué)的第一個排序算法。它重復(fù)地走訪過要排序的元素，依次比較相鄰兩個元素，如果他們的順序錯誤就把他們調(diào)換過來，直到?jīng)]有元素再需要交換，排序完成。這個算法的名字由來是因為越小(或越大)的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

　　冒泡排序算法的運作如下：

比較相鄰的元素，如果前一個比后一個大，就把它們兩個調(diào)換位置。對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，除了最后一個。持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

　　由于它的簡潔，冒泡排序通常被用來對于程序設(shè)計入門的學(xué)生介紹算法的概念。冒泡排序的代碼如下：

#include//?分類?--------------?內(nèi)部比較排序
//?數(shù)據(jù)結(jié)構(gòu)?----------?數(shù)組
//?最差時間復(fù)雜度?----?O(n^2)
//?最優(yōu)時間復(fù)雜度?----?如果能在內(nèi)部循環(huán)第一次運行時,使用一個旗標來表示有無需要交換的可能,可以把最優(yōu)時間復(fù)雜度降低到O(n)
//?平均時間復(fù)雜度?----?O(n^2)
//?所需輔助空間?------?O(1)
//?穩(wěn)定性?------------?穩(wěn)定

void?Swap(int?A[],?int?i,?int?j)
{
????int?temp?=?A[i];
????A[i]?=?A[j];
????A[j]?=?temp;
}

void?BubbleSort(int?A[],?int?n)
{
????for?(int?j?=?0;?j?<?n?-?1;?j++)?????????//?每次最大元素就像氣泡一樣"浮"到數(shù)組的最后
????{
????????for?(int?i?=?0;?i?<?n?-?1?-?j;?i++)?//?依次比較相鄰的兩個元素,使較大的那個向后移
????????{
????????????if?(A[i]?>?A[i?+?1])????????????//?如果條件改成A[i]?>=?A[i?+?1],則變?yōu)椴环€(wěn)定的排序算法
????????????{
????????????????Swap(A,?i,?i?+?1);
????????????}
????????}
????}
}

int?main()
{
????int?A[]?=?{?6,?5,?3,?1,?8,?7,?2,?4?};????//?從小到大冒泡排序
????int?n?=?sizeof(A)?/?sizeof(int);
????BubbleSort(A,?n);
????printf("冒泡排序結(jié)果：");
????for?(int?i?=?0;?i?<?n;?i++)
????{
????????printf("%d?",?A[i]);
????}
????printf("n");
????return?0;
}

?

　　上述代碼對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行冒泡排序的實現(xiàn)過程如下

　　使用冒泡排序為一列數(shù)字進行排序的過程如右圖所示：　　

　　盡管冒泡排序是最容易了解和實現(xiàn)的排序算法之一，但它對于少數(shù)元素之外的數(shù)列排序是很沒有效率的。

選擇排序(Selection Sort)

?

　　選擇排序也是一種簡單直觀的排序算法。它的工作原理很容易理解：初始時在序列中找到最?。ù螅┰兀诺叫蛄械钠鹗嘉恢米鳛橐雅判蛐蛄?；然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

　　注意選擇排序與冒泡排序的區(qū)別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最小（大）元素放到合適的位置；而選擇排序每遍歷一次都記住了當前最?。ù螅┰氐奈恢?，最后僅需一次交換操作即可將其放到合適的位置。

　　選擇排序的代碼如下：

#include//?分類?--------------?內(nèi)部比較排序
//?數(shù)據(jù)結(jié)構(gòu)?----------?數(shù)組
//?最差時間復(fù)雜度?----?O(n^2)
//?最優(yōu)時間復(fù)雜度?----?O(n^2)
//?平均時間復(fù)雜度?----?O(n^2)
//?所需輔助空間?------?O(1)
//?穩(wěn)定性?------------?不穩(wěn)定

void?Swap(int?A[],?int?i,?int?j)
{
????int?temp?=?A[i];
????A[i]?=?A[j];
????A[j]?=?temp;
}

void?SelectionSort(int?A[],?int?n)
{
????for?(int?i?=?0;?i?<?n?-?1;?i++)?????????//?i為已排序序列的末尾
????{
????????int?min?=?i;
????????for?(int?j?=?i?+?1;?j?<?n;?j++)?????//?未排序序列
????????{
????????????if?(A[j]?<?A[min])??????????????//?找出未排序序列中的最小值
????????????{
????????????????min?=?j;
????????????}
????????}
????????if?(min?!=?i)
????????{
????????????Swap(A,?min,?i);????//?放到已排序序列的末尾，該操作很有可能把穩(wěn)定性打亂，所以選擇排序是不穩(wěn)定的排序算法
????????}
????}
}

int?main()
{
????int?A[]?=?{?8,?5,?2,?6,?9,?3,?1,?4,?0,?7?};?//?從小到大選擇排序
????int?n?=?sizeof(A)?/?sizeof(int);
????SelectionSort(A,?n);
????printf("選擇排序結(jié)果：");
????for?(int?i?=?0;?i?<?n;?i++)
????{
????????printf("%d?",?A[i]);
????}
????printf("n");
????return?0;
}

?

?　　上述代碼對序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }進行選擇排序的實現(xiàn)過程如右圖　　

?

　　使用選擇排序為一列數(shù)字進行排序的宏觀過程：　　

　　選擇排序是不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在最小元素與A[i]交換的時刻。

　　比如序列：{?5, 8,?5,?2, 9 }，一次選擇的最小元素是2，然后把2和第一個5進行交換，從而改變了兩個元素5的相對次序。

　插入排序(Insertion Sort)

?

　　插入排序是一種簡單直觀的排序算法。它的工作原理非常類似于我們抓撲克牌

?

　　對于未排序數(shù)據(jù)(右手抓到的牌)，在已排序序列(左手已經(jīng)排好序的手牌)中從后向前掃描，找到相應(yīng)位置并插入。

　　插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

　　具體算法描述如下：

從第一個元素開始，該元素可以認為已經(jīng)被排序取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描如果該元素（已排序）大于新元素，將該元素移到下一位置重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置將新元素插入到該位置后重復(fù)步驟2~5

　　插入排序的代碼如下：

#include//?分類?-------------?內(nèi)部比較排序
//?數(shù)據(jù)結(jié)構(gòu)?----------?數(shù)組
//?最差時間復(fù)雜度?----?最壞情況為輸入序列是降序排列的,此時時間復(fù)雜度O(n^2)
//?最優(yōu)時間復(fù)雜度?----?最好情況為輸入序列是升序排列的,此時時間復(fù)雜度O(n)
//?平均時間復(fù)雜度?----?O(n^2)
//?所需輔助空間?------?O(1)
//?穩(wěn)定性?------------?穩(wěn)定

void?InsertionSort(int?A[],?int?n)
{
????for?(int?i?=?1;?i?<?n;?i++)?????????//?類似抓撲克牌排序
????{
????????int?get?=?A[i];?????????????????//?右手抓到一張撲克牌
????????int?j?=?i?-?1;??????????????????//?拿在左手上的牌總是排序好的
????????while?(j?>=?0?&&?A[j]?>?get)????//?將抓到的牌與手牌從右向左進行比較
????????{
????????????A[j?+?1]?=?A[j];????????????//?如果該手牌比抓到的牌大，就將其右移
????????????j--;
????????}
????????A[j?+?1]?=?get;?//?直到該手牌比抓到的牌小(或二者相等)，將抓到的牌插入到該手牌右邊(相等元素的相對次序未變，所以插入排序是穩(wěn)定的)
????}
}

int?main()
{
????int?A[]?=?{?6,?5,?3,?1,?8,?7,?2,?4?};//?從小到大插入排序
????int?n?=?sizeof(A)?/?sizeof(int);
????InsertionSort(A,?n);
????printf("插入排序結(jié)果：");
????for?(int?i?=?0;?i?<?n;?i++)
????{
????????printf("%d?",?A[i]);
????}
????printf("n");
????return?0;
}

?

?　　上述代碼對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行插入排序的實現(xiàn)過程如下

　　使用插入排序為一列數(shù)字進行排序的宏觀過程：　　

　　插入排序不適合對于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，比如量級小于千，那么插入排序還是一個不錯的選擇。 插入排序在工業(yè)級庫中也有著廣泛的應(yīng)用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序（通常為8個或以下）。