查看匯總：2014年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)總結(jié)匯總
排序技術(shù)
考點(diǎn)11 交換類排序法
考試鏈接:
考點(diǎn)11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。
冒泡排序法和快速排序法都屬于交換類排序法。
(1)冒泡排序法
首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的大者往后移動(dòng)，最后最大者到了線性表的最后。
然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移動(dòng)，最后最小者到了線性表的最前面。
對(duì)剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。
在最壞的情況下，冒泡排序需要比較次數(shù)為n(n-1)/2。
(2)快速排序法
它的基本思想是：任取待排序序列中的某個(gè)元素作為基準(zhǔn)(一般取第一個(gè)元素)，通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。
疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少?
冒泡排序法的平均執(zhí)行時(shí)間是O(n2)，而快速排序法的平均執(zhí)行時(shí)間是O(nlog2n)。
相關(guān)推薦：
計(jì)算機(jī)等級(jí)考試合格標(biāo)準(zhǔn)
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |