搜狗 C++工程師筆試題

搜狗2016 C++工程師筆試題

　　快速排序在下面哪種情況下優(yōu)勢最明顯()

　　A 數(shù)據(jù)有多個相同數(shù)值

　　B 數(shù)據(jù)基本有序

　　C數(shù)據(jù)基本無序

　　D 數(shù)據(jù)無任何相同數(shù)值

　　先思考一下再看答案吧!

　　因為總是會有人一看題目就看到答案了

　　這樣就很影響自己的思考

　　既然這樣

　　我們就思考一下再往下看

　　參考答案：C

　　快速排序?qū)儆趦?nèi)部排序;

　　快速排序的.實現(xiàn)基于分治法，具體分為三個步驟。假設(shè)待排序的序列為L[m..n]。

　　分解：序列L[m .. n]被劃分成兩個可能為空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每個元素均小于或等于L[pivot]，同時L[pivot+1.. n]的每個元素均大于L[pivot]。其中L[pivot]稱為這一趟分割中的主元(也稱為樞軸、支點(diǎn))。

　　解決：通過遞歸調(diào)用快速排序，對子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。

　　合并：由于兩個子序列是就地排序的，所以對它們的合并不需要操作，整個序列L[m .. n]已排好序。

　　快速排序每次將待排序數(shù)組分為兩個部分，在理想狀況下，每一次都將待排序數(shù)組劃分成等長兩個部分，則需要logn次劃分。

　　而在最壞情況下，即數(shù)組已經(jīng)有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判颍�所以快速排序時間復(fù)雜度下界為O(nlogn)，最壞情況為O(n^2)。在實際應(yīng)用中，快速排序的平均時間復(fù)雜度為O(nlogn)。

【搜狗2016 C++工程師筆試題】相關(guān)文章：

威盛公司軟件C++工程師筆試題12-17

2016年c++經(jīng)典面試題及答案10-03

嵌入式C/C++面試題201611-12

2016年華為認(rèn)證C/C++筆試題目11-06

華為C++筆試題12-25

聯(lián)想C++筆試題12-24

Sony C++筆試題12-19

C++筆試題目分享12-20

華為c/c++筆試題12-19