结构推理
写一个递归方式的选择排序算法。
非递归选择排序算法如下：
void selectionSort(int list[],int last){
int current;
int smallest;
int holdData;
int walker;
for(current=0;current＜last;current++){
smallest=current;
for(walker=current+1;walker＜=last;walker++)
if(list[walker]＜list[smallest])smallest=walker;
holdData=list[current];
list[current]=list[smallest];
list[smallest]=holdData;
}
return;
}
【正确答案】(1)递归方式的选择排序算法
void selectionSort_recursive(int list[],int first,int last){
int smallest;
int holdData;
int walker;
if(first＞=last)return;
smallest=first;
for(walker=first;walker＜=last;walker++)
if(list[walker]＜list[smallest])smallest=walker;
holdData=list[first];
list[first]=list[smallest];
list[smallest]=holdData;
selectionSort recursive(list,first+1,last);
}
(2)代价分析
与选择排序算法相同，该算法的时间复杂度为O(n2)。
【答案解析】