快速排序C或C++程序

C++#includeiostreamusingnamespacestd;//从小到大intpartition(inta[],intp,intr){intx=a[r];//通常，拿最后一个值，作为预期的中间值intmiddle=p;//记录“较小的一段数据”的最大下标。通常这个值在p和r的中间，故起名middlefor(intj=p;jr;j++){if(a[j]x){if(j!=middle){inttemp=a[middle];a[middle]=a[j];a[j]=temp;}middle++;}}inttemp=a[r];a[r]=a[middle];a[middle]=temp;returnmiddle;}voidQuickSort(inta[],intp,intr){if(pr){intq=partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}intmain(){intarray[]={0,-2,11,-4,13,-5,14,-43};QuickSort(array,0,7);for(inti=0;i=7;i++)coutarray[i];coutendl;return0;}C语言版本voidQuickSort(inta[],intnumsize)//a是整形数组，numsize是元素个数{inti=0,j=numsize-1;intval=a[0];//指定参考值val大小if(numsize1)//确保数组长度至少为2，否则无需排序{while(ij)//循环结束条件{for(;ji;j--)//从后向前搜索比val小的元素，找到后填到a[i]中并跳出循环if(a[j]val){a[i]=a[j];break;}for(;ij;i++)//从前往后搜索比val大的元素，找到后填到a[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)||(a.length==0))return;while(ij){while(ij&&a[i]=a[j]){//以数组start下标的数据为key，右侧扫描j--;}if(ij){//右侧扫描，找出第一个比key小的，交换位置inttemp=a[i];a[i]=a[j];a[j]=temp;}while(ij&&a[i]a[j]){//左侧扫描（此时a[j]中存储着key值）i++;}if(ij){//找出第一个比key大的，交换位置inttemp=a[i];a[i]=a[j];a[j]=temp;}}if(i-start1){//递归调用，把key前面的完成排序quickSort(a,start,i-1);}if(end-i1){quickSort(a,i+1,end);//递归调用，把key后面的完成排序}}////////////////////////////方式二////////////////////////////////更有效率点的代码：publicTextendsComparable?superTT[]quickSort(T[]targetArr,intstart,intend){inti=start+1,j=end;Tkey=targetArr[start];SortUtilTsUtil=newSortUtilT();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&&ij){i++;}if(i=j){break;}sUtil.swap(targetArr,i,j);if(targetArr[i]==key){j--;}else{i++;}}/*关键数据放到‘中间’*/sUtil.swap(targetArr,start,j);if(starti-1){this.quickSort(targetArr,start,i-1);}if(j+1end){this.quickSort(targetArr,j+1,end);}returntargetArr;}////////////////方式三：减少交换次数，提高效率/////////////////////privateTextendsComparable?superTvoidquickSort(T[]targetArr,intstart,intend){inti=start,j=end;Tkey=targetArr[start];while(ij){//按j--方向遍历目标数组，直到比key小的值为止while(ji&&targetArr[j].compareTo(key)=0){j--;}if(ij){//targetArr[i]已经保存在key中，可将后面的数填入targetArr[i]=targetArr[j];}//按i++方向遍历目标数组，直到比key大的值为止while(ij&&targetArr[i].compareTo(key)0){i++;}if(ij){//targetArr[j]已保存在targetArr[i]中，可将前面的值填入targetArr[j]=targetArr[i];}}//此时i==jtargetArr[i]=key;if(i-start1){//递归调用，把key前面的完成排序this.quickSort(targetArr,start,i-1);}if(end-j1){//递归调用，把key后面的完成排序this.quickSort(targetArr,j+1,end);}}