在所有排序方法中,關鍵字比較的次數與記錄的初始排列次序無關的是折半插入排序。
原因:
一、直接插入排序很明顯,在完全有序的情況下每個元素只需要與他左邊的元素比較一次就可以確定他最終的位置;
二、折半插入排序,比較次數是固定的,與初始排序無關;
三、快速排序,初始排序不影響每次劃分時的比較次數,都要比較n次,但是初始排序會影響劃分次數,所以會影響總的比較次數;
四、歸併排序在歸併的時候,如果右路最小值比左路最大值還大,那麼只需要比較n次,如果右路每個元素分別比左路對應位置的元素大,那麼需要比較2*n-1次,所以與初始排序有關。
歸併排序
假設二路歸併
1234
12 34 2次
2
1 2 3 4 有序
2314
23 14 2次
31 2次 再用2比較
2>1 1次 插入
1 2 3 4 有序 共5次
可見歸併排序的比較次數就不固定,隨著初始狀態不同而不同。
擴充套件資料:
一個排序演算法是穩定的,就是當有兩個相等記錄的關鍵字R和S,且在原本的列表中R出現在S之前,在排序過的列表中R也將會是在S之前。
當相等的元素是無法分辨的,比如像是整數,穩定度並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。
(4,1)(3,1)(3,7)(5,6)在這個狀況下,有可能產生兩種不同的結果,一個是依照相等的鍵值維持相對的次序,而另外一個則沒有:
(3,1)(3,7)(4,1)(5,6) (維持次序)
(3,7)(3,1)(4,1)(5,6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。
作這件事情的一個方式是人工擴充鍵值的比較,如此在其他方面相同鍵值的兩個物件間之比較,就會被決定使用在原先資料次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。
在所有排序方法中,關鍵字比較的次數與記錄的初始排列次序無關的是折半插入排序。
原因:
一、直接插入排序很明顯,在完全有序的情況下每個元素只需要與他左邊的元素比較一次就可以確定他最終的位置;
二、折半插入排序,比較次數是固定的,與初始排序無關;
三、快速排序,初始排序不影響每次劃分時的比較次數,都要比較n次,但是初始排序會影響劃分次數,所以會影響總的比較次數;
四、歸併排序在歸併的時候,如果右路最小值比左路最大值還大,那麼只需要比較n次,如果右路每個元素分別比左路對應位置的元素大,那麼需要比較2*n-1次,所以與初始排序有關。
歸併排序
假設二路歸併
1234
12 34 2次
2
1 2 3 4 有序
2314
23 14 2次
31 2次 再用2比較
2>1 1次 插入
1 2 3 4 有序 共5次
可見歸併排序的比較次數就不固定,隨著初始狀態不同而不同。
擴充套件資料:
一個排序演算法是穩定的,就是當有兩個相等記錄的關鍵字R和S,且在原本的列表中R出現在S之前,在排序過的列表中R也將會是在S之前。
當相等的元素是無法分辨的,比如像是整數,穩定度並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。
(4,1)(3,1)(3,7)(5,6)在這個狀況下,有可能產生兩種不同的結果,一個是依照相等的鍵值維持相對的次序,而另外一個則沒有:
(3,1)(3,7)(4,1)(5,6) (維持次序)
(3,7)(3,1)(4,1)(5,6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實現為穩定。
作這件事情的一個方式是人工擴充鍵值的比較,如此在其他方面相同鍵值的兩個物件間之比較,就會被決定使用在原先資料次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。