Go语言视频零基础入门到精通

javalearner

快速排序方法java实现与分析。  
    /**
*<p>Title: 快速排序法</p>
* <p>Description:
* 快速排序法的基本精神是在数组中找出适当的轴心，
* 然后将数组一分为二，分?e对左边与右边数组进行排序，
* 而影响快速排序法效率的正是轴心的选择。</p>
* <p>下面介绍了三种方法,从理论分析效率递增，
* 但是没有用大数组来进行测试</p>
* <p>Copyright: Copyright (c) 2005</p>
* @author paulLiu
* @version 1.0
*/
   
  
  
  
   
  

1. 
   
2. public class QuickSort {
   
3.   public QuickSort() {
   
4.   }
   
5.   /**
   
6.    * printArray 用来跟踪了算法演算过程
   
7.    */
   
8.   public static void printArray(int[] number) {
   
9.     for(int k=0 ;k< number.length;k++){
   
10.          System.out.print(number[k]);
    
11.          System.out.print(" ");
    
12.         }
    
13.    System.out.print("
14. ");
    
15.   }
    
16.   /**
    
17.    * sort 只是为了便于观察分析才设了这个方法，可有可无。
    
18.    * @param number int[] 数组
    
19.    */
    
20.   public static void sort(int[] number) {
    
21.    // sort(number,0,number.length-1);
    
22.    // System.out.println("以左边第一个元素为轴算法结束/////////////////////");
    
23.    
    
24.    
    
25.   //  provesortfirst(number,0,number.length-1);
    
26.   // System.out.println("以中间元素为轴算法结束/////////////////////");
    
27.    System.out.println("排序前的数组");
    
28.    printArray(number);
    
29.    System.out.println("开始排序");
    
30.    thirdsort(number,0,number.length-1);
    
31.    System.out.println("以最右边元素为轴算法结束/////////////////////");
    
32.   }
    
33.   /**
    
34.    * sort
    
35.    * 开始时，以左边第一个元素为轴
    
36.    * @param number int[]
    
37.    * @param left int
    
38.    * @param right int
    
39.    */
    
40.   private static void sort(int[] number, int left, int right) {
    
41.     if(left< right)
    
42.     {
    
43.       
    
44.       int s=number[left];
    
45.       int i=left;
    
46.       int j=right+1;
    
47.       while(true)//将数组划分成2半,一半小于s,一半大于s。
    
48.       {
    
49.         //令索引 i 从数列左方往右方找，直到找到大于 s 的数
    
50.         while(i+1< number.length &&number[++i]< s);
    
51.         //令索引 j 从数列右方往左方找，直到找到小于s 的数
    
52.         while(j>0&&number[--j]>s);
    
53.         if(i>=j) break; //如果 i >= j，退出。
    
54.         swap(number,i,j);//如果 i < j，?t交?Q索引i与j两处的值
    
55.          printArray(number);
    
56.       }
    
57.       //将左侧轴与j交换
    
58.       number[left]=number[j];
    
59.       number[j]=s;
    
60.       sort(number,left,j-1);//轴左边进行递归
    
61.          printArray(number);
    
62.     sort(number,j+1,right);//轴右边进行递归
    
63.           printArray(number);
    
64.    }
    
65.   }
    
66.   /**
    
67.    * provesortfirst
    
68.    * 以中间的元素为轴
    
69.    * @param number int[]
    
70.    * @param left int
    
71.    * @param right int
    
72.    */
    
73.   public static void provesortfirst(int[] number, int left, int right) {
    
74.     if(left < right) {            
    
75.       int s = number[(right+left)/2];            
    
76.       int i = left - 1;            
    
77.       int j = right + 1;            
    
78.       while(true) {                 
    
79.       // 向右找               
    
80.       while(number[++i] < s) ;               
    
81.       // 向左找               
    
82.       while(number[--j] > s) ;                 
    
83.       if(i >= j)                    
    
84.         break;                 
    
85.       swap(number, i, j);
    
86.        printArray(number);
    
87.     }            
    
88.     provesortfirst(number, left, i-1);  
    
89.       printArray(number);
    
90.     provesortfirst(number, j+1, right);
    
91.       printArray(number);
    
92.    }
    
93. }
    
94.   /**
    
95.    * swap
    
96.    * 交换值方法
    
97.    * @param number int[]
    
98.    * @param i int
    
99.    * @param j int
    
100.    */
     
101.   private static void swap(int[] number, int i, int j) {
     
102.     int t;
     
103.     t=number[i];
     
104.     number[i]=number[j];
     
105.     number[j]=t;
     
106.   }
     
107.   public static void main(String[] args) {
     
108.    int[] number={1100,45,17,24,11,54,32,14,26};
     
109.     sort(number);
     
110.   }
     
111.    
     
112. private static void thirdsort(int[] number, int left, int right)
     
113.      {  
     
114.        if(left < right) {            
     
115.          int q = partition(number, left, right);
     
116.          thirdsort(number, left, q-1);  
     
117.             printArray(number);
     
118.          thirdsort(number, q+1, right);      
     
119.             printArray(number);
     
120.        }   
     
121.      }  
     
122.      /**
     
123.       * partition 在轴设置方面有优点
     
124.       * @param number int[]
     
125.       * @param left int
     
126.       * @param right int
     
127.       * @return int
     
128.       */  
     
129.      private static int partition(int number[],int left, int right) //以右端元素为轴,划分数组,返回划分点
     
130.      {      
     
131.        int s = number[right];  //先以右边最后一个为轴      
     
132.        int i = left - 1;        
     
133.        for(int j = left; j < right; j++)
     
134.        {    if(number[j] <= s)
     
135.             {    i++;      
     
136.               swap(number, i, j);     
     
137.                printArray(number);
     
138.             }      
     
139.           }         
     
140.           swap(number, i+1, right);
     
141.           return i+1;     
     
142.         }   
     
143. }
     

复制代码

程序运行的一次结果:
C:java>java QuickSort
排序前的数组
1100 45 17 24 11 54 32 14 26
开始排序
1100 45 17 24 11 54 32 14 26
1100 45 17 24 11 54 32 14 26
1100 45 54 24 11 17 32 14 26
1100 45 54 32 11 17 24 14 26
1100 45 54 32 26 17 24 14 11
1100 45 54 32 26 17 24 14 11
1100 45 54 32 26 17 24 14 11
1100 45 54 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 17 24 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
1100 54 45 32 26 24 17 14 11
以最右边元素为轴算法结束///////////////////// C:java>

  
  
   
   

     
   

     
   
  

  

  










源码下载：http://file.javaxxz.com/2014/10/29/235932515.zip