排序算法 Java编程问题 小结

快排

遇到的问题：

通过断点调试 发现主要的问题是在第二递归时的if判断语句条件不对，看了 这篇博客的条件判断才发现问题所在。第一个判断语句不应该是l>1,而是左指针大于左边界lchild.完整的快排Java代码如下：

package Sort;

import java.util.Arrays;

public class QuickSort {
	public static void main(String args[]) {
		int arr[]= {33,2,3,4,6,1,34,21,45,25,76,81,18};
		
		  sort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
  public  static void sort(int arr[],int lchild,int rchild) {//为什么这里非要static修饰呢？
	  /*第一步 建立枢纽
	   * 第二步  设置方向
	   * 第三步  l r 分别为左右指针  lchild rchild分别表示左右边界
	   * */   
	  int l = lchild;
	  int r = rchild;
	  
	  int temp = arr[l];//待调整的元素，每一次将左边界值作为枢纽
	  int direction = 0;//表从右开始；
	  while( r != l ) {
		  if(direction == 0) {
			  if(r>lchild && arr[r]<temp  ) {
				  arr[l]=arr[r];
				  direction = 1;
			  }else r--; 
		  }else {
			  if(l<rchild && arr[l]>temp) {
				  arr[r] = arr[l];
				  direction = 0;
			  }else l++;
		  }
	  }
	  arr[l] = temp;//每一步的操作都是交换位置，这一步有必要吗？有，因为每次交换位置之后都是都是值大的替代了前一位，所以在数组在单轮调整完全之前都会有两个值相同。故待调整的元素会被覆盖，将提前存好的待调元素放在左右指针相汇的位置。
	  
	
	 
 	  if(l>lchild) {//注意这里不是l>1 ,而是左指针大于左边界
 		  
 		 sort(arr,lchild,l-1);
 	  }
 	  if( rchild-r >1) {
 		 sort(arr,r+1,rchild); 
 	  }
	  
  }
  
}