快速排序 递归算法代码实现如下
那么问题来了：
楼主经过debug,得出:先进行第一次分组,得出第一个middle值,
之后不断的调用_quickSort(list, low, middle - 1);对低字表进行递归排序.
直到if(low < high)条件语句不成立(这是完成对低字表的排序).
问题就出现在这,if条件语句判断为false时,这时为什么还要执行if(){}内的_quickSort(list,middle + 1, high); 这部分代码?还有这时执行这个方
法时,参数取值的来源是什么?
1.public class quickSort {
2. int a[]={49,38,18,23,34,15,35,25,53,51};
3.public quickSort(){ //构造方法
4. quick(a);
5. for(int i=0;i<a.length;i++){
6. System.out.println(a[i]);
}
}
7. public int getMiddle(int[] list, int low, int high) {
8. int tmp =list[low]; //数组的第一个作为中轴
9. while (low < high){
10. while (low < high&& list[high] >= tmp) {
11. high--;
}
12. list[low] =list[high]; //比中轴小的记录移到低端
13. while (low < high&& list[low] <= tmp) {
14. low++;
}
15. list[high] =list[low]; //比中轴大的记录移到高端
}
16. list[low] = tmp; //中轴记录到尾
17. return low; //返回中轴的位置
}
18. public void _quickSort(int[] list, int low, int high) {
19. if (low < high){
20. int middle =getMiddle(list, low, high); //将list 数组进行一分
21. _quickSort(list, low, middle - 1); //对低字表进行递归排
22. _quickSort(list,middle + 1, high); //对高字表进行递归排序
}
}
public void quick(int[] a2) {
if (a2.length > 0) { //查看数组是否为空
_quickSort(a2,0, a2.length - 1);
}
}
public static void main(String[] args) {//主方法
quickSort q=new quickSort();
}
}
------解决思路----------------------
恩对，是非常常见的哦，能用到递归大部分是因为使用了分治法，就是把大任务分成相同的几个小任务，代码都是类似于这样的~