A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 何向阳 中级黑马   /  2012-12-22 09:35  /  1632 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文


快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。



代码:
  
  • import java.util.Arrays;  
  •   
  • public class QuickSort {  
  •     public static void main(String args[])  
  •     {  
  •         int array[]={49,38,65,97,76,13,27,49};  
  •         System.out.println(Arrays.toString(array));  
  •         quickSort(array,0,array.length-1);  
  •         System.out.println(Arrays.toString(array));  
  •     }  
  •    
  •     public static void quickSort(int arr[],int low,int high)  
  •     {  
  •         if(low<high)  
  •         {  
  •             int mid = partition(arr,low,high);  
  •            
  •             quickSort(arr,low,mid-1);  
  •            
  •             quickSort(arr,mid+1,high);  
  •         }  
  •     }  
  •      
  •     public static int partition(int array[],int low,int high)  
  •     {  
  •       
  •         int pivotKey = array[low];  
  •         int i=low,j=high;  
  •   
  •         if(low<high)  
  •         {  
  •             while(i<j)  
  •             {  
  •                
  •                 while(i<j&&array[j]>=pivotKey)  
  •                 {  
  •                     j--;  
  •                 }  
  •                
  •                 if(i<j)  
  •                 {  
  •                     array=array[j];  
  •                     i++;  
  •                 }  
  •                   
  •                
  •                 while(i<j&&array<=pivotKey)  
  •                 {  
  •                     i++;  
  •                 }  
  •                
  •                 if(i<j)  
  •                 {  
  •                     array[j]=array;  
  •                     j--;  
  •                 }  
  •             }  
  •             
  •             array=pivotKey;  
  •       
  •         }  
  •         
  •         System.out.println(Arrays.toString(array));  
  •         
  •         return i;  
  •     }  
  • }  



评分

参与人数 1技术分 +1 收起 理由
邵天强 + 1 论坛有好多快速排序例子,不过鼓励一下.

查看全部评分

1 个回复

倒序浏览
public class Test4 {
public static void main(String[] args) {
  int[] arr = new int[] { 4, 2, 6, 8, 1, 7, 5, 9, 0 };
  Test4 test4 = new Test4();//实例化对象
  test4.quicksort(arr, 0, arr.length-1);// 传参并调用quicksort
  System.out.println(Arrays.toString(arr));//打印结果
}
public void swap(int arr[],int i,int j) {// 通过临时变量,交换数据
           int temp=arr[i];
           arr[i]=arr[j];
           arr[j]=temp;
}                                  // 第一次交换分析
public void quicksort(int arr[],int low,int high){ // 假设传入low=0; high=a.length-1;
  if(low<high){
   int pivot,ppos,i; // 声明变量
   ppos=low; // p_pos指向low,即位索引为0位置 ;
   pivot=arr[ppos]; // 将0位置上的数值赋给pivot;
   for(i=low+1;i<=high;i++){
    if(arr[i]>pivot){ // 1位置的数与0位置数作比较: a[1]>a[0]
     ppos++; // 2位与1位比较,3位与2位比较......
     swap(arr,ppos,i);   // 传参并调用swap      
    }
   
   }
   swap(arr,low,ppos); // 将p_pos设为high再次调用swap
   quicksort(arr,low,ppos-1);   // 递归调用,排序左半区
   quicksort(arr,ppos+1,high);  // 递归调用,排序右半区
  }
  
}
}

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马