1.6排序技術(shù)
考點(diǎn)11 交換類排序法
考試鏈接:
考點(diǎn)11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。
冒泡排序法和快速排序法都屬于交換類排序法。
（1）冒泡排序法
首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的大者往后移動，最后者到了線性表的最后。
然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。
對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。
在最壞的情況下，冒泡排序需要比較次數(shù)為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。
疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少？
冒泡排序法的平均執(zhí)行時(shí)間是O（n2），而快速排序法的平均執(zhí)行時(shí)間是O（nlog2n）。
考點(diǎn)11 交換類排序法
考試鏈接:
考點(diǎn)11屬于比較難的內(nèi)容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應(yīng)該熟練掌握幾種排序算法的基本過程。
冒泡排序法和快速排序法都屬于交換類排序法。
（1）冒泡排序法
首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個(gè)元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的大者往后移動，最后者到了線性表的最后。
然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個(gè)相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。
對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)已經(jīng)排好序。
在最壞的情況下，冒泡排序需要比較次數(shù)為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序。
疑難解答：冒泡排序和快速排序的平均執(zhí)行時(shí)間分別是多少？
冒泡排序法的平均執(zhí)行時(shí)間是O（n2），而快速排序法的平均執(zhí)行時(shí)間是O（nlog2n）。