java数据结构和算法

java java数据结构和算法
创建时间:
阅读:
  1. 一 .冒泡算法
    1. 1.核心思想
    2. 2.原理理解
    3. 3.代码实现
  2. 二.选择排序算法
    1. 1.核心思想
    2. 2.原理理解
    3. 3.代码实现
  3. 三.插入排序算法
    1. 1.核心思想
    2. 2.原理理解
    3. 3.代码实现
  4. 四.对象排序算法
    1. 1.新建一个对象类
    2. 2.添加比较方法
    3. 3.测试比较方法
  5. 五.栈
    1. 1.核心思想
    2. 2.原理理解
    3. 3.代码实现

一 .冒泡算法

1.核心思想

比较两个元素，如果前一个比后一个大则进行交换，经过对每个元素的比较，最后将最大的元素设置成最后一个元素，重复该操作，最后形成一个从小到大的排序。

2.原理理解

例如：
有数组里面有4个数，则冒 3轮就可以实现排序。 
第一轮      数据比较 3次
第二轮        数据比较 2次
第三轮       数据比较 1次

3.代码实现

public class BubblingTest {
    private int index = 0;
    private long[] arr = null;
    public BubblingTest(){
        if(arr==null){
            arr = new long[50];
        }
    }
    public void insert(int value){
        arr[index] = value;
        index++;
    }
    public void display(){
        for(int i=0;i<index;i++){
            System.out.print(arr[i]+",");
        }
        System.out.println(arr.toString());
    }
    public void bubblingSort(){
        long temp = 0L;
        for(int i=0;i<index-1;i++){    // 轮数
            for(int j=0;j<index-i-1;j++){     //比较次数
                if(arr[j]>arr[j+1]){
                     temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        BubblingTest test = new BubblingTest();
        test.insert(10);
        test.insert(12);
        test.insert(1);
        test.insert(20);
        test.bubblingSort();
        test.display();
    }
}

二.选择排序算法

1.核心思想

扫描所有的元素，得到最小的元素，并将最小的元素与左边第一个元素进行交换，再次扫描出第一位置的所有元素，得到最小的元素，与左边第二个元素进行交换，一次类推。

2.原理理解

例如：
有数组里面有4个数，则选择 3轮就可以实现排序。 
轮数    首位数下标    比较数首位下标    数据总数
第一轮    0    1    4
第二轮    1    2    3
第三轮    2    3    2

3.代码实现

public class SelectTest {
    private long[] arr = null;
    private int index = 0;
    public SelectTest(){
        if(arr == null){
            arr = new long[20];
        }
    }
    public void insert(int value){
        arr[index] = value;
        index++;
    }
    public void display(){
        for(int i=0;i<index;i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }
    public void selectSort(){

        for(int i=0;i<index-1;i++){//选择几轮
            int k = i;//记录下标
            for(int j=i+1;j<index;j++){ // 选最小的记录
                if(arr[k]>arr[j]){
                    k = j;//记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(k!=i){ //交换a[i]和a[k]
                long temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
    }
    public static void main(String[] args) {
        SelectTest test = new SelectTest();
        test.insert(12);
        test.insert(2);
        test.insert(32);
        test.insert(17);
        test.insert(52);
        test.display();
        test.selectSort();
        test.display();
    }
}

三.插入排序算法

1.核心思想

抽出一个元素，在其前面的元素中找到合适的位置进行插入。

2.原理理解

例如：
有数组里面有4个数，则插入 3轮就可以实现排序。 
轮数    选择数下标    待比较首位数下标    待比较数据总数
第一轮    1    0    1
第二轮    2    1    2
第三轮    3    2    3

3.代码实现

public class InsertTest {
    private static long[] arr = null;
    private int index;
    public void insert(int value){
        arr[index] = value;
        index++;
    }
    public void display(){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public void insertSort(){
        for(int i=1;i<arr.length;i++){ //插入几轮

            long temp = arr[i];
            for(int j=i-1;j>=0 ;j--){//待比较数据个数，和首位数据下标
                if(arr[j]>temp){
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        arr = new long[4];   //4位数比较
        InsertTest test = new InsertTest();
        test.insert(10);
        test.insert(12);
        test.insert(1);
        test.insert(20);
        test.display();
        test.insertSort();
        test.display();
    }
}

四.对象排序算法

1.新建一个对象类

public class Student {
    private String name;
    private String sex;
    private int age;
    private String stuNumber;
    public Student(String name, String sex, int age, String stuNumber) {
        super();
        this.name = name;
        this.sex = sex;
        this.age = age;
        this.stuNumber = stuNumber;
    }
    public String getStuNumber() {
        return stuNumber;
    }
    public void setStuNumber(String stuNumber) {
        this.stuNumber = stuNumber;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getSex() {
        return sex;
    }
    public void setSex(String sex) {
        this.sex = sex;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "ObjectTest [name=" + name + ", sex=" + sex + ", age=" + age + ", stuNumber=" + stuNumber + "]";
    }

}

2.添加比较方法

public class StudentSort {
    private Student[] students = null;
    private int index;
    public StudentSort(int value){
        students = new Student[value];
    }
    public void insert(Student stu){
        students[index] = stu;
        index++;
    }
    public void display(){
        for(int i=0;i<index;i++){
            System.out.println(students[i].toString());
        }
    }
    /**
     * name冒泡排序
     */
    public void bubblingSortByName(){
        for(int i=0;i<students.length-1;i++){
            Student stemp = null;
            for(int j=0;j<students.length-1-i;j++){
                if(students[j].getName().compareTo(students[j+1].getName())>0){
                    stemp = students[j];
                    students[j] = students[j+1];
                    students[j+1] = stemp;
                }
            }
        }
    }
    /**
     * name插入排序
     */
    public void insertSortByName(){
        for(int i=1;i<students.length;i++){
            Student insertTemp = students[i];
            for(int j=i-1;j>=0;j--){
                if(students[j].getName().compareTo(insertTemp.getName())>0){
                    students[j+1]=students[j];
                    students[j] = insertTemp;
                }
            }
        }
    }
    /**
     * name 选择排序
     */
    public void selectSortByName(){
        for(int i=0;i<students.length-1;i++){
            int tempIndex = i;
            for(int j=i;j<students.length-1;j++){
                if(students[j].getName().compareTo(students[j+1].getName())>0){
                    tempIndex = j+1;
                }
            }
            if(tempIndex!=i){
                Student min = students[tempIndex];
                students[tempIndex] = students[i];
                students[i] = min;
            }
        }
    }
}

3.测试比较方法

public class ObjectTest {
    public static void main(String[] args) {
        Student stu = new Student("zhansan", "man", 12, "122201");
        Student stu1 = new Student("lisi", "man", 14, "122203");
        Student stu2 = new Student("wangwu", "woman", 18, "122205");
        Student stu3 = new Student("zhaoliu", "woman", 13, "122202");
        StudentSort sort = new StudentSort(4);
        sort.insert(stu);
        sort.insert(stu1);
        sort.insert(stu2);
        sort.insert(stu3);
        sort.display();
//        sort.bubblingSortByName();
//        sort.insertSortByName();
        sort.selectSortByName();
        System.out.println("排序后");
        sort.display();
    }
}

五.栈

1.核心思想

栈只允许访问一个数据项，也就是最后插入的数据项。只有移除了这个数据项，才能访问倒数第二个插入的数据项。

2.原理理解

栈里面的数据可以看成是一个数组，栈里能存元素的最大个数用maxSize表示，栈顶位置用top表示。

3.代码实现

public class MyStack {
    private int maxSize;
    private long[] arr;
    private int top;
    public MyStack(int value){
        maxSize = value;
        arr = new long[maxSize];
        top = -1;
    }
    //压入数据
    public void push(long value){
        top++;
        arr[top] = value;
    }
    //弹出数据
    public long pop(){
        return arr[top--]; 
    }
    //访问栈顶数据
    public long peek(){
        return arr[top];
    }
    //栈是否为空
    public boolean isEmpty(){
        return (top==-1);
    }
    //栈是否满了
    public boolean isFull(){
        return (top==maxSize-1);
    }

}
public class StackTest {
    public static void main(String[] args) {
        MyStack stack = new MyStack(10);
        stack.push(12);
        stack.push(22);
        stack.push(52);
        stack.push(16);
        stack.push(13);
        while(!stack.isEmpty()){
            System.out.println("栈顶数据"+stack.peek());
            System.out.println(stack.pop());
        }
    }
}

文章标题:java数据结构和算法

发布时间:2020-01-15, 17:13:18

最后更新:2020-01-15, 17:13:19

©2019 chen wei