黑马程序员技术交流社区

标题: 快速排序 java实现 [打印本页]

---

作者: 何向阳    时间: 2012-12-22 09:35
标题: 快速排序 java实现

快速排序是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;  
•     }  
• }  
  
  

---

作者: 王进亮    时间: 2012-12-22 12:25
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);  // 递归调用,排序右半区
  }
  
}
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2