第8章排序(算法設計)習題練習答案

將哨兵放在R[n]中被排序的記錄放在R[n]中重寫直接插入排序算法
解
    重寫的算法如下
  void InsertSort(SeqList R)
　　{//對順序表中記錄R[n]按遞增序進行插入排序
　　　int ij;
　　　for(i=n;i>=;i) //在有序區中依次插入R[n]R[]
　　　　if(R[i]key>R[i+]key) //若不是這樣則R[i]原位不動
　　　　　{ 
　　　　　　R[n]=R[i];j=i+; //R[n]是哨兵
　　　　　　do{ //從左向右在有序區中查找插入位置
　　　　　　　　R[j]=R[j]; //將關鍵字小於R[i]key的記錄向右移
　　　　　　　　j++;
　　　　　　　}while(R[j]key<R[n]key]);
　　　　　　R[j]=R[n]; //將R[i]插入到正確位置上
　　　　　}//endif
　　}//InsertSort

以單鏈表作為存儲結構實現直接插入排序算法 
解
　#define int KeyType //定義KeyType 為int型
　typedef struct node{
　　　KeyType key; //關鍵字域
　　　OtherInfoType info; //其它信息域
　　　struct node * next; //鏈表中指針域
　　}RecNode; //記錄結點類型
　typedef RecNode * LinkList ; //單鏈表用LinkList表示

　void InsertSort(LinkList head)
　　{//鏈式存儲結構的直接插入排序算法head是帶頭結點的單鏈表
　　　RecNode *p*q*s; 
　　　if ((head>next)&&(head>next>next))//當表中含有結點數大於
　　　　{
　　　　　p=head>next>next;//p指向第二個節點
　　　　　head>next=NULL;
　　　　　q=head;//指向插入位置的前驅節點
　　　　　while(p)&&(q>next)&&(p>key<q>next>key)
　　　　　　q=q>next;
　　　　　if (p)
　　　　　　{s=p;p=p>next;// 將要插入結點摘下
　　　　　　　s>next=q>next;//插入合適位置q結點後
　　　　　　　q>next=s;
　　　　　　}
　　　　}
　　}

設計一算法使得在盡可能少的時間內重排數組將所有取負值的關鍵字放在所有取非負值的關鍵字之前請分析算法的時間復雜度 
解
　　因為只需將負數關鍵字排在前面而無需進行精確排列順序因此本算法采用兩端掃描的方法就象快速排序采用的方法一樣左邊掃描到正數時停止開始掃描右邊遇到負數時與左邊的當前記錄交換如此交替進行一趟下來就可以完成排序

　void ReSort(SeqList R)
　　{//重排數組使負值關鍵字在前
　　　int i=j=n; //數組存放在R[n]中
　　　while (i<j) //i<j表示尚未掃描完畢
　　　　{ while(i<j&&R[i]key<) //遇到負數則繼續掃描
　　　　　　i++;
　　　　　R[]=R[i]; //R[]為輔助空間
　　　　　while(i<j&&R[j]key>=)// 遇到正數則繼續向左掃描
　　　　　　　　j;
　　　　　R[i++]=R[j];R[j]=R[];//交換當前兩個元素並移動指針
　　　　}//endwhile
　　}//ReSort

　　本算法在任何情況下的比較次數均為n(每個元素和)相比交換次數少於n/總的來說時間復雜度為O(n)

*寫一個雙向冒泡排序的算法即在排序過程中交替改變掃描方向 
解
　　算法如下
　void BubbleSort(SeqList R)
　　{//R[n]是待排序文件雙向掃描冒泡排序
　　　int ijk;
　　　Boolean exchange; //交換標記
　　　i=n;j=;
　　　exchange=TRUE;
　　　while (i>j)&&(exchange)
　　　　{k=i;exchange=FALSE;
　　　　　while (k>=j)//由下往上掃描
　　　　　　{if (r[k]>r[k+])
　　　　　　　　{r[]=r[k];r[k]=r[k+];r[k+]=r[k];exchange=TRUE;//交換
　　　　　　　　}//endif
　　　　　　　k;
　　　　　　}//endwhile
　　　　　if (exchange)
　　　　　　{exchange=FALSE;
　　　　　　　j++;k=j+;
　　　　　　　while(k<=i)//由上往下掃描
　　　　　　　　{if (r[k]<r[k])
　　　　　　　　　{r[]=r[k];r[k]=r[k];r[k]=r[k];exchange=TRUE;//交換
　　　　　　　　　}//endif
　　　　　　　　　k++;
　　　　　　　　}endwhile
　　　　　　　i;
　　　　　　}//endif
　　　　}endwhile
　　}//endsort

下面是一個自上往下掃描的冒泡排序的偽代碼算法它采用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 

解算法如下
void BubbleSort(int A[]int n)
　//不妨設A[n]是整型向量
　int lastExchangeji=;
　while (i<n) //這一條很重要如不改為這樣算法將無限循環下去
　　lastExchange=n;
　　for(j=n;j>i;j)//從下往上掃描A[i]
　　　　if(A[j]<A[j]){
　　　　　　交換A[j]和A[j];
　　　　　　lastExchange=j;
　　　　}
　　i=lastExchange;//將i置為最後交換的位置
　}//endwhile
}//BubbleSort

改寫快速排序算法要求采用三者取中的方式選擇劃分的基准記錄若當前被排序的區間長度小於等於時無須劃分而是直接采用直接插入方式對其排序 
解
　　改寫後的算法如下
　void QuickSort(SeqList Rint low int high)
　　{//對R[lowhigh]快速排序
　　　int pivotpos;
　　　if(highlow<=)//若當前區內元素少於個
　　　　{//則進行直接插入排序
　　　　　InsertSort(Rlowhigh);
　　　　}
　　　else
　　　　{
　　　　　pivotpos=midPartion(Rlowhigh);
　　　　　QuickSort(Rlowpivotpos);
　　　　　QuickSort(Rpivotpos+high);
　　　　}
　　}//QuickSort

　int midPartion(SeqList Rint i int j)
　　{//三者取中規則定基准
　　　if(R[(i+j)/]key>R[i]key)
　　　　{ 交換R[(i+j)/]和R[i];}
　　　if(R[i]key>R[j]key)
　　　　{ 交換R[i]和R[j];}
　　　if(R[i]key)<R[(i+j)/]key)
　　　　{ 交換R[i]和R[(i+j)/];}
　　　//以上三個if語句就使區間的第一個記錄的key值為三個key的中間值
　　　return Partion(Rij);//這樣我們就可以仍使用原來的劃分算法了
　　}

對給定的j(≤j≤n )要求在無序的記錄區R[n]中找到按關鍵字自小到大排在第j個位置上的記錄(即在無序集合中找到第j個最小元)試利用快速排序的劃分思想編寫算法實現上述的查找操作 
答
　int QuickSort(SeqList Rint jint lowint high)
　　{ //對R[lowhigh]快速排序
　　　int pivotpos //劃分後的基准記錄的位置
　　　if(low<high){//僅當區間長度大於時才須排序
　　　　　pivotpos=Partition(Rlowhigh) //對R[lowhigh]做劃分
　　　　　if (pivotpos==j) return r[j];
　　　　　else if (pivotpos>j) return(Rjlowpivotpos);
　　　　　　　　else return quicksort(Rjpivotpos+high);
　　　　}
　　} //QuickSort

以單鏈表為存儲結構寫一個直接選擇排序算法
答
　#define int KeyType //定義KeyType 為int型
　typedef struct node{
　　　KeyType key; //關鍵字域
　　　OtherInfoType info; //其它信息域
　　　struct node * next; //鏈表中指針域
　　}RecNode; //記錄結點類型

　typedef RecNode * LinkList ; //單鏈表用LinkList表示

　void selectsort(linklist head)
　　{RecNode *p*q*s;
　　　if(head>next)&&(head>next>next)
　　　　{p=head>next;//p指向當前已排好序最大元素的前趨
　　　　　while (p>next)
　　　　　　{q=p>next;s=p;
　　　　　　　while(q)
　　　　　　　　{if (q>key<s>key) s=q;
　　　　　　　　　q=q>next;
　　　　　　　　}//endwhile
　　　　　　　交換s結點和p結點的數據
　　　　　　　p=p>next;
　　　　　　}//endwhile
　　　　}//endif
　　}//endsort

寫一個heapInsert(Rkey)算法將關鍵字插入到堆R中去並保證插入R後仍是堆提示應為堆R增加一個長度屬性描述(即改寫本章定義的SeqList類型描述使其含有長度域)將key先插入R中已<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23604.html