Quick Sort

Quick Sort

這排序法一時難理解他的原理，
據說他的精神是在一數列中選一個數字P為基準點(pivot)
然後將其他的數字分成兩邊
大於P的放左邊，小於P的放右邊

之後分別在左、右兩邊的數列有找一個數I(左)、J(右)當基準點
也一依照上一段作法。


步驟:

以第一個數為基準點



package lottery;

public class lottery {
static int  sum;
static long[] array=new long[42];
static long[] num = new long[42];
public static void random(){
   
for(long i=1;i<=100000L;i++)
{ sum =(int)(Math.random()*42)+1;
//System.out.println(sum);
array[sum-1]+=1;
}
    }
   
public static void print_array(){
   
System.out.println("number"+"\t"+"frequency");
for(int i=0;i<array.length;i++)
{
System.out.print((i+1)+"\t");
System.out.println(array[i]);
}
}
public static void selection_sort(){
for(int i=0;i<array.length;i++)
{
 for(int j=i+1;j<array.length;j++)
 {

 long temp;
  if(array[j]>array[i])
  {
  temp = array[i];
  array[i]=array[j];
  array[j]=temp;
  }
 }
}
}

   
public static void main(String[] args) {            
    random();
    print_array();
//    selection_sort();
//    System.out.println(array.length);
    Quick_sort(array,0,array.length-1);
   
   
    //int count =0;
System.out.println("\n"+"descend sort"+"\n");
for(int i=0;i<array.length;i++)
{
System.out.print((i+1)+"\t");
System.out.println(array[i]);
    }
    //Quit_sort(array,1,array.length);
}
public static void Quick_sort(long[] array,int left,int right)
{
   //large to small
  
int pivot = left;//pivot
int i=left+1;//index of left
int j= right;//index of right
long temp;
while(true)
{
    while((i< array.length) && (array[i]< array[pivot])){
     i++;   
   }
   
 while( (j>-1)&&(array[j] > array[pivot])  )
{
 j--;
}

if( j>= i)
{
temp = array[ j];
array[j]=array[pivot];
array[pivot] = temp;
break;
}
temp = array[ j];
array[ j]=array[ i];
array[ i]=temp;
}

Quick_sort(array,j+1,right);//right
Quick_sort(array,left,j-1 );//left
}
   
}