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

插入排序(O(n^2))
效率比冒泡排序和选择排序高

从下标1开始,以下标0值进行比较,
其中没有交换,只有复制。

0.0 为啥不直接新建一个数组,有序的插入啊。
因为在学插入排序啊。

我写的插入排序v1.0感觉是有问题的,这三重循环了,时间复杂度就上去了。

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

/**
 * @author Zen
 * @version 1.0: InsertSortArray.java, v 0.1 2019/05/09 16:33 Zen Exp $
 */
public class InsertSortArray {
    int [] arr;
    int size;

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

    public InsertSortArray(int[] array){
        arr = array;
        size = array.length;
    }
    public void insertSort(){
        for(int i = 1 ; i < size;i++){
            for(int j = 0;j < i; j++ ){
                if(arr[j] > arr[i]){
                    int temp;
                    temp = arr[i];
                    for(int k = i ; k > j; k--){
                        arr[k] = arr[k-1];
                    }
                    arr[j] = temp;
                }
            }
            displayAll();
        }
    }
    public void displayAll(){
        for(int i = 0;i< size;i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }


}

插入排序v2.0 好像这样的插入排序才是效率稍微高一点的。



/**
 * 外层循环控制哪个数成了插入数
 * 内存循环插入数与已排序数组从大到小比较,看是否要交换位置。
 */
public void insertSort() {
    for(int out = 1; out < size ;out ++){
        int temp = arr[out];
        for(int in = out -1; in >= 0;in --){
            if(temp < arr[in]){
                swap(in,in+1);
            }
            displayAll();
        }
    }
}
public void swap(int i,int j){
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

视频中的插入排序的写法
我写的步骤就多了很多了。
感觉比我写的简单很多,看来我还是需要慢慢的练习,不断优化啊。

public void insertSort() {
    for(int out = 1; out < size ;out ++){
        int temp = arr[out];
        int in = out;
        while(in > 0 && a[in-1] >= temp){
            a[in] = a[in - 1];
            in --;
        }
        a[in] = temp;
    }
}

对象数组的插入排序,对对象进行排序。

/**
 * 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();
    }
}

  • 不同的结构类型介绍
  • 栈介绍
  • 表示栈Java代码

数据结构
数组 栈 树 适用于数据库应用中作数据记录

栈和队列

  1. 通常情况作为程序员的工具来应用
  2. 受限访问 你想拿底下的,需要先拿后进的。
  3. 更加抽象(主要通过接口进行定义)

栈就是一组记录,表现形式是先进后出。
底层可以用链表来实现,还可以用数组来实现。

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

/**
 * @author Zen
 * @version 1.0: SimpleArrayStack.java, v 0.1 2019/05/11 16:16 Zen Exp $
 */
public class SimpleArrayStack {
    int [] stack;
    int top;//数组下标
    int maxsize;
    public SimpleArrayStack(int m){
        maxsize = m;
        stack = new int[maxsize];
        top = -1;
    }

    /**
     * 进栈
     * @param value
     */
    public void push(int value){
        stack[++top] = value;
    }

    /**
     * 出栈
     * @return
     */
    public int pop(){
        return stack[top--];
    }
    public int peek(){
        return stack[top];
    }
    public boolean isEmpty(){
        return top == -1;
    }
    public boolean isFull(){
        return top == maxsize -1;
    }
    public void displayAll(){
        for(int i = 0 ;i <=top ; i++){
            System.out.println(stack[i]);
        }
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package stack;

/**
 * @author Zen
 * @version 1.0: SimpleArrayStackApp.java, v 0.1 2019/05/11 16:23 Zen Exp $
 */
public class SimpleArrayStackApp {
    public static void main(String[] args) {
        SimpleArrayStack s = new SimpleArrayStack(100);
        s.push(10);
        s.push(20);
        s.push(30);
        s.push(40);
        s.push(50);
        s.push(60);
        s.push(70);
        s.push(80);
        s.push(90);
        s.displayAll();
        s.pop();
        s.pop();
        s.displayAll();

    }
}

栈的应用实例

  • 单词逆序
  • 分隔符匹配
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package stack;

/**
 * @author Zen
 * @version 1.0: CharStack.java, v 0.1 2019/05/11 16:40 Zen Exp $
 * @function 字节数组栈
 */
public class CharStack {
    char []  arr;
    int top;
    int maxize;
    public CharStack(int m){
        maxize = m;
        arr = new char[maxize];
        top = -1;
    }
    public void push(char value){
        arr[++top] = value;
    }
    public char pop(){
        return arr[top--];
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package stack;

/**
 * @author Zen
 * @version 1.0: Reverse.java, v 0.1 2019/05/11 16:44 Zen Exp $
 */
public class Reverse {
    String input;
    String output = "";
    CharStack cs;

    public Reverse(String s){
        input = s;
    }

    public void reverse(){
        cs = new CharStack(100);
        for(int i = 0 ; i < input.length(); i++){
            System.out.println(input.charAt(i));
         cs.push(input.charAt(i));
        }
        while(cs.top >= 0){
            output += cs.pop();
        }
        System.out.println("Reverse:"+output);
    }
}
/**
 * heyzen.club Inc.
 * Copyright (c) 2018-2019 All Rights Reserved.
 */
package stack;

/**
 * @author Zen
 * @version 1.0: ReverseApp.java, v 0.1 2019/05/11 16:53 Zen Exp $
 */
public class ReverseApp {
    public static void main(String[] args) {
        Reverse reverse = new Reverse("ABDCEFGHI");
        reverse.reverse();
    }
}

分隔符匹配
这个写的很简单,实际上还是需要更多的控制的。

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

/**
 * @author Zen
 * @version 1.0: ChecBracket.java, v 0.1 2019/05/11 17:09 Zen Exp $
 */
public class CheckBracket {
    String input;
    CharStack cs ;
    public CheckBracket(String s){
        input = s;
    }
    public void check(){
        cs = new CharStack(100);
        for(int i = 0 ; i < input.length(); i++){
            char a = input.charAt(i);
            if(a == '{' || a =='('||a == '['  ){
               cs.push(a);
            }
            if(a == '}'&& cs.pop()!= '{'){
                System.out.println("死啦死啦的有");
                break;
            }
            if(a == ']'&& cs.pop()!= '['){
                System.out.println("死啦死啦的有");
                break;
            }
            if(a == ')'&& cs.pop()!= ')'){
                System.out.println("死啦死啦的有");
                break;
            }
        }


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

import java.util.Scanner;

/**
 * @author Zen
 * @version 1.0: CheckBracketApp.java, v 0.1 2019/05/11 17:21 Zen Exp $
 */
public class CheckBracketApp {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        CheckBracket cb = new CheckBracket(s);
        cb.check();
    }
}

本文链接:

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