將哨兵放在R[n]中
被排序的記錄放在R[
n
]中
重寫直接插入排序算法
以單鏈表作為存儲結構實現直接插入排序算法
設計一算法使得在盡可能少的時間內重排數組將所有取負值的關鍵字放在所有取非負值的關鍵字之前請分析算法的時間復雜度
* 寫一個雙向冒泡排序的算法即在排序過程中交替改變掃描方向
下面是一個自上往下掃描的冒泡排序的偽代碼算法它采用lastExchange 來記錄每趟掃描中進行交換的最後一個元素的位置並以它作為下一趟排序循環終止的控制值請仿照它寫一個自下往上掃描的冒泡排序算法
void BubbleSort(int A[]int n)
//不妨設A[n]是整型向量
int lastExchangeji=n;
while (i>)
lastExchange=;
for(j=;j<i;j++)//從上往下掃描A[i]
if(A[j+]<A[j]){
交換A[j]和A[j+];
lastExchange=j;
}
i=lastExchange;//將i置為最後交換的位置
}//endwhile
}//BubbleSort
改寫快速排序算法要求采用三者取中的方式選擇劃分的基准記錄若當前被排序的區間長度小於等於時無須劃分而是直接采用直接插入方式對其排序
對給定的j(≤j≤n )要求在無序的記錄區R[n]中找到按關鍵字自小到大排在第j個位置上的記錄(即在無序集合中找到第j個最小元)試利用快速排序的劃分思想編寫算法實現上述的查找操作
`以單鏈表為存儲結構寫一個直接選擇排序算法
寫一個heapInsert(Rkey)算法將關鍵字插入到堆R中去並保證插入R後仍是堆提示應為堆R增加一個長度屬性描述(即改寫本章定義的SeqList類型描述使其含有長度域)將key先插入R中已有元素的尾部(即原堆的長度加的位置插入後堆的長度加)然後從下往上調整使插入的關鍵字滿足性質請分析算法的時間
寫一個建堆算法從空堆開始依次讀入元素調用上題中堆插入算法將其插入堆中
寫一個堆刪除算法HeapDelete(Ri)將R[i]從堆中刪去並分析算法時間提示先將R[i]和堆中最後一個元素交換並將堆長度減然後從位置i開始向下調整使其滿足堆性質
已知兩個單鏈表中的元素遞增有序試寫一算法將這兩個有序表歸並成一個遞增有序的單鏈表算法應利用原有的鏈表結點空間
設向量A[n]中存有n個互不相同的整數且每個元素的值均在到n之間試寫一時間為O(n)的算法將向量A排序結果可輸出到另一個向量B[n]中
* 寫一組英文單詞按字典序排列的基數排序算法設單詞均由大寫字母構成最長的單詞有d個字母提示所有長度不足d個字母的單詞都在尾處補足空格排序時設置個箱子分別與空格ABZ對應
From:http://tw.wingwit.com/Article/program/sjjg/201311/23622.html
