快速排序C或C++程序.doc

《快速排序C或C++程序.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、C++#include　usingnamespacestd;//从小到大intpartition(inta[],intp,intr){intx=a[r];//通常，拿最后一个值，作为预期的中间值intmiddle=p;//记录“较小的一段数据”的最大下标。通常这个值在p和r的中间，故起名middlefor(intj=p;j

2、;a[r]=a[middle];a[middle]=temp;returnmiddle;}  voidQuickSort(inta[],intp,intr){if(p

3、rn0;} C语言版本voidQuickSort(inta[],intnumsize)//a是整形数组，numsize是元素个数{inti=0,j=numsize-1;intval=a[0];//指定参考值val大小if(numsize>1)//确保数组长度至少为2，否则无需排序{while(ii;j--)//从后向前搜索比val小的元素，找到后填到a[i]中并跳出循环if(a[j]

4、j]中并跳出循环if(a[i]>val){a[j]=a[i];break;}}a[i]=val;//将保存在val中的数放到a[i]中QuickSort(a,i);//递归，对前i个数排序QuickSort(a+i+1,numsize-1-i);//对i+1到numsize这numsize-1-i个数排序}}JAVApublicstaticvoidquickSort(inta[],intstart,intend){inti,j;i=start;j=end;if((a==null)

5、

6、(a.length==0))return;while(i

7、1){//递归调用，把key前面的完成排序quickSort

8、(a,start,i-1);}if(end-i>1){quickSort(a,i+1,end);//递归调用，把key后面的完成排序}} ////////////////////////////方式二////////////////////////////////更有效率点的代码：public>T[]quickSort(T[]targetArr,intstart,intend){inti=start+1,j=end;Tkey=targetArr[start];SortUtils

9、Util=newSortUtil(); if(start>=end){returntargetArr;} /*从i++和j--两个方向搜索不满足条件的值并交换**条件为：i++方向小于key，j--方向大于key*/while(true){while(targetArr[j].compareTo(key)>0){j--;}while(targetArr[i].compareTo(key)<0&&i=j){break;}sUtil.swap(targetArr,i,j);if(targetArr[i]==k

10、ey){j--;}else{i++;}} /*关键数据放到‘中间’*/sUtil.swap(targetArr,start,j); if(start