數(shù)據(jù)結(jié)構(gòu)名詞解釋-資料下載頁(yè)
2025-06-25 07:19本頁(yè)面
【正文】 內(nèi)插入排序, 直到增量為1時(shí),進(jìn)行最后一次排序止。指的是待排序記錄存放在計(jì)算機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程；指的是待排序記錄的數(shù)量很大,以致內(nèi)存一次不能容納全部記錄,在排序過(guò)程中對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。假設(shè)Ki=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri領(lǐng)先于Rj(即i＜j)。若在排序后的序列中Rj 領(lǐng)先于Ri ,則稱所用的排序方法是不穩(wěn)定的。假設(shè)Ki=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri領(lǐng)先于Rj(即i＜j)。若在排序后的序列中Ri仍領(lǐng)先于Rj,則稱所用的排序方法是穩(wěn)定的第1遍,將初始文件中的記錄R1看作有序子文件,將R2插入這個(gè)子文件中。若R2的關(guān)鍵字小于R1的關(guān)鍵字,則R2插在R1的前面,否則R2插在R1的后面。第2遍,將R3插入前面的兩個(gè)記錄的有序子文件中,得到3個(gè)記錄的有序子文件。依此類推,繼續(xù)進(jìn)行下去,直到將Rn插入到前面的n1個(gè)記錄的有序子文件中,最后得到n個(gè)記錄的有序文件。 氣泡排序的過(guò)程很簡(jiǎn)單。從第一記錄開始,相鄰的兩個(gè)記錄關(guān)鍵字進(jìn)行比較,若順序不對(duì),立即交換,直至N1個(gè)與第N個(gè)比較為止。得到一個(gè)最大(或最小)的關(guān)鍵字記錄的結(jié)果位置。選擇排序是每一趟在ni+1(i= 1,2,3…n1)個(gè)記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。其中最簡(jiǎn)單的是簡(jiǎn)單選擇排序快速排序的基本思想是把當(dāng)前待排序的記錄,存放到整個(gè)表排好序后,它應(yīng)當(dāng)在的最終位置上。將原來(lái)的待排序表分割成兩部分,其中一部分表中的關(guān)鍵字均比另一部分表中的關(guān)鍵字小。然后,分別對(duì)兩部分表用同樣的方式進(jìn)行排序,直到整個(gè)表排好序。首先將根結(jié)點(diǎn)的記錄與當(dāng)前樹中具有最大序號(hào)的記錄交換,把交換后具有最大序號(hào)的記錄輸出,得到一個(gè)排序的結(jié)果。這時(shí)的樹不再是堆樹,排序暫時(shí)停止。然后,必須把樹重新調(diào)整成堆樹,再重復(fù)上述過(guò)程,直到所有記錄都排好序。歸并排序是把兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。把含有N 個(gè)記錄的無(wú)序表當(dāng)成N 個(gè)有序的子表,每個(gè)子表的的長(zhǎng)度為1,然后,利用兩兩歸并,得到n/2個(gè)長(zhǎng)度為2或1的有序子表。再兩兩歸并直到得到長(zhǎng)度為N 的一個(gè)有序表。對(duì)于一個(gè)有向圖,每?jī)蓚€(gè)頂點(diǎn)之間都有路徑,稱該圖為強(qiáng)連通圖。對(duì)于一個(gè)無(wú)向圖,其極大連通子圖叫做該圖一個(gè)連通分量。基數(shù)排序是借助“分配”和“收集”兩種操作對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種內(nèi)排序方法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1