題目：
Class A{
Public:
Intk1;int k2;
};
一個(gè)數(shù)組A a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
下面哪一個(gè)是函數(shù)調(diào)用之后的結(jié)果
{{1,2},{2,7},{3,1},{3,4},{6,5}}
f1:選擇排序；f2:直接插入排序；f3:冒泡，f4:快排
A. f1(a,5,cmp)
B. f2(a,5,cmp)
C. f3(a,5,cmp)
D. f4(a,5,cmp)
E. 以上都不對(duì)
分析：
這道題出的很有意思，乍一看，題干這么大，可能會(huì)被唬住，其實(shí)冷靜下來看一下，很簡(jiǎn)單，就是一個(gè)排序的穩(wěn)定性非穩(wěn)定性的分析。所謂穩(wěn)定性，即：保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同，如果排序的結(jié)點(diǎn)僅僅是一個(gè)數(shù)，則穩(wěn)定性意義不大，但是如果有多個(gè)鍵值，就需要考慮穩(wěn)定性的分析。例如，對(duì)于本題，如果排序算法是穩(wěn)定的，那么因?yàn)樵瓟?shù)組{3,4}排在{3,1}前，根據(jù)穩(wěn)定性的定義，排序的結(jié)果就一定不會(huì)出現(xiàn){3,1}排在{3,4}前的情況。而如果算法是不穩(wěn)定的，那么只能說，{3,1}有排在{3,4}前面的可能，需要根據(jù)具體的排序過程判斷是否相等的值會(huì)變換位置。關(guān)于八種算法穩(wěn)定性的分析，可以查看http://hi.baidu.com/shismbwb/item/404c94898cfd2855850fab24。選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法。
所以，首先明確四個(gè)函數(shù)都采用了什么樣的排序算法：
f1:選擇排序；f2:直接插入排序；f3:冒泡，f4:快排
f2和f3是穩(wěn)定的，直接pass掉。然后非穩(wěn)定的再看是否變換了位置。A和D如果走一遍程序的話，會(huì)發(fā)現(xiàn){3,4}和{3,1}這兩個(gè)元素是變了順序的。
對(duì)于A答案，a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
第一遍排序：{{1,2},{6,5},{2,7},{3,1},{3,4}}
第二遍排序：{{1,2},{2,7},{6,5},{3,1},{3,4}}
第三遍排序：{{1,2},{2,7},{3,1},{6,5},{3,4}}
第四遍排序：{{1,2},{2,7},{3,1},{3,4},{6,5}}
所以正確
對(duì)于D答案，a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
第一遍排序的運(yùn)行過程是這樣的。
初始：low=0,high=4,i=0,t={3,4}
For循環(huán)：
J=1, c({6,5},t)>0,i=0,沒有交換(a[i],a[j]),{{3,4},{6,5},{2,7},{3,1},{1,2}}
J=2,c({2,7},t)<0,i=1,交換({6,5},{2,7}),{{3,4},{2,7},{6,5},{3,1},{1,2}}
J=3, c({3,1},t)=0,i=2,交換({6,5},{3,1})，{{3,4},{2,7},{3,1},{6,5},{1,2}}
J=4, c({1,2},t)<0,i=3，交換({6,5},{1,2})，{{3,4},{2,7},{3,1},{1,2},{6,5}}
最后，執(zhí)行exchange(a,low,i), 交換({3,4},{1,2})，{{1,2},{2,7},{3,1},{3,4},{6,5}}
得到第一遍排序結(jié)果：{{1,2},{2,7},{3,1},{3,4},{6,5}}，找到了{(lán)3,1}的位置，已經(jīng)在{3,4}的前面，所以最后的結(jié)果一定與預(yù)期結(jié)果相同。這里需要非常注意的是在_f41函數(shù)中,if(c(a[j],t)<=0)，如果寫成c(a[j],t)<0的話，則該答案也不會(huì)選擇。所以最終的答案是A和D
