冒泡排序
1、排序方法
將被排序的記錄數(shù)組R[1..n]垂直排列，每個(gè)記錄R[i]看作是重量為R[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。
（1）初始
R[1..n]為無序區(qū)。
（2）第一趟掃描
從無序區(qū)底部向上依次比較相鄰的兩個(gè)氣泡的重量，若發(fā)現(xiàn)輕者在下、重者在上，則交換二者的位置。即依次比較(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；對(duì)于每對(duì)氣泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，則交換R[j+1]和R[j]的內(nèi)容。
第一趟掃描完畢時(shí)，"最輕"的氣泡就飄浮到該區(qū)間的頂部，即關(guān)鍵字最小的記錄被放在最高位置R[1]上。
（3）第二趟掃描
掃描R[2..n]。掃描完畢時(shí)，"次輕"的氣泡飄浮到R[2]的位置上……
最后，經(jīng)過n-1 趟掃描可得到有序區(qū)R[1..n]
注意：
第i趟掃描時(shí)，R[1..i-1]和R[i..n]分別為當(dāng)前的有序區(qū)和無序區(qū)。掃描仍是從無序區(qū)底部向上直至該區(qū)頂部。掃描完畢時(shí)，該區(qū)中最輕氣泡飄浮到頂部位置R[i]上，結(jié)果是R[1..i]變?yōu)樾碌挠行騾^(qū)。
2、冒泡排序過程示例
對(duì)關(guān)鍵字序列為49 38 65 97 76 13 27 49的文件進(jìn)行冒泡排序的過程【參見動(dòng)畫演示】
3、排序算法
（1）分析
因?yàn)槊恳惶伺判蚨际褂行騾^(qū)增加了一個(gè)氣泡，在經(jīng)過n-1趟排序之后，有序區(qū)中就有n-1個(gè)氣泡，而無序區(qū)中氣泡的重量總是大于等于有序區(qū)中氣泡的重量，所以整個(gè)冒泡排序過程至多需要進(jìn)行n-1趟排序。
若在某一趟排序中未發(fā)現(xiàn)氣泡位置的交換，則說明待排序的無序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止。為此，在下面給出的算法中，引入一個(gè)布爾量exchange，在每趟排序開始前，先將其置為FALSE。若排序過程中發(fā)生了交換，則將其置為TRUE。各趟排序結(jié)束時(shí)檢查exchange，若未曾發(fā)生過交換則終止算法，不再進(jìn)行下一趟排序。
代碼：
template <typename T>
void SortPP(vector<T>&list){
for(int i=0;i<list.size();++i){
for(int j=list.size()-2;j>=i;j--){
if(list[j+1]<list[j]){
int t=list[j+1];
list[j+1]=list[j];
list[j]=t;
}
}
}
}