文章責編:lipeng566
看了本文的網(wǎng)友還看了學歷| 高考 中考 考研 自考 成考 外語| 四六級 職稱英語 商務英語 公共英語 資格| 公務員 報關員 銀行 證券 司法 導游 教師 計算機| 等考 軟考
工程|一建 二建 造價師 監(jiān)理師 咨詢師 安全師 結構師 估價師 造價員 會計| 會計證 會計職稱 注會 經(jīng)濟師 稅務師 醫(yī)學| 衛(wèi)生資格 醫(yī)師 藥師 [更多]
查看匯總:2014年計算機二級公共基礎知識總結匯總
排序技術
考點11 交換類排序法
考試鏈接:
考點11屬于比較難的內容,一般以選擇題的形式考查,考核幾率為30%,分值約為2分,讀者應該熟練掌握幾種排序算法的基本過程。
冒泡排序法和快速排序法都屬于交換類排序法。
(1)冒泡排序法
首先,從表頭開始往后掃描線性表,逐次比較相鄰兩個元素的大小,若前面的元素大于后面的元素,則將它們互換,不斷地將兩個相鄰元素中的大者往后移動,最后最大者到了線性表的最后。
然后,從后到前掃描剩下的線性表,逐次比較相鄰兩個元素的大小,若后面的元素小于前面的元素,則將它們互換,不斷地將兩個相鄰元素中的小者往前移動,最后最小者到了線性表的最前面。
對剩下的線性表重復上述過程,直到剩下的線性表變空為止,此時已經(jīng)排好序。
在最壞的情況下,冒泡排序需要比較次數(shù)為n(n-1)/2。
(2)快速排序法
它的基本思想是:任取待排序序列中的某個元素作為基準(一般取第一個元素),通過一趟排序,將待排元素分為左右兩個子序列,左子序列元素的排序碼均小于或等于基準元素的排序碼,右子序列的排序碼則大于基準元素的排序碼,然后分別對兩個子序列繼續(xù)進行排序,直至整個序列有序。
疑難解答:冒泡排序和快速排序的平均執(zhí)行時間分別是多少?
冒泡排序法的平均執(zhí)行時間是O(n2),而快速排序法的平均執(zhí)行時間是O(nlog2n)。
相關推薦:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內蒙古 |