原文地址http://www.cnblogs.com/liukemng/p/3715925.html

之前看到一個(gè)題目，大概是：有一個(gè)長(zhǎng)度為n的數(shù)組，數(shù)組內(nèi)的元素取值范圍為0到m，且不相等，要求元素經(jīng)過(guò)n次移動(dòng)后使數(shù)組有序（即算法的復(fù)雜度為O(n)）。看到題目后想了快速排序和歸并排序發(fā)現(xiàn)并不能滿(mǎn)足題目要求，直到有次看書(shū)又看到了桶排序然后豁然開(kāi)朗，所以決定把這些排序算法再寫(xiě)一遍，加深記憶。

約定：之后的文章默認(rèn)待排序的數(shù)組大小都為n，排序結(jié)果為由小到大，采用c#作為代碼實(shí)現(xiàn)。

1.基本的冒泡排序算法：

基本思想：

冒泡排序外層共需要對(duì)序列進(jìn)行n-1次遍歷，內(nèi)層從e[0]到e[n-i]（i為外層遍歷的次數(shù)）兩兩進(jìn)行比較，如果e[j-1]>e[j]則進(jìn)行交換，直到比較e[0]和e[1]后為止，冒泡排序算法的時(shí)間復(fù)雜度為O(n2)；；

代碼實(shí)現(xiàn)：

/// <summary>/// 基本的冒泡排序算法/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void BubbleSort(int[] intArray, int length){    int i, j, temp;    for (i = 0; i < length; i++)    {        for (j = 1; j < length - i; j++)        {            if (intArray[j - 1] > intArray[j])            {                temp = intArray[j - 1];                intArray[j - 1] = intArray[j];                intArray[j] = temp;            }        }    }}
2.改進(jìn)的冒泡排序算法一：
上面的排序算法不管某次循環(huán)后數(shù)組是否已經(jīng)有序，依然繼續(xù)遍歷，這樣的話(huà)在對(duì)基本有序的數(shù)組進(jìn)行排序是效率顯然是很低的，我們可以設(shè)置一個(gè)標(biāo)志位，判斷某次遍歷后元素是否發(fā)生了交換，如果沒(méi)有發(fā)生交換則證明排序完成，結(jié)束遍歷從而提高效率 ；
代碼實(shí)現(xiàn)：
/// <summary>/// 改進(jìn)后的冒泡排序算法1/// 設(shè)立標(biāo)志判斷某次循環(huán)是否發(fā)生了交換，如果沒(méi)有發(fā)生交換則證明排序完成/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void BubbleSort1(int[] intArray, int length){    int i, temp, k = length;    bool flag = true;    while (flag)    {        flag = false;        for (i = 1; i < k; i++)        {            if (intArray[i - 1] > intArray[i])            {                flag = true;                temp = intArray[i - 1];                intArray[i - 1] = intArray[i];                intArray[i] = temp;            }        }        k--;    }}
3.改進(jìn)的冒泡排序算法二：
上面改進(jìn)后的冒泡排序算法還可以繼續(xù)改進(jìn)，比如在進(jìn)行第一次遍歷前序列元素排列是這樣的,我們發(fā)現(xiàn)當(dāng)把元素5,4進(jìn)行交換后,后面的元素已經(jīng)有序,則我們可以設(shè)置一個(gè)標(biāo)志,記錄最后一次交換元素的位置,在以后的遍歷中可以根據(jù)設(shè)置的標(biāo)志來(lái)縮短要比較元素的下界;
3
2
1
5
4
6
7
8
9
代碼實(shí)現(xiàn)：
/// <summary>/// 改進(jìn)后的冒泡排序算法2/// 記錄最后一次交換的位置作為排序交換的結(jié)束位置/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void BubbleSort2(int[] intArray, int length){    int i, temp, index, k = length;    while (k > 0)    {        index = k;        k = 0;        for (i = 1; i < index; i++)        {            if (intArray[i - 1] > intArray[i])            {                k = i;                temp = intArray[i - 1];                intArray[i - 1] = intArray[i];                intArray[i] = temp;            }        }    }}
以上就是冒泡排序算法的內(nèi)容。