題目：
Class A{
Public:
Intk1;int k2;
};
一個數(shù)組A a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
下面哪一個是函數(shù)調用之后的結果
{{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. 以上都不對
分析：
這道題出的很有意思良拼，乍一看充边，題干這么大，可能會被唬住贬媒，其實冷靜下來看一下肘习，很簡單，就是一個排序的穩(wěn)定性非穩(wěn)定性的分析脖含。所謂穩(wěn)定性，即：保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同养葵，如果排序的結點僅僅是一個數(shù)，則穩(wěn)定性意義不大佃蚜，但是如果有多個鍵值夏醉，就需要考慮穩(wěn)定性的分析。例如氯夷，對于本題，如果排序算法是穩(wěn)定的腮考，那么因為原數(shù)組{3,4}排在{3,1}前玄捕，根據(jù)穩(wěn)定性的定義，排序的結果就一定不會出現(xiàn){3,1}排在{3,4}前的情況馅闽。而如果算法是不穩(wěn)定的馍迄，那么只能說，{3,1}有排在{3,4}前面的可能暴凑，需要根據(jù)具體的排序過程判斷是否相等的值會變換位置赘来。關于八種算法穩(wěn)定性的分析，可以查看http://hi.baidu.com/shismbwb/item/404c94898cfd2855850fab24嗦篱。選擇排序幌缝、快速排序、希爾排序腿宰、堆排序不是穩(wěn)定的排序算法，而冒泡排序吃度、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法伊者。
所以间护，首先明確四個函數(shù)都采用了什么樣的排序算法：
f1:選擇排序；f2:直接插入排序法精；f3:冒泡痴突，f4:快排
f2和f3是穩(wěn)定的，直接pass掉帮碰。然后非穩(wěn)定的再看是否變換了位置拾积。A和D如果走一遍程序的話，會發(fā)現(xiàn){3,4}和{3,1}這兩個元素是變了順序的拓巧。
對于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}}
所以正確
對于D答案输拇，a[5]={{3,4},{6,5},{2,7},{3,1},{1,2}}
第一遍排序的運行過程是這樣的贤斜。
初始：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}}
得到第一遍排序結果：{{1,2},{2,7},{3,1},{3,4},{6,5}}，找到了{3,1}的位置前普，已經在{3,4}的前面壹堰，所以最后的結果一定與預期結果相同。這里需要非常注意的是在_f41函數(shù)中,if(c(a[j],t)<=0)峻厚，如果寫成c(a[j],t)<0的話谆焊，則該答案也不會選擇。所以最終的答案是A和D
