對(duì)于冒泡排序，大家肯定都熟知，每一輪的冒泡都將最大的數(shù)排到最前面，每一輪的時(shí)間復(fù)雜度是O(n)，如果要排序的數(shù)組大小為n，要經(jīng)過n輪才能將數(shù)組中所有元素排序，所以總共的時(shí)間復(fù)雜度為O(n2)。
關(guān)于冒泡排序的源碼如下：
迭代型冒泡排序
#include <stdio.h>
#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0
void BubbleSort(int *a, int len) //待排數(shù)組a以及它的長(zhǎng)度len
{
int ordered = false;
int temp, i;
while(len && !ordered)
{
ordered = true; //也許一趟排序過程中沒有發(fā)生交換，說明數(shù)組已有序
for(i = 1; i < len; i++) //此時(shí)i從1開始比從0開始更好
{
if(a[i-1] > a[i])
{
ordered = false;
temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}
}
len--;
}
}
int main()
{
int a[5] = {5,1,2,3,4};
int i = 0;
int len = length(a);
BubbleSort(a,len);
for(i = 0; i < len; i++)
{
printf("%d ",a[i]);
}
return 0;
}對(duì)于快速排序，選出一個(gè)樞紐元素，然后將這個(gè)樞紐元素和數(shù)組所有元素進(jìn)行比較，把彼樞紐元素大的元素放在樞紐元素右邊，把比樞紐元素小的放在樞紐元素左邊， 而對(duì)于一趟快速排序要比較n次，每一趟快排的時(shí)間復(fù)雜度是O(n)，接下來你要對(duì)快排劃分出來的兩個(gè)子數(shù)組進(jìn)行遞歸快排，如果每一趟快排很平均的將數(shù)組劃分為兩個(gè)子數(shù)組，那么遞歸快排的深度就是O(lgn),所以總的時(shí)間復(fù)雜度就是O(nlgn)。
但是快排可以退化成冒泡，如果一旦每一趟快排，不幸的選擇出最大或最小元素作為樞紐元素，那么遞歸深度將變成n，則時(shí)間復(fù)雜度變成了O(n2)，此時(shí)快排的效率降到最低，退化為冒泡，所以快排對(duì)于樞紐元素的選擇上很關(guān)鍵，如果能選擇出每趟平均劃分?jǐn)?shù)組的樞紐元素，那么快排的效率最高，如何選擇樞紐元素將成為衡量快排的關(guān)鍵，我推薦使用三者取中法來選擇，每趟快排前，先將數(shù)組開始位置，中間位置，以及結(jié)尾位置的三個(gè)元素進(jìn)行比較，選擇其中的中間大的數(shù)做為樞紐元素，這樣可以降低退化成冒泡的風(fēng)險(xiǎn)，也可以使用任取一個(gè)數(shù)做為樞紐元素，這樣也可以降低風(fēng)險(xiǎn)。
我準(zhǔn)備開始寫遞歸型的冒泡排序和遞歸型的快速排序，你會(huì)發(fā)現(xiàn)兩者的區(qū)別，以及為什么快排會(huì)比冒泡好的原因，以及如何將程序從冒泡寫成快排。
遞歸型冒泡排序
#include <stdio.h>
#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0
int Sort(int *a, int len)
{
int ordered = true; //也許一趟排序過程中沒有發(fā)生交換，說明數(shù)組已有序
int temp, i;
for(i = 1; i < len; i++) //由此可以看出Sort()的時(shí)間復(fù)雜度是O(n)，跟待排數(shù)組的長(zhǎng)度有關(guān)。
{
if(a[i-1] > a[i])
{
ordered = false;
temp = a[i];
a[i] = a[i-1];
a[i-1] = temp;
}
}
return ordered;
}
void BubbleSort(int *a, int len) //冒泡排序的遞歸算法
{
if(len == 1) //如果只有一個(gè)元素，它就是最大的元素，無須在冒泡
return;
else
{
int ordered = Sort(a,len); //選出最大的元素，將所有比最大元素小的元素放在最大元素的左邊，而快排是將使用一個(gè)樞紐元素，將比樞紐元素大的放在樞紐右邊，小的放在左邊
if(ordered) //如果一趟冒泡，沒有交換元素，說明已有序
return;
BubbleSort(a,len-1); //遞歸冒泡出最大元素后面的所有元素，如果快排將作為快排的左遞歸
//如果快排會(huì)有右遞歸
}
}
int main()
{
int a[10] = {10,1,5,2,4,3,6,7,9,8};
int i = 0;
int len = length(a);
BubbleSort(a,len);
for(i = 0; i < len; i++)
{
printf("%d ",a[i]);
}
return 0;
}遞歸快速排序
#include <stdio.h>
#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0
int Sort(int *a, int low, int high)
{
int pivot = a[low]; //這里每次的樞紐元素都取了待排數(shù)組的第一個(gè)元素，記住是a[low],而不是a[0]
if(low < high) //時(shí)間復(fù)雜度是O(n),n是數(shù)組長(zhǎng)度
{
while(a[high] >= pivot && low < high)
high --;
a[low] = a[high];
while(a[low] <= pivot && low <high)
low ++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
void QuickSort(int *a, int low, int high)
{
if(low >= high)
return ;
else
{
int mid = Sort(a,low,high); //劃分子遞歸數(shù)組
QuickSort(a,low,mid-1); //左遞歸
QuickSort(a,mid+1,high); //右遞歸，一旦右遞歸mid+1=high，將退化成冒泡，遞歸深度將變成n，n為數(shù)組長(zhǎng)度
}
}
int main()
{
int a[5] = {3,1,5,2,4};
int i = 0;
int len = length(a);
QuickSort(a,0,len-1);
for(i = 0; i < len; i++)
{
printf("%d ",a[i]);
}
return 0;
}由上可以看出，遞歸型的冒泡就是一個(gè)只有右子樹的遞歸樹，遞歸深度為O(n)，而好的快速排序，將產(chǎn)生一個(gè)平衡的二叉樹，遞歸深度為O(lgn)，所以快排是對(duì)冒泡的一個(gè)巨大的改進(jìn)。
喜歡 
頂
難過
囧
圍觀
無聊