17 在所有排序方法中,關鍵字比較的次數與記錄的初始排列次序無關的是選擇排序。為什麼呢

時間 2021-07-12 17:31:24

1樓:格子裡兮

原因:一、直接插入排序很明顯,在完全有序的情況下每個元素只需要與他左邊的元素比較一次就可以確定他最終的位置;

二、折半插入排序,比較次數是固定的,與初始排序無關;

三、快速排序,初始排序不影響每次劃分時的比較次數,都要比較n次,但是初始排序會影響劃分次數,所以會影響總的比較次數;

四、歸併排序在歸併的時候,如果右路最小值比左路最大值還大,那麼只需要比較n次,如果右路每個元素分別比左路對應位置的元素大,那麼需要比較2*n-1次,所以與初始排序有關。

歸併排序

假設二路歸併

12  34   2次

2<4  2<3  2次   不用再繼續  共4次

1 2 3 4 有序

2314

23  14  2次

3<4  3>1  2次   再用2比較

2>1       1次   插入

1 2 3 4 有序  共5次

可見歸併排序的比較次數就不固定,隨著初始狀態不同而不同。

2樓:倒黴熊

每一趟從待排序的資料元素中選出最小(或最大)的一個元素,順序放在已排好序的數列的最後,直到全部待排序的資料元素排完。

可以看到,每次都是遍歷一遍剩下要排序的部分,找出其最大值或最小值。所以。。。。。

3樓:匿名使用者

因為選擇排序每趟選擇的比較次數是固定的,不會因為順序不一樣而比較次數不一樣。比如(1,2,3)和(3,2,1)這兩個序列次序不同,但是在第一趟選擇排序中選出最小的值1同樣進行2次比較,第二趟選出第二小的值2同樣進行1次比較……也就是說,……

4樓:匿名使用者

答案是直接選擇排序!因為不管初始排列次序是相對正序還是相對亂序,選擇排序對關鍵字的比較次數都是相同的!因為它每一次都要選出關鍵字中最小的!

5樓:匿名使用者

冒泡也與初始排序次序有關,因為一般在實現氣泡排序時,都採用改進演算法,設定一個標誌位flag,將其初始值設定為非0,表示被排序的表示是一個無序的表,每一次排序開始前設定flag值為0,在進行資料交換時,修改flag為非0。在新一輪排序開始時,檢查此標誌,若此標誌為0,表示上一次沒有做過交換資料,則結束排序;否則進行排序。所以,當記錄序列的初始狀態為"正序",則氣泡排序過程只需進行一趟排序即可

6樓:匿名使用者

你趕緊去找一本書先看一下,就知道怎麼回事了,很簡單的!

在所有排序方法中,關鍵字比較的次數與記錄的初始排列次序無關的 20

7樓:

a:希爾排序是按不同步長對元素進行插入排序,無序情況下步長大,在開始第一趟排序後,變得稍微有序,步長變短,直至排序成功,所以說有序比無序情況下的第一趟排序的初始步長小,排序趟數也少,所以比較次數少。

b:氣泡排序是將序列中值大的壓到序列頂端,就像冒泡一樣一個一個的將值大的冒出來。假設n個值,一趟排序後會將最大的排到位置n,然後對前n-1位進行第二趟排序,直至某一次排序中序列中的值是遞增的,排序結束。

所以說有序情況和無序情況儘管每一趟關鍵字比較次數相同,但有序情況下排序趟數要少,所以總比較次數也要小。

c:插入排序簡單,就是將記錄插入已經排好序的序列中。例如1至n為一個序列,把1看作一個有序序列a,將2至n各個值插入a中,必須要n-1趟操作(2與1比較,2大於1,序列變為1.

2,3與1.2比較,3大於2,序列變為1.2.

3,直至序列變為1.2.3.....

n).如果插入的序列2至n是有序的,則每趟操作的時候只需比較一次就可以得到有序序列。所以說插入排序最好條件下時(即有序條件下),關鍵字比較n-1次。

d:選擇排序,序列為1至n,第一趟是把2到n依次與1比較,把最小的放在位置1,第二趟是把3至n依次與2比較,把最小的放在位置2,迴圈以下操作,直至n-1趟後結束。它的次數是固定的,中途假如a與a+1至n比較後序列不變,而且有序,但後續比較還是要進行。

比如說1至n的序列關鍵字值就是1至n,它用插入排序是最簡單的,只需n-1次比較。但在選擇排序中,它會依次比較,不會因為已經有序停止,而是會依次的進行n-1趟操作。

8樓:匿名使用者

氣泡排序有一種優化方法,就是在每趟冒泡的時候都檢測這次是否有交換元素的順序,如果沒有交換就說明序列是排好序的,下次就不用再冒泡了!所以和初始序列是有關係的

9樓:匿名使用者

氣泡排序會在每一趟排序的for 迴圈首句放置一個flag初始值為false;如果發生了交換,就讓flag=true,如果一趟結束之後flag 沒有變化,就說明表已經有序。排序結束。

10樓:亂取了這個名字

選擇排序無論它的初始順序是怎樣,它的比較次數都是n(n-1)/2.因為它是第一個數與後面的所有數進行比較,找出最值與第一個數進行互換,然後第二位數與後面所有數進行比較…因為它是數和其他數進行比較,比較期間不會判斷陣列的順序,所以在程式結束前,它不會因為陣列的順序而停止。

11樓:原來的源

我認為選d。插入排序(此處包括直接插入排序、折半插入排序、希爾排序)中,每一趟排序時,關鍵字比較次數和初始序列(是否有序)有關;氣泡排序也有關。而簡單選擇排序中,所有趟數下來關鍵字總是總共比較n(n-1)/2次,每一趟關鍵字比較次數也是固定的。

12樓:1026呵呵

折半插入排序中記錄比較次數與初始序列無關。每躺排序尋找位置時,折半次數一定

c中的var關鍵字和object關鍵字的區別,順便介紹下object的使用方法以及好處

走路的大樂樂 到這裡看看吧 c 中的object型別到底是什麼概念,如何使用,有什麼意義? var關鍵字是c 3.0開始新增的特性,稱為推斷型別 可以賦予區域性變數推斷 型別 var 而不是顯式型別。var 關鍵字指示編譯器根據初始化語句右側的表示式推斷變數的型別。推斷型別可以是內建型別 匿名型別 ...

如何在查詢pdf檔案中關鍵字

很多辦公軟體都有查詢這個功能,其使用方法都是差不多的,當然pdf也不例外,不過還是以該軟體為主,下面推薦以下方法,希望能幫到你解決問題 步驟二 然後選擇 開啟 瀏覽 開啟一個我們需要編輯的pdf文件。步驟三 在軟體介面的右上方,有 查詢 和 高階查詢 功能。步驟四 選擇 查詢功能 在頁面右上方會跳轉...

c 中所有關鍵字的發音和意思,要詳細

asm 1 auto bad cast bad typeid bool break case catch char class const const cast continue default delete dodouble dynamic cast else enum except explic...