首頁>Program>source

在分析QS時,每个人总是指"几乎排序"的最壞情况.自然輸入何時会發生這種情况?

我想出的唯一示例是重新索引。

最新回復
  • 5月前
    1 #

    我认為人们對基於分區的排序演算法Quicksort和" qsort"各種庫實現感到困惑。

    我更類似Quicksort演算法具有可插拔的枢轴選擇演算法,這對於分析其行為非常重要。

    如果始终選擇第一个元素作為枢轴,則最壞的情况是已经排序的列表.通常,很有可能陣列已经/几乎已排序,因此此實現的效果很差。

    類似地,出於同樣的原因,選擇最後一个元素作為枢轴也是很糟糕的。

    某些實現通過選擇中間元素作為枢纽来尝試避免此問题.這在已经/几乎已排序的陣列上表現不佳,但是仍然可以構造一个可以利用這種可預測的資料透视選擇並使其在二次時間內執行的輸入。

    因此,您將获得隨機的枢轴選擇演算法,但是即使這樣也不能保證 O(N log N)

    因此,開發了其他演算法,這些演算法將在選擇枢轴之前使用序列中的某些資訊.当然,您可以掃描整个序列並找到中位數,然後將其用作支點.這保證了 O(N log N) ,但實践中当然会慢一些。

    因此,有些弯角被砍掉了,人们設計了3位中值演算法.当然,後来甚至被所謂的3分中值"杀手"所利用。

    因此,人们做出了更多尝試以提供更多"智慧"資料透视選擇演算法,以保證 O(N log N) 渐近行為仍然足够快,可以付诸實践,並取得不同程度的成功。

    因此,實際上,除非指定Quicksort的特定實現,否則最壞情况何時發生的問题是不確定的.如果使用所謂的中位數中位數枢轴選擇演算法,則不会出現二次最壞情况。

    但是,大多數庫的實現都有可能丧失 O(N log N) 確保平均情况下更快的排序.某些真正古老的實現使用第一个元素作為枢轴,現在人们已经很好地理解它是差的,不再被廣泛采用。

  • 5月前
    2 #

    我相信快速排序的最壞情况取決於 在每个步骤中選擇枢轴元素.如果資料透视表可能是列表中的最小元素或最大元素(例如,已排序列表的第一个或最後一个元素),則Quicksort的效能最差。

    例如 您選擇列表的中間元素,已经排序的列表就不会出現最壞情况的執行時間。

    因此,如果您怀疑您的方案可能是快速排序的不良情况,則只需更改枢轴元素的選擇即可使快速排序更好地執行。

    註意:我知道,這並没有提供更多關於在最壞情况下进行快速排序的真實案例.這樣的示例取決於您使用的實現。

  • 5月前
    3 #

    實際的問题是:"什麼時候(自然排序)這種情况(几乎排序)?"。

    尽管所有答案都涉及"匯致最壞情况效能的原因",但没有一个涵盖"匯致資料满足最壞情况效能情况的原因"。

    所以,要迴答實際問题

      Programmer error: Basically you land up sorting a list twice. Typically this happens because a list is sorted one place in code. And later in another piece of code you know you need the list to be sorted, so you sort it again.

      Using almost-chronological data: You have data that is generally received in chronological order, but occasionally some elements are out of position. (Consider a multi-threaded environment adding time-stamped elements to a list. Race conditions can cause elements to be added in a different order to which they were time-stamped.) In this situation, if you need sorted data, you must re-sort. Because the order of the data is not guaranteed.

      Adding items to a list: If you have a sorted list and simply append some items (i.e. without using binary insertion). You would need to re-sort an almost-sorted list.

      Data from an external source: If you receive data from an external source, there may be no guarantee that it's sorted. So you sort it yourself. However, if the external source is sorted, you will be re-sorting the data.

      Natural ordering: This is similar to the chronoloigcal data. Basically, the natural order of the data you receive may be sorted. Consider an insurance company adding car registrations. If the authority assiging car registrations does so in a predictable order, newer cars are likelybut not guaranteedto have higher registration numbers. Since you're not guaranteed it's sorted - you have to re-sort.

      Interleaved data: If you receive data from multiple sorted sources with overlapping keys, you could get keys resembling the following: 1 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18. Even though half the elements are out-of-sequence with its neighbour, the list is "almost sorted". Certainly using QuickSort that pivots on the first element would exhibit O(n^2) 效能。

      結論

      因此,在上述所有情况下,查詢几乎排序的資料實際上非常容易.這就是為什麼最好避免使用以第一个元素為中心的QuickSort的原因. polygene提供了一些有趣的資訊,說明了其他關键性考虑因素。

      As a side-note: One of the usually worst performing sorting algorithms, actually does quite well with "almost-sorted" data. In the interleaved data above, bubble-sort requires only 9 swap operations. It's performance would actually be O(n)

  • 5月前
    4 #

    来自Quicksort

    for quicksort, "worst case" corresponds to already sorted

    具有相同編號的所有專案的列表已经已排序

  • 5月前
    5 #

    最差情况的快速排序:

    陣列的所有元素都相同

    陣列已按相同順序排序

    陣列已按相反順序排序。

相似問題

  • linux:卸載从源代碼構建的python吗?
  • c#:實體框架/ Linq to SQL:跳過並接受