QuickSort 再探, 高分请教!

Question

小第已经写好了,把最后一个数作为POVIT的程序,已经测试!
public class QuickSort{
public static void main(String[] args){
  int length=100; int []a=new int[length];

for(int i=0;i<length;i++)

 a[i]=(int)(Math.random()*length);
  for(int i=0;i<a.length;i++)
    System.out.print(a[i]+",");
System.out.println("==============");  QSort(a,0,length-1);
  
  for(int i=0;i<a.length;i++){
    System.out.print(a[i]+",");
  }
}static int Partition(int[] list, int low, int high) {
  
   int pivotkey;
   int temp = list[high];            
   pivotkey = list[high];     
   while (low<high) {            
      while (low<high && list[low]<=pivotkey) ++low;
      list[high] = list[low];      
      
      while (low<high && list[high]>=pivotkey) --high;
      list[low] = list[high];     
      
   }
   list[high] = temp;            
   return high;                  
} 
static void QSort(int[] list, int low, int high) {   int pivotloc;
  if (low < high) {                     
    pivotloc = Partition(list, low, high);  
    QSort(list, low, pivotloc-1); 
    QSort(list, pivotloc+1, high);         
  }
} }

Answer 1

public class QuickSort1{
  public static void main(String[] args){
    int[] a = new int[] {8,1,4,9,6,3,5,2,7,0};
    QSort(a,0,9);
    for(int i=0;i<a.length;i++){
      System.out.print(a[i]+",");
    }
  }
  static int Partition(int[] list, int low, int high) {
    int pivotkey = list[high];  //最后一个数
    while (low<high) {
      while (low<high && list[low]<=pivotkey) ++low;
        list[high] = list[low];
      while (low<high && list[high]>=pivotkey) --high;
        list[low] = list[high];
   }
   list[high] = pivotkey;
   return high;
  } 
  static void QSort(int[] list, int low, int high) {
    int pivotloc;
    if (low < high) {
      pivotloc = Partition(list, low, high);
      QSort(list, low, pivotloc-1);
      QSort(list, pivotloc+1, high);
    }
  } 
}

Answer 2

public class QuickSort2{
  private static java.util.Random rand = new java.util.Random();
  public static void main(String[] args){
    int[] a = new int[] {8,1,4,9,6,3,5,2,7,0};
    QSort(a,0,9);
    for(int i=0;i<a.length;i++){
      System.out.print(a[i]+",");
    }
  }
  static int Partition(int[] list, int low, int high) {
    int privotIndex = rand.nextInt(high);   //随机数
    while(privotIndex<low || privotIndex>high){
      privotIndex = rand.nextInt(high);
    }    
    int temp = list[privotIndex];
    list[privotIndex] = list[high];
    list[high] = temp;    
    int pivotkey = temp;
    while (low<high) {
      while (low<high && list[low]<=pivotkey) ++low;
        list[high] = list[low];
      while (low<high && list[high]>=pivotkey) --high;
        list[low] = list[high];
   }
   list[high] = pivotkey;
   return high;
  } 
  static void QSort(int[] list, int low, int high) {
    int pivotloc;
    if (low < high) {
      pivotloc = Partition(list, low, high);
      QSort(list, low, pivotloc-1);
      QSort(list, pivotloc+1, high);
    }
  } 
}

Answer 3

public class QuickSort3{
  public static void main(String[] args){
    int[] a = new int[] {8,1,4,9,6,3,5,2,7,0};
    QSort(a,0,9);
    for(int i=0;i<a.length;i++){
      System.out.print(a[i]+",");
    }
  }
  static int Partition(int[] list, int low, int high) {
    int privotIndex = (low+high)/2;   //中间数
    int temp = list[privotIndex];
    list[privotIndex] = list[high];
    list[high] = temp;    
    int pivotkey = temp;
    while (low<high) {
      while (low<high && list[low]<=pivotkey) ++low;
        list[high] = list[low];
      while (low<high && list[high]>=pivotkey) --high;
        list[low] = list[high];
   }
   list[high] = pivotkey;
   return high;
  } 
  static void QSort(int[] list, int low, int high) {
    int pivotloc;
    if (low < high) {
      pivotloc = Partition(list, low, high);
      QSort(list, low, pivotloc-1);
      QSort(list, pivotloc+1, high);
    }
  } 
}

Answer 4

为什么“只有找头,尾,中间,三个数的中间数作为POVIT才是科学的”？

Answer 5

因为,如果头或尾的数,是最大的,或者是最小的,那QUICKSORT的效率就大打折扣了,理想的POVIT是所有数的中值,但对于长数列来说,不大可能实现.所有只有找头或尾的中值了.

Answer 6

老大,我发现程序有个大BUG,当对30000个数或者更多(降序)的进行排列的时候,OVERFLOW了.这是怎么回事? 
int length=300000;
int []a=new int[length];
for(int i=0;i<length;i++)
 a[i]=(length-i);对上面的数组A进行排列,出现OVERFLOW情况.

Answer 7

原代码不存在大BUG，仅是因用递归算法致使栈溢出，现已改进为非递归(仅针对Integer)，你再试一下：
public class QuickSort4{
  private static Integer[] list;
  private static java.util.LinkedList stack;  
  public static void main(String[] args){
    Integer[] list = new Integer[30000];
    for(int i=0;i<list.length;i++)
      list[i]=new Integer(list.length-i);
    QSort(list);
    for(int i=0;i<list.length;i++)
      System.out.print(list[i]+","); 
  }  
  private static int getPartition(int low, int high) {
    Integer tempInt = list[low];
    while (low<high) {
      while (low<high && list[high].intValue()>=tempInt.intValue()) --high;
        list[low] = list[high];
      while (low<high && list[low].intValue()<=tempInt.intValue()) ++low;
        list[high] = list[low];
    }
    list[low] = tempInt;
    return low;
  }  
  public static void QSort(Integer[] list){
    QuickSort1.list = list;
    stack = new java.util.LinkedList();
    quicksort(0,list.length-1);
  } 
  private static void quicksort(int low,int high){
    Position tempPos;
    int pivotIndex;
    while(low<high){
      if((high-low)>2){
        pivotIndex = getPartition(low,high);
        if((high-pivotIndex)>(pivotIndex-low)){
          stack.addLast(new Position(pivotIndex+1,high));
          low = pivotIndex+1;
        }else{
          stack.addLast(new Position(low,pivotIndex-1));
          high = pivotIndex-1;
        }
      }else if(low<high && (high-low)<3){
        sort3(low,high);
        low = high;
      }else{
        tempPos = (Position)stack.removeLast();
        low = tempPos.low;
        high = tempPos.high;
      }
    }
  }
  private static void sort3(int low,int high){
    if((high-low) == 1){
      if(list[low].intValue() > list[high].intValue())exchange(list[low],list[high]);
      else{
        if(list[low].intValue() > list[low+1].intValue())
          exchange(list[low],list[low+1]);
        if(list[low+1].intValue() > list[high].intValue())
          exchange(list[low+1],list[high]);
        if(list[low].intValue() > list[low+1].intValue())
          exchange(list[low],list[low+1]);        
      }
    }
  }
  private static void exchange(Integer a,Integer b){
        Integer tempInt = list[a];
        list[a] = list[b];
        list[b] = tempInt;
  }
  private static class Position{
    int low,high;
    Position(int low,int high){
      this.low = low;
      this.high = high;      
    }
  } 
}