請教，快速排序的空間復(fù)雜度？快速排序每次將要排序的數(shù)組分成兩部分。在理想情況下，如果要排序的數(shù)組每次被劃分為兩個(gè)等長的部分，則需要將其劃分logn次。在最壞的情況下，即當(dāng)數(shù)組是有序的或大致有序的時(shí)，每

請教，快速排序的空間復(fù)雜度？

快速排序每次將要排序的數(shù)組分成兩部分。在理想情況下，如果要排序的數(shù)組每次被劃分為兩個(gè)等長的部分，則需要將其劃分logn次。在最壞的情況下，即當(dāng)數(shù)組是有序的或大致有序的時(shí)，每個(gè)分區(qū)只能減少一個(gè)元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判?，因此快速排序的時(shí)間復(fù)雜度下限為O（nlogn），最壞的情況是O（n^2）。在實(shí)際應(yīng)用中，快速排序的平均時(shí)間復(fù)雜度為O（nlogn）。在序列的操作中，快速排序只需要常量空間?？臻g復(fù)雜度為s（1）。但是需要注意的是，遞歸堆棧需要花費(fèi)最少的logn和最多的n個(gè)空間。

下列四種排序中（ ）的空間復(fù)雜度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆？

快速排序通常是o（log2n），這也是遞歸的深度。如果基準(zhǔn)值選擇不當(dāng)，則為O（n）。當(dāng)然，即使結(jié)果不是遞歸的，冒泡排序也屬于簡單排序，只需要幾個(gè)輔助循環(huán)變量。因此，對于o（1）Hill排序，只修改了直接插入排序，一般不設(shè)置特殊的收縮增量序列，這也是o（1）堆排序只需要一個(gè)中間輔助變量和一些循環(huán)變量，這也是o（1）因此：答案是a

直接選擇排序的空間復(fù)雜度和冒泡排序是O（1），因?yàn)橹皇褂昧藘蓚€(gè)循環(huán)變量和一到兩個(gè)flag和exchange中間變量，這與要排序的記錄數(shù)無關(guān)。時(shí)間復(fù)雜度：冒泡排序最好有有序關(guān)鍵字，n-1關(guān)鍵字比較，0記錄移動(dòng)，最差的是完全相反的順序，關(guān)鍵字比為0與n（n-1）/2次比較，當(dāng)記錄移動(dòng)3N（n-1）/2次時(shí)，冒泡排序的時(shí)間復(fù)雜度為O（n^2）。直接選擇排序關(guān)鍵字的比較次數(shù)總是n（n-1）/2次。當(dāng)記錄移動(dòng)至少0次，最多3（n-1）次時(shí)，直接選擇排序的時(shí)間復(fù)雜度為O（n^2）

選擇排序和冒泡排序的空間復(fù)雜度和時(shí)間復(fù)雜度是多少？

冒泡排序、插入排序、合并排序和基數(shù)排序都是穩(wěn)定排序?？焖倥判?、選擇排序、堆排序和希爾排序都是不穩(wěn)定排序。冒泡排序、插入排序和選擇排序的時(shí)間復(fù)雜度為O（n^2），合并排序、堆排序和快速排序的時(shí)間復(fù)雜度為O（n*log（n）），冒泡排序、插入排序和選擇排序的空間復(fù)雜度為O（1），合并排序?yàn)镺（n）。