java编程之排序

浏览数：10 / 时间：2015年06月08日

第一种排序：【冒泡排序】基本数据类型的排序。

【1】最简易的冒泡排序。效率低。因为比较的次数和趟数最多。

 1 /**
 2      * 最原始的冒泡排序。
 3      * 效率低。
 4      * 因为趟数和次数最多。都是按最大化的循环次数进行循环
 5     * @Title: sort 
 6     * @Description: TODO(这里用一句话描述这个方法的作用) 
 7     * @param arr
 8     * @return void    返回类型 
 9     * @author 尚晓飞
10     * @date 2014-8-5 上午8:42:45
11      */
12     public static void sort(int[] arr){
13                 //要走arr.length-1趟
14                 for(int i=0;i<arr.length-1;i++){
15                         System.out.println("第"+(i+1)+"趟");
16                     for(int j=0;j<arr.length-1;j++){
17                         
18                         if(arr[j]>arr[j+1]){
19                             int temp=arr[j];
20                             arr[j]=arr[j+1];
21                             arr[j+1]=temp;
22                         
23                         }
24                         System.out.println("第"+(j+1)+"次"+Arrays.toString(arr));
25                     }
26                 }
27                 System.out.println("TestSort.sort01()"+Arrays.toString(arr));
28     }

View Code

【2】进行一次优化的冒泡排序。减少每趟的比较次数。

 1 /**
 2      * 冒泡排序，减少每趟比较的次数.
 3      * 每一趟都能找到数列中相对最大的一个数。
 4      * 而每一次，都是进行数列中每两个相邻的数进行比较。需要比较数列长度-1次。才能完成一趟。
 5      * 由于每一趟都找出一个最大数，所以，找出的最大数，就不用再比较了，因此每一趟的比较次数就随着趟数的增加而减少。
 6     * @Title: sort01 
 7     * @Description: TODO(这里用一句话描述这个方法的作用) 
 8     * @param arr
 9     * @return void    返回类型 
10     * @author 尚晓飞
11     * @date 2014-8-4 下午8:37:45
12      */
13     public static void sort01(int[] arr){
14         //要走arr.length-1趟
15         for(int i=0;i<arr.length-1;i++){
16                 System.out.println("第"+(i+1)+"趟");
17             for(int j=0;j<arr.length-1-i;j++){
18                 
19                 if(arr[j]>arr[j+1]){
20                     int temp=arr[j];
21                     arr[j]=arr[j+1];
22                     arr[j+1]=temp;
23                 }
24                 System.out.println("第"+(j+1)+"次"+Arrays.toString(arr));
25             }
26         }
27         System.out.println("TestSort.sort01()"+Arrays.toString(arr));
28     }

View Code

【3】进行最终的优化。减少比较的趟数和次数

 1     /**
 2      * 冒泡排序。最终版，减少趟数并且也减少每趟的次数
 3     * @Title: sort02 
 4     * @Description: TODO(这里用一句话描述这个方法的作用) 
 5     * @param arr
 6     * @return void    返回类型 
 7     * @author 尚晓飞
 8     * @date 2014-8-4 下午8:52:59
 9      */
10     public static void sort02(int[] arr){
11                 //建立一个标示。如果数列已经排序完毕，则跳出循环，提高效率
12                 boolean flag=true;
13                 for(int i=0;i<arr.length-1;i++){
14                     System.out.println("第"+(i+1)+"趟");
15                      flag=true;
16                     for(int j=0;j<arr.length-1-i;j++){
17                         
18                         if(arr[j]>arr[j+1]){
19                             int temp=arr[j];
20                             arr[j]=arr[j+1];
21                             arr[j+1]=temp;
22                             //如果有相邻数字互换位置，说明数列还没有排好序，则将标示改成false，不让跳出循环
23                             flag=false;
24                         }
25                         System.out.println("第"+(j+1)+"次"+Arrays.toString(arr));
26                     }
27                     
28                     //在某一趟，已经没有相邻数据交换位置，说明，顺序已经排好，则跳出本层循环
29                     if(flag){
30                         break;
31                     }
32                     
33                 
34                 }
35                 System.out.println("TestSort.sort02()"+Arrays.toString(arr));
36     }