交換排序：兩兩比較待排序記錄的關鍵碼，若是逆置，則交換，直到無逆置。其中最簡單的交換排序是：冒泡排序。
冒泡排序(Bubble Sort，也叫起泡排序)：不斷地比較相鄰的記錄，若是不滿足排序要求，則交換。
交換時，可從前向後，也可從後向前。看一個從前向後的排序過程：
原序列 12 3 45 33 6
下標 0 1 2 3 4
第一趟：
3 12 45 33 6 (3,12交換)
3 12 45 33 6 (12,45不用交換)
3 12 33 45 6 (45,33交換)
3 12 33 6 45 (45,6交換)
第二趟：
3 12 33 6 45 (3,12不用交換)
3 12 33 6 45 (12,33不用交換)
3 12 6 33 45 (33,6交換)
第三趟：
3 12 6 33 45 (3,12不用交換)
3 6 12 33 45 (12,6交換)
第四趟：
3 6 12 33 45 (3,6不用交換)
結束。以上過程非常之詳盡，相信你一定懂了。
代碼一：
void BubbleSort10(int a[], int n) //從左向右
{
if (a && n > 1)
{
int i,j;
for (i = 1; i < n; i++) //最多只需進行n-1趟排序
for (j = 0; j < n - i ; j++)
{
if (a[j] > a[j+1])
Swap(a[j], a[j+1]);
}
}
}
void BubbleSort11(int a[], int n) //從右向左
{
if (a && n > 1)
{
int i,j;
for (i = 1; i < n; i++)
for (j = n - 1; j>=i; j--)
{
if (a[j - 1] > a[j])
Swap(a[j - 1], a[j]);
}
}
}
是的！既然如此，下一趟排序就不用進行了。
針對代碼一，給出優化的代碼二：
void BubbleSort20(int a[], int n) //從左向右
{
if (a && n > 1)
{
int i,j = n-1;
bool flag = true;
while(flag)
{
flag = false;
for (i = 0; i < j; i++)
if (a[i] > a[i+1])
{
Swap(a[i], a[i+1]);
flag = true;
}
j--;
}
}
}
void BubbleSort21(int a[], int n) //從右向左
{
if (a && n > 1)
{
int i,j = 1;
bool flag = true;
while(flag)
{
flag = false;
for (i = n - 1; i >= j; i--)
if (a[i - 1] > a[i])
{
Swap(a[i - 1], a[i]);
flag = true;
}
j++;
}
}
}有的，記錄上一趟排序時交換元素的最遠距離，下一趟排序最遠只到這個位置。
針對代碼二，給出優化的代碼三：
void BubbleSort30(int a[], int n) //從左向右
{
if (a && n > 1)
{
int i,k,j = n-1;
bool flag = true;
while(flag)
{
flag = false;
k = 0;
for (i = 0; i < j; i++)
{
if (a[i] > a[i+1])
{
Swap(a[i], a[i+1]);
flag = true;
k = i;
}
}
if (k == 0)
break;
j = k;
}
}
}
void BubbleSort31(int a[], int n) //從右向左
{
if (a && n > 1)
{
int i,k,j = 1;
bool flag = true;
while(flag)
{
flag = false;
k = n - 1;
for (i = n - 1; i >= j; i--)
{
if (a[i - 1] > a[i])
{
Swap(a[i - 1], a[i]);
flag = true;
k = i;
}
}
if (k == n - 1)
break;
j = k;
}
}
}
交換方法的代碼是這樣：
void Swap(int &a, int &b)
{
if(a!=b)
{
a^=b;
b^=a;
a^=b;
}
}
小結：
冒泡排序是穩定的，但不高效。時間復雜度是O(n^2)。
轉載請注明出處，本文地址：http://blog.csdn.net/zhangxiangdavaid/article/details/30271613
若是有所幫助，頂一個哦！
專欄目錄看這裡：數據結構與算法目錄
