quicksorting.java

sorting,分类的几种常见的java实现

package sorting_yanrui;

import java.util.TimerTask;

public class QuickSorting {
	static int c=0;
	static TimerTask timer;
	public long QuickSorting (int a[],int lo, int hi)
	{ 
	 //  lo is the lower index, hi is the upper index 
	 //  of the region of array a that is to be sorted 
		 int i=lo, j=hi, h; 
		 int x=a[(lo+hi)/2]; 

	 //  partition 
	 do 
	 { 
	  while (a[i]<x) {i++; }//c++;}
	  while (a[j]>x) {j--; }//c++;}
	  if (i<=j) 
	  { 
	   h=a[i]; a[i]=a[j]; a[j]=h; 
	   i++; j--;c++; 
	  } 
	 } while (i<=j); 

	 //  recursion 
	 if (lo<j) QuickSorting(a, lo, j); 
	 if (i<hi) QuickSorting(a, i, hi); 
	long t=timer.scheduledExecutionTime();
	 return t;
}

	
	public static void sift(int key[],int l,int m)
	{
	    int i,j,x;
	    i=l;
	    j=2*i;
	    x=key[i];
	    while (j<=m)
	    {   
	        c++;
	        if(j<m && key[j]<key[j+1]) {j++;c++;c++;}
	        if(x<key[j])
	        {
	            c++;
	            key[i]=key[j];//shiftCount++;
	            i=j;//shiftCount++;
	            j=2*i;
	        }
	        else j=m+1;
	    }
	    key[i]=x;//shiftCount++;
	}


}