冒泡排序可以說(shuō)是最簡(jiǎn)單的排序了。我們學(xué)習(xí)C語(yǔ)言循環(huán)的時(shí)候都會(huì)提到。
可見(jiàn)這是一種淺而易懂的排序算法！
但不見(jiàn)得這種算法就沒(méi)用處。首先，他很容易理解，這樣在各種教材中比較適合拿來(lái)“開(kāi)門(mén)見(jiàn)山”。其次是他很穩(wěn)定。 若明確知道即將排的數(shù)字很混亂，隨機(jī)性很強(qiáng)，則用冒泡排序也未償不可。 誰(shuí)讓他始終是O(n^2)呢。
冒泡排序法代碼：
1
void BubbleSort(int a[],int l)
2
{
3
for(int i = 0; i< l;++i)
4
{
5 for(int j = i+1; j< l; ++j)
6 {
7 if(a[j]<a[i])
8 {
9 int t = a[i];
10 a[i] = a[j];
11 a[j] = t;
12
}
13 }
14 }
15
}
從中我們可以看到，每次都會(huì)將后面的L-(i+1)個(gè)數(shù)拿來(lái)和a[i]比較，然后將小一點(diǎn)的換到前面。有人就覺(jué)得啊，這個(gè)每次都交換很費(fèi)性能，影響效率。所以他們就將a[j]和a[i]比較后的最小值的下標(biāo)記下來(lái)，當(dāng)比較完之后，最后記下的下標(biāo)就是最小的值的下標(biāo)，然后再進(jìn)行一次交換。于是便有了選擇排序法。
選擇排序法代碼：
1void SelectSort(int a[],int l)
2{
3 for(int i = 0; i< l; ++i)
4 {
5 int k=i;
6 for(int j = i+1; j<l;++j)
7 {
8
9 if(a[j]<a[k])
10 {
11 k=j;
12 }
13 }
14 int t = a[i];
15 a[i]=a[k];
16 a[k]= t;
17 }
18}
雖然，我們并沒(méi)有根本性地扭轉(zhuǎn)冒泡排序的地位。但效率是有明顯提升的，至少減少了L*(L-1)-L = L*(L-2) = L^2 - 2*L次交換！
另外，目前廣為使用的快速排序和選擇排序聯(lián)合使用，也會(huì)有意想不到的提升！
眾所周知，當(dāng)用快速排序法排序時(shí)，劃分到很細(xì)的時(shí)候，明顯很虧。 比如：兩三個(gè)數(shù)排序卻要?jiǎng)澐殖蓛啥眩@樣很劃不來(lái)。所以，我們可以設(shè)定一個(gè)閥值，當(dāng)快速排序劃分到一定粒度的時(shí)候，便采用選擇排序。 至于這個(gè)閥值，可以通過(guò)performace來(lái)測(cè)試，以得到一個(gè)“最優(yōu)值”
1void QSort(int a[],int l,int r)
2{
3 int p;
4 if(l<r)
5 {
6 if(l-r<= DEFINE_NUMBER)
7 SelectSort(a,l,r);
8 else
9 {
10 p = Partition(a,l,r);
11 QSort(a,l,p-1);
12 QSort(a,p+1,r);
13 }
14 }
15}