<li id="368mr"></li>

問答題

【簡(jiǎn)答題】試設(shè)計(jì)一個(gè)算法，使得在O（n）的時(shí)間內(nèi)重排待排序表（用數(shù)組表示）中的數(shù)據(jù)對(duì)象，將所有取負(fù)值的排序碼排在所有取正值（非負(fù)值）的排序碼之前。（在寫算法之前首先用C++類定義數(shù)據(jù)表的結(jié)構(gòu)）。

答案：

你可能感興趣的試題

【簡(jiǎn)答題】
有一種簡(jiǎn)單的排序算法，叫做計(jì)數(shù)排序（count Sorting）。這種排序算法對(duì)一個(gè)待排序的表（用數(shù)組表示）進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為 c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為 c。
（1）給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義；
（2）使用C++語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法。

答案：

【計(jì)算題】
下面的程序是一個(gè)的兩路歸并算法merge，只需要一個(gè)附加存儲(chǔ)。設(shè)算法中參加歸并的兩個(gè)歸并段是A[left]～A[mid]和A[mid]～A[right]，歸并后結(jié)果歸并段放在原地。

若A = { 12， 28， 35， 42， 67， 9， 31， 70 }， left = 0， mid = 4， right = 7。寫出每次執(zhí)行算法最外層循環(huán)后數(shù)組的變化，并給出每次執(zhí)行算法最外層循環(huán)時(shí)的數(shù)據(jù)記錄移動(dòng)次數(shù)。

答案：