真正的数据结构和算法【2】

存储对象的数组和大O表示法

存储对象的数组

1.创建一个类比如Person 姓名 年龄
2.创建一个存储对象的数组类 查找 删除 显示所有
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package array;

/**
 * @author Zen
 * @version $Id: Person.java, v 0.1 2019/05/09 13:51 Zen Exp $
 */
public class Person {
    public String name;
    public int age;
    public Person(String pname,int page){
        name = pname;
        age = page;
    }

    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;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package array;


/**
 * @author Zen
 * @version $Id: PersonArray.java, v 0.1 2019/05/09 13:53 Zen Exp $
 */
public class PersonArray {
    Person [] arr ;
    int size;

    public PersonArray(int maxsize){
        arr = new Person[maxsize];
    }

    public void find(String sname){
        for(int i = 0;i <size ; i++){
            if (arr[i].getName().equals(sname)){
                System.out.println( arr[i].toString());
                break;
            }
        }
    }

    public void insert(String name,int age){
        arr[size] = new Person(name,age);
        size++;
    }

    public void delete(String sname){
        for(int i = 0 ; i < size;i++){
            if(arr[i].getName().equals(sname)){
                for(int j = i; j<size -1;j++){
                    arr[j] = arr[j+1];
                }
                size--;
            }
        }
    }

    public void displayAll(){
        for(int i = 0 ;i < size;i++){
            System.out.println(arr[i].toString());
        }
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package array;

/**
 * @author Zen
 * @version $Id: PersonArrayApp.java, v 0.1 2019/05/09 14:12 Zen Exp $
 */
public class PersonArrayApp {
    public static void main(String[] args) {
        PersonArray personArray = new PersonArray(100);
        System.out.println("插入开始");
        personArray.insert("zhansan",23);
        personArray.displayAll();
        personArray.insert("lisi",24);
        personArray.displayAll();
        personArray.insert("wangwu",25);
        personArray.displayAll();
        personArray.insert("zhaoliu",26);
        personArray.displayAll();
        personArray.insert("xiaoqi",27);
        personArray.displayAll();
        System.out.println("查找开始");
        String findkey = "lisi";
        personArray.find(findkey);
        System.out.println("删除开始");
        personArray.delete("lisi");
        personArray.displayAll();
    }
}

大O表示法
粗略度量计算机算法效率的方法

线性查找 O(n) 还可以
二分查找 O(log N) 良好
无序数组的插入 O(1) 优秀
有序数组的插入 O(N) 还可以
有序数组的删除 O(N) 还可以

冒泡排序O(n^2)

排序:数据需要有序,按不同的要求排序,不一样的方式排效率不同。

冒泡排序规则:【第一次拿出最大的 双重循环 像泡泡一样不断的上浮】 交换次数多,循环次数多

1.比较两个对象
2.如果左边的大于右边,则调换位置
3.向右移动一个位置继续与下一个排序

在写冒泡排序的时候,第一次写的有点问题,外层内层都从零开始。
每一次都找出了最大的,
所以外层循环遍历了一次,相应就会减少一次,不需要继续循环。
内循环的话,就是每次循环相邻的两个数,比较大小,调换顺序,每次找出最大值。

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package sort;

/**
 * @author Zen
 * @version $Id: BubbleSort.java, v 0.1 2019/05/09 14:42 Zen Exp $
 */
public class BubbleSortArray {
    int [] arr ;
    int size = 0;
    public BubbleSortArray(int maxsize){
        arr = new int[maxsize];
    }
    public BubbleSortArray(int[] array){
        arr = array;
        size= array.length;
    }
    public void insert(int value){
        arr[size++] = value;
    }
    public void bubbleSort(){
        for(int i = size ;i > 0; i--){
            for(int j = 0 ;j < size -1 ;j++){
                if(arr[j]>arr[j+1]){
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    displayAll();
                }
            }
        }
    }

    public void displayAll(){
        for(int i = 0;i< size;i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package sort;

/**
 * @author Zen
 * @version $Id: BubbleSortArrayApp.java, v 0.1 2019/05/09 14:53 Zen Exp $
 */
public class BubbleSortArrayApp {
    public static void main(String[] args) {
        int [] arr = new int[]{32,33,21,55,44,66,1};
        BubbleSortArray bubbleSortArray = new BubbleSortArray(arr);
        bubbleSortArray.displayAll();
        bubbleSortArray.bubbleSort();
        bubbleSortArray.displayAll();
    }
}

选择排序 交换次数少,循环次数和冒泡排序一样。
扫描一遍,找出最小的。
外层控制循环遍数,
内存查找最小元素,交换位置。

/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package sort;

/**
 * @author Zen
 * @version $Id: SelectSortArray.java, v 0.1 2019/05/09 15:20 Zen Exp $
 */
public class SelectSortArray {
    int [] arr;
    int size = 0;
    public SelectSortArray(int maxsize){
        arr = new int[maxsize];
    }
    public SelectSortArray(int[] array){
        arr = array;
        size = array.length;
    }

    /**
     * 相比冒泡排序,需要注意下标的交换.
     * 选择排序和冒泡排序最大的差距是在交换次数比较少
     */
    public void selectSort(){
        int min ;
        int index ;
        for(int i = 0; i <size ;i++){
            min = arr[i];
            index = i;
            for(int j = i; j <size ;j++){
                if(arr[j] < min){
                    index = j;
                    min = arr[j];
                }
            }

            int temp;
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;

            displayAll();
        }
    }
    public void insert(int value){
        arr[size++] = value;
    }
    public void displayAll(){
        for(int i = 0;i< size;i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }

}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package sort;

/**
 * @author Zen
 * @version 3: SelectSortArrayApp.java, v 0.1 2019/05/09 16:00 Zen Exp $
 */
public class SelectSortArrayApp {
    public static void main(String[] args) {
        int [] arr = new int[]{32,33,21,55,44,66,1};
        SelectSortArray selectSortArray = new SelectSortArray(arr);
        selectSortArray.displayAll();
        selectSortArray.selectSort();
    }
}

本文链接:

https://heyzen.club/index.php/Coder/290.html
1 + 4 =
快来做第一个评论的人吧~