真正的数据结构和算法【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代码
数据结构
数组 栈 树 适用于数据库应用中作数据记录
栈和队列
- 通常情况作为程序员的工具来应用
- 受限访问 你想拿底下的，需要先拿后进的。
- 更加抽象(主要通过接口进行定义)
栈就是一组记录，表现形式是先进后出。
底层可以用链表来实现，还可以用数组来实现。
/**
* 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();
}
}