`

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_SimpleSelection类:

 

 

package com.flg;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
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_SimpleSelection {

    /**
     * 获得要测试的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("张30",30));
        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));
        


        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进行排序:简单选择排序
     *
     * 简单选择排序就是通过n-i次比较,从n-i+1个记录中选出最小的记录,
     * 并和第i(1<=i<=n)个记录交换
     * 和冒泡相比,减少了比较次数和交换次数
     * 比较次数为:n-1+n-2+...1=n(n-1)/2次
     *
     * @param list
     */
    public void listSort1(List<Person> list,boolean isAsc){

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

               Person p1,p2;
               int i,j,min;

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

                   min = i;

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

                       comparaCount ++;//统计比较次数
                       if(!(isAsc^(p1.getAge()>p2.getAge()))){ //非运算,非真即假
                          min = j;
                       }
                   }

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




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

        MyPersonListSortTest_SimpleSelection m = new MyPersonListSortTest_SimpleSelection();

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

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

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



    }
}

 

过程分析帮助理解:

此方法的思想就是从i+1位置开始往后找出包括i位置在内的最小的值放到i的位置上。
此处用了一个中间变量min来记录本轮最小值的下标。

以下为伪代码,仅供帮助理解:

初始数组:
[30 6 9 12 18 16 20 3 27 30]

第一轮(指以i为轮次计数)
 i=0  min=0 此时list[min=0]=30
从j=i+1 也就是list[1]位置开始往后循环,
list[1]=6比list[min=0]=30小,所以让min=1,
此后j一直++,直到运行到list[7]=3比list[min=1]=6小,所以让min=7,
一轮下来只做一次交换,就是把最小的和i位置的交换,前提是i不是最小的,这样数组就变成
[3 6 9 12 18 16 20 30 27 30] 

第二轮
i=1 min=1  此时list[min=1]=6; 
从j=i+1=2 也就是list[2]=9的位置开始往后循环。
这一轮下来,最小值在i的位置上没变,所以不用替换位置。这样数组没变
[3 6 9 12 18 16 20 30 27 30 ]

... ... ...
... ... ...

以次类推,直到第8轮
i=7 list[min=7]=30
从j=i+1 也就是list[8]=27的位置开始往后循环,发现27比30小,所以让min=8
这一轮下来,数组变成
[3 6 9 12 18 16 20 27 30 30] 

第9轮没有变化

排序完毕

 

 

19
25
分享到:
评论
1 楼 FX夜归人 2012-07-30  
if(!(isAsc^(p1.getAge()>p2.getAge()))){ //非运算,非真即假  
    min = j;  
}


//  
if(!(isAsc && (p1.getAge() > p2.getAge()))){
    min = j;  
}

相关推荐

    数据结构与算法-Java语言版

    本书选择Java语言以面向对象的方式描述数据结构,还特别强调了封装和分解的信息隐藏原理。主要内容包括:面向对象编程的基本原理,判定算法效率的方法,堆栈、队列及其应用,对于多种递归的详细讨论,二叉树、B树、2...

    Java数据结构与算法-笔记-代码-课件-资料

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序...

    最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构

    最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构

    Java数据结构与算法编程基础全面系统教程

    JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...

    java数据结构与算法.pdf

    包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...

    数据结构与排序算法(JAVA版)

    这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!

    Java数据结构与算法

    介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的学习。

    数据结构与算法-java版

    数据结构与算法-java版 ...以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。

    Java数据结构和算法(第二版).zip

    《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...

    Java数据结构与算法概述-初级篇.docx

    数据结构-栈与队列,链表,递归,简单排序到高级排序的算法的详细笔记,本人根据视频学习进行的数据结构记录。适合入门算法学习初级篇

    java数据结构和算法

    java 数据结构和算法, 排序算法, 数组,链表,二叉树

    最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构

    最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构

    Java数据结构与算法中的源代码和applet - 站长下载

    书名:数据结构Java版 图书编号:2086963 出版社:清华大学 定价:118.0 ISBN:730213544 作者:(美)福特(Ford,W.H.),(美)托普(Topp,W.R.) 著,梁志敏 译 出版日期:2006-11-11 版次: 开本: 简介: 本书...

    lz4压缩算法java实现-LZ4-极快的压缩算法,排序算法数据结构 最快的排序算法

    lz4压缩算法java实现-LZ4-极快的压缩算法,排序算法数据结构 最快的排序算法

    java数据结构和算法.(第二版)

    《数据结构与算法》以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构...

    排序算法-数据结构 C Java

    随着科技的不断发展,计算机的应用领域越来越广,但由于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并...排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量,进而影响整个软件的性能。

    最快的排序算法 java最快的排序-在Java中对列表进行排序的最快方法,排序算法数据结构

    最快的排序算法 java最快的排序-在Java中对列表进行排序的最快方法,排序算法数据结构

    数据结构与算法-学习笔记 Java 版.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

Global site tag (gtag.js) - Google Analytics