搜狗2016 C++工程師筆試題
快速排序在下面哪種情況下優(yōu)勢最明顯()
A 數據有多個(gè)相同數值
B 數據基本有序
C數據基本無(wú)序
D 數據無(wú)任何相同數值
先思考一下再看答案吧!
因為總是會(huì )有人一看題目就看到答案了
這樣就很影響自己的思考
既然這樣
我們就思考一下再往下看
參考答案：C
快速排序屬于內部排序;
快速排序的.實(shí)現基于分治法，具體分為三個(gè)步驟。假設待排序的序列為L(cháng)[m..n]。
分解：序列L[m .. n]被劃分成兩個(gè)可能為空的子序列L[m .. pivot-1]和L[pivot+1 .. n]，使L[m .. pivot-1]的每個(gè)元素均小于或等于L[pivot]，同時(shí)L[pivot+1.. n]的每個(gè)元素均大于L[pivot]。其中L[pivot]稱(chēng)為這一趟分割中的主元(也稱(chēng)為樞軸、支點(diǎn))。
解決：通過(guò)遞歸調用快速排序，對子序列L[m .. pivot-1]和L[pivot+1 .. r]排序。
合并：由于兩個(gè)子序列是就地排序的，所以對它們的合并不需要操作，整個(gè)序列L[m .. n]已排好序。
快速排序每次將待排序數組分為兩個(gè)部分，在理想狀況下，每一次都將待排序數組劃分成等長(cháng)兩個(gè)部分，則需要logn次劃分。
而在最壞情況下，即數組已經(jīng)有序或大致有序的情況下，每次劃分只能減少一個(gè)元素，快速排序將不幸退化為冒泡排序，所以快速排序時(shí)間復雜度下界為O(nlogn)，最壞情況為O(n^2)。在實(shí)際應用中，快速排序的平均時(shí)間復雜度為O(nlogn)。
【搜狗2016 C++工程師筆試題】相關(guān)文章：
威盛公司軟件C++工程師筆試題12-17
嵌入式C/C++面試題201611-12
2016年華為認證C/C++筆試題目11-06
華為C++筆試題12-25
聯(lián)想C++筆試題12-24
Sony C++筆試題12-19
C++筆試題目分享12-20
華為c/c++筆試題12-19