第10章 内排序.doc

《第10章 内排序.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第10章内排序程序10.1简单选择排序templatevoidSelectSort(TA[],intn){intsmall;for(inti=0;ivoi

2、dInsertSort(TA[],intn){for(inti=1;i0&&tempvoidBubbleSort(TA[],intn){inti,j,last;i=n-1;while(i>0){//最多进行n-1趟last=0;//进入循环就将l

3、ast置成0for(j=0;jvoidQuickSort(TA[],intn){QSort(A,0,n-1);//以初始序列为待排序序列开始快速排序}templatevoidQSort(TA[],intleft,intright)//left和right为待排序

4、序列的下界和上界{inti,j;if(leftA[left]);//j指针从右往左找第一个£分割元素的元素if(i

5、);//交换分割元素A[left]和A[j]的位置QSort(A,left,j-1);//对低端序列快速排序QSort(A,j+1,right);//对高端序列快速排序}}程序10.5两路合并的C++程序templatevoidMerge(TA[],inti1,intj1,inti2,intj2){//i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界T*Temp=newT[j2-i1+1];//分配能存放两个子序列的临时数组inti=i1,j=i2,k=0;//i,j是两个子序列的游动指针，k是Temp的游动指针while(i<=j1&&j

6、<=j2)//若两个子序列都不空，则循环if(A[i]<=A[j])Temp[k++]=A[i++];//将A[i]和A[j]中较小的存入Temp[k]elseTemp[k++]=A[j++];while(i<=j1)Temp[k++]=A[i++];//若第一个子序列中还有剩余的就存入Tempwhile(j<=j2)Temp[k++]=A[j++];//若第二个子序列中还有剩余的就存入Tempfor(i=0;i

7、sT>voidMergeSort(TA[],intn){inti1,j1,i2,j2;//i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界intsize=1;//子序列中元素个数，初始化为1。while(sizen-1)j2=n-1;//若第2个子序列中不足size个元素，则置子序列2的上界j2=n-1els