JAVA数据结构与算法---JAVA冒泡排序

按List中Person类的age属性进行排序。

Person类：

package com.flg;

/**
 * Created with IntelliJ IDEA.
 * User: fuliguo
 * Date: 12-7-29
 * Time: 下午13:09
 * To change this template use File | Settings | File Templates.
 */
public class Person {

    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public Person(){}

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

}

MyPersonListSortTest_bubble类：

 

 

 

 

package com.flg;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * 冒泡排序
 * Created with IntelliJ IDEA.
 * User: fuliguo
 * Date: 12-7-29
 * Time: 下午13:10
 * To change this template use File | Settings | File Templates.
 */
public class MyPersonListSortTest_bubble {

    /**
     * 获得要测试的list
     * @return   list
     */
    public List getList(){

        List list  = new ArrayList<Person>() ;
        Random random = new Random();
        int j;
       /*
       for(int i=0;i<10;i++){
           j = 1+Math.abs(random.nextInt()%29); //30以内随机数
             //System.out.println("随机数-->>"+j);
             list.add(new Person("张"+j,j));  //年龄随机增长

       }
       */

        list.add(new Person("张6",6));
        list.add(new Person("张9",9));
        list.add(new Person("张12",12));
        list.add(new Person("张18",18));
        list.add(new Person("张16",16));
        list.add(new Person("张20",20));
        list.add(new Person("张3",3));
        list.add(new Person("张27",27));
        list.add(new Person("张30",30));
        list.add(new Person("张30",30));


        return list;

    }

    /**
     * 控制台输出遍历list对像顺序
     * @param list
     */
    public  void printList(List list) {
        Person p;
        for(int i=0;i<list.size();i++){
            p = (Person)list.get(i);
            System.out.println(p.getName()+"---"+p.getAge());
        }

    }

    private void swap(List list,int i,int j){

                Person p1 = (Person)list.get(i);
                Person p2 = (Person)list.get(j);

                list.set(i,p2);
                list.set(j,p1);

    }
    /**
     * 对list进行排序:冒泡排序
     *
     * 从本轮第一个对象开始，逐个与它后面的每个对象比较，
     * 如果大小关系不对，位置就对换
     * 注意对换后，其实本轮第一个对象已经变了，然后拿这个换后的对象继续与后面的比较
     *
     * @param list
     */
    public void listSort1(List<Person> list,boolean isAsc){

               int comparaCount = 0;//统计比较次数
               int swapCount = 0;//统计交换次数

               Person p1,p2;

               for(int i=0;i<list.size();i++){

                   for(int j=i+1;j<list.size();j++){
                       p1 = (Person)list.get(i);
                       p2 = (Person)list.get(j);

                         /**
                          * 根据非运算特点，此代码可优化成非运算形式
                          * true^true---false
                          * true^false---true
                          * false^false---false

                          if(isAsc){//升序
                               if(p1.getAge()>p2.getAge()){
                                   swap(list,i,j);
                               }
                          }else {
                              if(p1.getAge()<p2.getAge()){
                                  swap(list,i,j);
                              }
                          }
                        */
                          comparaCount ++;//统计比较次数
                          if(!(isAsc^(p1.getAge()>p2.getAge()))){ //非运算，非真即假
                              swap(list,i,j);//i和j位置上的对象交换
                              swapCount++;//统计交换次数
                          }



                   }
               }
        //若使用统计比较数comparaCount和统计交换次数swapCount
        //要改成固定方式生成对象，针对同一组对象进行比较，
        // 否则随机生成，前后没有可比性
        System.out.println("listSort1===>comparaCount:"+comparaCount+"||swapCount:"+swapCount);
    }

    /**
     * 对list进行排序:冒泡排序
     *
     * <从前往后>，相邻对象两两比较
     * 与listSort1相比，即便不是本轮要找的最小/大对象，中间过程中也不会被换到比它小/大的对象后面
     * 而listSort1只是想着把本轮最小的找出来，在这轮过程中已经分出大小的对象位置得不到巩固
     * 该方法为方法3做中间过渡
     *
     *
     * @param list
     */
    public void listSort2(List<Person> list,boolean isAsc){

        int comparaCount = 0;//统计比较次数
        int swapCount = 0;//统计交换次数

        Person p1,p2;

        for(int i=0;i<list.size();i++){

            for(int j=0;j<list.size()-1-i;j++){//注意：此处与listSort1不同
                p1 = (Person)list.get(j);   //此处与listSort1不同
                p2 = (Person)list.get(j+1); //此处与listSort1不同

                comparaCount++;
                if(!(isAsc^(p1.getAge()>p2.getAge()))){ //非运算，非真即假
                    swap(list,j,j+1);//相邻位置对象交换
                    swapCount++;
                }

            }
        }

        //若使用统计比较数comparaCount和统计交换次数swapCount
        //要改成固定方式生成对象，针对同一组对象进行比较，
        // 否则随机生成，前后没有可比性
         System.out.println("listSort2===>comparaCount:"+comparaCount+"||swapCount:"+swapCount);

    }

    /**
     * 对list进行排序:冒泡排序 ,对排序算法第二次优化
     *
     * <从后往前>，相邻对象两两比较，，
     * 与listSort2相比,换了比较起点位置，其实从前和从后开始都一样，多一个写法而已
     * 关键在于，一轮比较过后，没有交换对象动作，侧不再进行后续比较
     *
     * @param list
     */
    public void listSort3(List<Person> list,boolean isAsc){

        int comparaCount = 0;//统计比较次数
        int swapCount = 0;//统计交换次数
        boolean flag = true;
        Person p1,p2;

        for(int i=0;(i<list.size())&&flag;i++){

            flag = false; //如果一轮下来，没有交换的，说明当前顺序已经正确，无须继续后的比较了。

            for(int j=list.size()-1;j>i;j--){
                p1 = (Person)list.get(j);
                p2 = (Person)list.get(j-1);

                comparaCount++;
                if(!(isAsc^(p1.getAge()<p2.getAge()))){ //非运算，非真即假
                    flag = true;
                    swap(list,j,j-1);
                    swapCount++;
                }

            }
        }

        //若使用统计比较数comparaCount和统计交换次数swapCount
        //要改成固定方式生成对象，针对同一组对象进行比较，
        // 否则随机生成，前后没有可比性
         System.out.println("listSort3===>comparaCount:"+comparaCount+"||swapCount:"+swapCount);

    }



    public static void main(String [] args) throws InvocationTargetException, IllegalAccessException {

        MyPersonListSortTest_bubble m = new MyPersonListSortTest_bubble();

        //排序isAsc:true 升序，false:降序
        boolean  isAsc = true;

        List list = m.getList();
        System.out.println("==========排序前=========");
        m.printList(m.getList());

        List list1 = m.getList();
        m.listSort1(list1, isAsc); //排序isAsc:true 升序，false:降序
        System.out.println("listSort1==========排序后=========");
        m.printList(list1);

        List list2 = m.getList();
        m.listSort2(list2, isAsc); //排序isAsc:true 升序，false:降序
        System.out.println("listSort2==========排序后=========");
        m.printList(list2);

        List list3 = m.getList();
        m.listSort3(list3, isAsc); //排序isAsc:true 升序，false:降序
        System.out.println("listSort3==========排序后=========");
        m.printList(list3);

    }
}