现在的位置: 首页 > 综合 > 正文

每天一道编程题(七)——————快速排序

2013年08月28日 ⁄ 综合 ⁄ 共 767字 ⁄ 字号 评论关闭
30元程序员衣装优惠券,仅剩3天!点击领取

快速排序是将要排序的集合A,进行分块排序。一般步骤为:1.如果A中的元素个数是0或1,则返回。2.A中的任意元素为pivot(中心元素【个人理解】)3.将A按照中心元素划分为两部分A1和A2 4.对A1和A2分别进行如上操作。其实是一个递归的过程。如何选取中心元素会影响到快速排序的速度,本次算法采用最普遍的将数组中的第一个元素作为pivot

public class QuickSort {
   public static int pivot(int[] nums,int first,int last){
	   int key=nums[first];
	   while(first<last){
		   while((first<last)&&(nums[last]>=key))
			   last--;
		   nums[first]=nums[last];
		   while((first<last)&&(nums[first]<=key))
			   first++;
		   nums[last]=nums[first];
	   }
	   nums[first]=key;
	   return first;
   }
	
	public static void quicksort(int[] nums,int first,int last){
      if(first<last){
    	  int pivot=pivot(nums, first, last);
    	  quicksort(nums, first, pivot-1);
    	  quicksort(nums, pivot+1, last);
      }
        
	   
   }
   public static void main(String[] args){
	   int[] num={10,9,8,7,6,5,4,3,2,1};
		int[] num2={1,2,3,4,5,6};
		quicksort(num,0,num.length-1);
		for (int a:num){
		System.out.println(a);
		}
   }
}

30元程>序员衣装优惠券,仅剩3天!点击领取

抱歉!评论已关闭.