第C語(yǔ)言超詳細(xì)梳理排序算法的使用當(dāng)gap1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap==1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比

選擇排序

直接選擇排序

解析

每一次遍歷待排序的數(shù)據(jù)元素從中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始（或者末尾）位置，直到全部待排序的數(shù)據(jù)元素排完

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

//選擇排序

voidSelectSort(int*a,intn)

intbegin=0,end=n-1;//記錄下標(biāo)

while(beginend)

intmini=begin;

for(inti=begin;i=end;i++)

//遍歷找到最小數(shù)據(jù)并記錄下標(biāo)

if(a[i]a[mini])

mini=i;

Swap(a[begin],a[mini]);//交換

begin++;//縮小范圍

}

總結(jié)

時(shí)間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

不推薦使用

堆排序

堆排序是指利用堆（數(shù)據(jù)結(jié)構(gòu)）進(jìn)行選擇數(shù)據(jù)的一種排序算法

基礎(chǔ)思想：

先將原數(shù)組建成堆，需要注意的是排升序要建大堆，排降序建小堆

注：以大堆為例

一個(gè)根節(jié)點(diǎn)與子節(jié)點(diǎn)數(shù)據(jù)如果不符合大堆結(jié)構(gòu)，那么則對(duì)根節(jié)點(diǎn)數(shù)據(jù)進(jìn)行向下調(diào)整，而向下調(diào)整的前提是左右子樹(shù)也符合大堆結(jié)構(gòu),所以從堆尾數(shù)據(jù)的根節(jié)點(diǎn)位置開(kāi)始向下調(diào)整建大堆

大堆堆頂數(shù)據(jù)一定是待排數(shù)據(jù)中最大的，將堆頂數(shù)據(jù)與堆尾數(shù)據(jù)交換,交換后將除堆尾數(shù)據(jù)看成新堆，對(duì)現(xiàn)堆頂數(shù)據(jù)進(jìn)行向下調(diào)整成大堆,以此循環(huán)直至排列完畢

向下調(diào)整：

找到子節(jié)點(diǎn)中的較大數(shù)據(jù)節(jié)點(diǎn)比較，如果父節(jié)點(diǎn)數(shù)據(jù)比大子節(jié)點(diǎn)小則交換，直到不符合則停止向下交換，此時(shí)再次構(gòu)成了一個(gè)大堆結(jié)構(gòu).

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

voidAdjustdown(int*a,intn,intparent)

intchild=parent*2+1;

while(childn)

//找到數(shù)據(jù)大的子結(jié)點(diǎn)

if(child+1na[child+1]a[child])

child++;

//父節(jié)點(diǎn)數(shù)據(jù)小于子節(jié)點(diǎn)就交換

if(a[parent]a[child])

Swap(a[parent],a[child]);

//更新下標(biāo)

parent=child;

child=parent*2+1;

else//否則向下調(diào)整完畢

break;

//堆排序(升序)建大堆

voidHeapSort(int*a,intn)

inti;

//建大堆

for(i=(n-1-1)/2;ii--)

Adjustdown(a,n,i);

//交換調(diào)整

for(i=n-1;ii--)

Swap(a[0],a[i]);//與當(dāng)前堆尾數(shù)據(jù)交換

Adjustdown(a,i,0);//對(duì)交換后堆頂數(shù)據(jù)進(jìn)行向下調(diào)整

}

總結(jié)：

堆排序使用堆來(lái)選數(shù)，效率就高了很多。

時(shí)間復(fù)雜度：O(N*logN)

空間復(fù)雜度：O(1)

穩(wěn)定性：不穩(wěn)定

交換排序之冒泡排序

冒泡排序

每次遍歷數(shù)組，對(duì)相鄰數(shù)據(jù)進(jìn)行比較，不符合排序要求則交換

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

//冒泡排序

voidBubbleSort(int*a,intn)

inti,j;

for(i=0;in-1;i++)//趟數(shù)

for(j=0;jn-1-i;j++)//比較次數(shù)

if(a[j]a[j+1]