2014年計算機二級公共基礎(chǔ)知識總結(jié)第一章(6)

　　查看匯總：2014年計算機二級公共基礎(chǔ)知識總結(jié)匯總

　　排序技術(shù)

　　考點11 交換類排序法

　　考試鏈接:

　　考點11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。

　　冒泡排序法和快速排序法都屬于交換類排序法。

　　(1)冒泡排序法

　　首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最后最大者到了線性表的最后。

　　然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。

　　對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時已經(jīng)排好序。

　　在最壞的情況下，冒泡排序需要比較次數(shù)為n(n-1)/2。

　　(2)快速排序法

　　它的基本思想是：任取待排序序列中的某個元素作為基準(zhǔn)(一般取第一個元素)，通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。

　　疑難解答：冒泡排序和快速排序的平均執(zhí)行時間分別是多少?

　　冒泡排序法的平均執(zhí)行時間是O(n2)，而快速排序法的平均執(zhí)行時間是O(nlog2n)。

　　相關(guān)推薦：

　　計算機等級考試合格標(biāo)準(zhǔn)

　　2014年計算機等考上機六大注意事項

　　考試吧：2014年3月計算機等考真題及答案解析專題