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

請教，快速排序的空間復雜度？

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

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因為這是一個Java問題，所以這是典型的TOPK問題。首先取前100個數(shù)字構建一個最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時調整堆。堆中最后100個元素就是結果?？臻g復雜度為k，時間復雜度為nlogk

選擇排序和冒泡排序的空間復雜度和時間復雜度是多少？

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

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

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

堆排序可以通過簡單的交換將數(shù)據(jù)安排到適當?shù)亩阎校瑹o需輔助空間。堆和原始數(shù)據(jù)是集成的。創(chuàng)建：heap | unprocessed data sort:heap | sorted data堆的大小和未處理/排序的數(shù)據(jù)加起來等于原始數(shù)據(jù)的大小。