真正的数据结构和算法【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();
}
}