為什麼快速排序是不穩定的排序法,為什麼快速排序是乙個不穩定的排序法?

2021-03-11 19:51:59 字數 6805 閱讀 8760

1樓:小萍笑笑

在此先簡單闡述

復一下快

制速排序的具體做法:設定需要排序序bai列du第乙個數

字為關鍵字p(也叫樞zhi軸),同dao時設定兩個指標high和low,初始狀態時,low指向p,high指向序列中最後乙個數;

首先從high所指位置起向前找第乙個小於關鍵字p的數字,並與p相互交換位置;然後從low所指位置起向後搜尋,找到第乙個大於p的數字,並與p相互交換位置,重複這兩部直至low=high為止,這就是一趟快速排序完成;但是到此不一定就完成了快速排序的排序工作,第一趟排序完成只是將序列中的數字分成三部分,p在中間部分,p之前的數字肯定比p小,p後面的那些數字都是比p大的,在分別對前後兩部分進行快速排序即可。

所謂排序的穩定性,就是指在排序過程中,在對a關鍵字排序後會不會改變其他關鍵字的順序。

自己都可以試試,在比較有相同關鍵字序列的情況下,穩定的排序會將較早出現的元素排在前面,而不會是後面。

比如:對(49,38,49,20,97,76)排序,就是不穩定排序

我們也是剛學了這個東西,希望我的理解和解釋能幫你解決疑惑

2樓:泰凡嬴巨集邈

一組資料用快速排序究竟用多少次能排完?這是不確定的。在最壞的情況下比其它的排序演算法還要慢,當然這種機率出現的情況很少。

因此說它不穩定,不是說它排序的結果不穩定,而是時間複雜度不穩定。

3樓:鞏博革小蕾

不穩定只是說在排序沒有完成之前(假設說:降序排列)會暫時的出現小的排在前面的情況

沒有排完就中斷,不能保證一部分是有序的,所以稱為不穩定大學教科書:

資料結構裡面寫的,不信去查

4樓:匿名使用者

用aaaaab舉例(a>b),以b為標準,第乙個a到b後面去了,不穩定了

5樓:叔_你真帥

以ai與aj為例子

copy

快速排序有兩個方向,左邊的i下標一直往右走,當a[i] <= a[center_index],

其中center_index是中

樞元素的陣列下標,一般取為陣列第0個元素。而右邊的

j下標一直往左走,當a[j] > a[center_index]。如果i和j都走不動了,

i <= j, 交換a[i]和a[j],重複上面的過程,直到i>j。

交換a[j]和a[center_index],完成一趟快速排序。在中樞元素和a[j]交換的

時候,很有可能把前面的元素的穩定性打亂,比如序列5 3 3 4 3 8 9 10 11,

現在中樞元素5和3(第5個元素,下標從1開始計)交換就會把元素3的穩定性打亂

,所以快速排序是乙個不穩定的排序演算法,不穩定發生在中樞元素和a[j]交換的時刻。

在快速排序、堆排序、歸併排序中,什麼排序是穩定的?

6樓:沉珂側畔

歸併排序是穩定的「快速排序和堆排序都不穩定.不穩定:就是大小相同的兩個數,經過排序後,最終位置與初始位置交換了。

快速排序:

27 23 27 3

以第乙個27作為pivot中心點,則27與後面那個3交換,形成

3 23 27 27,排序經過一次結束,但最後那個27在排序之初先於初始位置3那個27,所以不穩定。

堆排序:

比如:3 27 36 27,

如果堆頂3先輸出,則,第三層的27(最後乙個27)跑到堆頂,然後堆穩定,繼續輸出堆頂,是剛才那個27,這樣說明後面的27先於第二個位置的27輸出,不穩定。」

「2 歸併排序(mergesort)

歸併排序先分解要排序的序列,從1分成2,2分成4,依次分解,當分解到只有1個一組的時候,就可以排序這些分組,然後依次合併回原來的序列中,這樣就可以排序所有資料。合併排序比堆排序稍微快一點,但是需要比堆排序多一倍的記憶體空間,因為它需要乙個額外的陣列。」

以ai與aj為例子

快速排序有兩個方向,左邊的i下標一直往右走,當a[i] <= a[center_index],其中center_index樞元素的陣列下標,一般取為陣列第0個元素。而右邊的j下標一直往左走,當a[j] > a[center_indexij都走不動了,i <= j, 交換a[i]和a[j],重複上面的過程,直到i>j。

交換a[j]和a[center_index],完成一趟快速排序。在中樞元素和a[j]交換的時候,很有可能把前面的元素的穩定性打亂,比如序列5 3 3 4 3 8 9 10 11,現在中樞元素5和3(第5個元素,下標從1開始計)交換就會把元素3的穩定性打亂,所以快速排序是乙個不穩定的排序演算法,不穩定發生在中樞元素和a[j]交換的時刻。

在快速排序、堆排序、歸併排序中,什麼排序是穩定的?

7樓:匿名使用者

歸併排序是穩定的排序演算法。

歸併排序的穩定性分析:

歸併排序是把序列遞迴地分成短序列,遞迴出口是短序列只有1個元素或者2個序列,然後把各個有序的段序列合併成乙個有序的長序列,不斷合併直到原序列全部排好序。

可以發現,在1個或2個元素時,1個元素不會交換,2個元素如果大小相等,沒有外部干擾,將不會破壞穩定性。

那麼,在短的有序序列合併的過程中,穩定性是沒有受到破壞的,合併過程中如果兩個當前元素相等時,把處在前面的序列的元素儲存在結果序列的前面,這樣就保證了穩定性。所以,歸併排序也是穩定的排序演算法。

8樓:匿名使用者

歸併排序是穩定的

「快速排序和堆排序都不穩定

不穩定:就是大小相同的兩個數,經過排序後,最終位置與初始位置交換了。

快速排序:

27 23 27 3

以第乙個27作為pivot中心點,則27與後面那個3交換,形成

3 23 27 27,排序經過一次結束,但最後那個27在排序之初先於初始位置3那個27,所以不穩定。

堆排序:

比如:3 27 36 27,

如果堆頂3先輸出,則,第三層的27(最後乙個27)跑到堆頂,然後堆穩定,繼續輸出堆頂,是剛才那個27,這樣說明後面的27先於第二個位置的27輸出,不穩定。」

「2 歸併排序(mergesort)

歸併排序先分解要排序的序列,從1分成2,2分成4,依次分解,當分解到只有1個一組的時候,就可以排序這些分組,然後依次合併回原來的序列中,這樣就可以排序所有資料。合併排序比堆排序稍微快一點,但是需要比堆排序多一倍的記憶體空間,因為它需要乙個額外的陣列。」

參考資料

9樓:卟懂

在常見排序中,只有希爾排序、堆排序、快速排序是不穩定的

10樓:匿名使用者

歸併排序(n log n);穩定

堆排序 (n log n);不穩定

快排(n log n)不穩定

11樓:傅邃出好

是歸併排序,我剛剛也做這個題目。

因為堆排序時間複雜度為n*logn,空間複雜度為1,是不穩定排序,適合較多情況;

而歸併排序的時間複雜度為n*logn,空間複雜度為n,是穩定排序。

快速排序的時間複雜度為n,空間複雜度最好的情況是logn,最壞的情況是n^2,是不穩定的排序方法。(書本原話)。

資料結構中排序的方法中穩定的有那些,不穩定的有那些(如快速排序等)

12樓:黃家三爺爺

穩定的氣泡排序(bubble sort) — o(n2)   雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2)   插入排序 (insertion sort)— o(n2)   桶排序 (bucket sort)— o(n); 需要 o(k) 額外 記憶體   計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體   歸併排序 (merge sort)— o(n log n); 需要 o(n) 額外記憶體   原地歸併排序 — o(n2)   二叉樹排序 (binary tree sort) — o(n log n); 需要 o(n) 額外記憶體   鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體   基數排序 (radix sort)— o(n·k); 需要 o(n) 額外記憶體   gnome sort — o(n2)   library sort — o(n log n) with high probability, 需要 (1+ε)n 額外記憶體

不穩定選擇排序 (selection sort)— o(n2)   希爾排序 (shell sort)— o(n log n) 如果使用最佳的現在版本   ***b sort — o(n log n)   堆排序 (heapsort)— o(n log n)   **oothsort — o(n log n)   快速排序 (quicksort)— o(n log n) 期望時間, o(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序   introsort — o(n log n)   patience sorting — o(n log n + k) 最外情況時間, 需要 額外的 o(n + k) 空間, 也需要找到最長的遞增子串行(longest increasing subsequence)

在快速排序, 堆排序,歸併排序中 哪個是最穩定的排序方法? 20

13樓:匿名使用者

1 快速排序(quicksort)

快速排序是乙個就地排序,分而治之,大規模遞迴的演算法。

從本質上來說,它是歸併排序的就地版本。快速排序可以由下面四步組成。

(1) 如果不多於1個資料,直接返回。

(2) 一般選擇序列最左邊的值作為支點資料。

(3) 將序列分成2部分,一部分都大於支點資料,另外一部分都小於支點資料。

(4) 對兩邊利用遞迴排序數列。

快速排序比大部分排序演算法都要快。儘管我們可以在某些特殊的情況下寫出比快速排序快的演算法,但是就通常情況而言,沒有比它更快的了。快速排序是遞迴的,對於記憶體非常有限的機器來說,它不是乙個好的選擇。

2 歸併排序(mergesort)

歸併排序先分解要排序的序列,從1分成2,2分成4,依次分解,當分解到只有1個一組的時候,就可以排序這些分組,然後依次合併回原來的序列中,這樣就可以排序所有資料。合併排序比堆排序稍微快一點,但是需要比堆排序多一倍的記憶體空間,因為它需要乙個額外的陣列。

3 堆排序(heapsort)

堆排序適合於資料量非常大的場合(百萬資料)。

堆排序不需要大量的遞迴或者多維的暫存陣列。這對於資料量非常巨大的序列是合適的。比如超過數百萬條記錄,因為快速排序,歸併排序都使用遞迴來設計演算法,在資料量非常大的時候,可能會發生堆疊溢位錯誤。

堆排序會將所有的資料建成乙個堆,最大的資料在堆頂,然後將堆頂資料和序列的最後乙個資料交換。接下來再次重建堆,交換資料,依次下去,就可以排序所有的資料。

4 shell排序(shellsort)

shell排序通過將資料分成不同的組,先對每一組進行排序,然後再對所有的元素進行一次插入排序,以減少資料交換和移動的次數。平均效率是o(nlogn)。其中分組的合理性會對演算法產生重要的影響。

現在多用d.e.knuth的分組方法。

shell排序比氣泡排序快5倍,比插入排序大致快2倍。shell排序比起quicksort,mergesort,heapsort慢很多。但是它相對比較簡單,它適合於資料量在5000以下並且速度並不是特別重要的場合。

它對於資料量較小的數列重複排序是非常好的。

5 插入排序(insertsort)

插入排序通過把序列中的值插入乙個已經排序好的序列中,直到該序列的結束。插入排序是對氣泡排序的改進。它比氣泡排序快2倍。

一般不用在資料大於1000的場合下使用插入排序,或者重複排序超過200資料項的序列。

6 氣泡排序(bubblesort)

氣泡排序是最慢的排序演算法。在實際運用中它是效率最低的演算法。它通過一趟又一趟地比較陣列中的每乙個元素,使較大的資料下沉,較小的資料上公升。它是o(n^2)的演算法。

7 交換排序(exchangesort)和選擇排序(selectsort)

這兩種排序方法都是交換方法的排序演算法,效率都是 o(n2)。在實際應用中處於和氣泡排序基本相同的地位。它們只是排序演算法發展的初級階段,在實際中使用較少。

8 基數排序(radixsort)

基數排序和通常的排序演算法並不走同樣的路線。它是一種比較新穎的演算法,但是它只能用於整數的排序,如果我們要把同樣的辦法運用到浮點數上,我們必須了解浮點數的儲存格式,並通過特殊的方式將浮點數對映到整數上,然後再對映回去,這是非常麻煩的事情,因此,它的使用同樣也不多。而且,最重要的是,這樣演算法也需要較多的儲存空間。

9 總結

下面是乙個總的**,大致總結了我們常見的所有的排序演算法的特點。

排序法 平均時間 最差情形 穩定度 額外空間 備註

冒泡 o(n2) o(n2) 穩定 o(1) n小時較好

交換 o(n2) o(n2) 不穩定 o(1) n小時較好

選擇 o(n2) o(n2) 不穩定 o(1) n小時較好

插入 o(n2) o(n2) 穩定 o(1) 大部分已排序時較好

基數 o(logrb) o(logrb) 穩定 o(n)

b是真數(0-9),

r是基數(個十百)

shell o(nlogn) o(ns) 1

快速 o(nlogn) o(n2) 不穩定 o(nlogn) n大時較好

歸併 o(nlogn) o(nlogn) 穩定 o(1) n大時較好

堆 o(nlogn) o(nlogn) 不穩定 o(1) n大時較好

為什麼打雷閃電的時候網路這麼不穩定

閃電其實是高壓電流,它能發生電磁感應干涉網線裡的電流訊號 希望採納 打雷閃電用wifi會有影響嗎,會不會燒壞?打雷閃電用wifi會有影響,可能導致貓與路由器被燒壞,1 打雷閃電期間,會有較強的電磁訊號,影響室內wifi訊號,2 打雷閃電時,可能引起家庭電流的猛然變化,如電壓瞬間公升高等,從而燒壞路由...

穩壓器輸入電壓穩定為什麼輸出的電壓不穩定

你用的可能是220v的電bai源du 穩壓器吧,用這個主要是電壓太zhi低或電壓起dao伏較大的版地方,它內部是靠電子權線路檢測輸出電壓的高低 也就是負載功率 而自動調節的,調節的具體元件是繼電器,就象汽車開了轉向燈後聽到的那種,裡面有好幾個,通過它的吸合和釋放來達到一小部分電壓的接入與否來大體穩定...

什麼是穩定流動和不穩定流動,在實驗中如何控制

流體在管道內或bai在窯爐系 du統中流動時,如果任一zhi截面上的流動狀dao 況 流速 壓強 重度 成分等專 都不屬隨時間而改變,這種流動就稱為穩定流動 反之,流動各量隨著時間而改變,就稱為不穩定流動。實際上流體 如氣體,重油等 在管道內或窯爐系統中流動時,只要波動不太大,都可以視為穩定流動。什...