数据结构

1. 数组：数组是最基本的数据结构，是一张表，线性表，除了第一个和最后一个之外，其余的元素都是首位相连的。
2. 链表
3. 树
4. 图

1. 先完成需求要求的功能
2. 根据程序运行的结果进行优化处理
3. 代码重构
4. 提高效率

在一个数组中查找某一个数字

int [] arr = new int[]{1,58,46,33,10,5,-8};
Scanner scanner = new Scanner(System.in);
System.out.println("请输入一个数: ");
int num = scanner.nextInt();
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == num) {
        System.out.println("你要找的数是 "+num+",在目标数组中的下标是"+i);
        break;
    }
    if (i==arr.length-1) {
        System.out.println("你要找的数是 "+num+",在目标数组中是不存在的");
    }
}

用二分法在数组中查找一个数字

public static void main(String[] args) {
/*
    查找算法：
    二分法算法
    如果要使用二分法查找数字，前提是这个数组必须有排列顺序
 */

    int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7,9};
    Scanner scanner = new Scanner(System.in);
    System.out.println("请输入要查找的数字：");
    int target = scanner.nextInt();

    int left = 0; // 最左边的下标
    int right = arr.length - 1; // 最右边的下标
    boolean flag = false;
    if (target < arr[left] || target > arr[right]) {
        System.out.println(target + "在目标数组中不存在");
    } else {
        while (left <= right) {
            if (target == arr[(left + right) / 2 ]) {
                System.out.println("found");
                flag = true;
                break;
            } else {
                if (target < arr[(left + right) / 2]) {
                    right = (left + right) / 2 -1;
                } else {
                    left = (left + right) / 2+1 ;
                }
            }
        }
        if (flag) {
            System.out.println("你找到了"+target+"，在数组中下标是"+((left + right) / 2 ));
        } else {
            System.out.println(target + "在目标数组中不存在");
        }
    }
}

二分法解析
定义left和right为左角标和右角标
每次把targe和 数组中间的值 判断大小
然后移动left或right角标

排序算法

1.冒泡排序
2.快速排序
3.插入排序
4.选择排序
5.希尔排序
6.堆排序
7.归并排序
8.桶排序

冒泡排序

/*
     需求：将一个数组从小到大排序
     思路分析：
        冒泡排序需要两层for循环
        外层for循环控制的是需要各个数之间比较几轮
        内层for循环控制的是每个数的真正比较
 */
int [] arr = new int[]{1,58,46,33,10,5,-8};
for (int i = 0; i < arr.length-1; i++) {
    for (int j = 0; j < arr.length-i-1; j++) {
        if (arr[j] > arr[j+1]) {
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}
for (int i : arr) {
    System.out.print(i+" ");
}

冒泡排序分析

每一次做循环 判断 当前a[i]与下一位a[i+1]的大小关系
找出小的 然后放在二者的前面 即换位
每次执行完一次循环后，都会将最大值放在数组的末尾
每次做完循环，最后一位便不需要再判断，所以j的次数可以-1

选择排序

int [] arr = new int[]{0,10,9,8,7,6,5,4,3,2,1};
for (int i = 0; i < arr.length-1; i++) {
    int minIndex = i;
    for (int j = i+1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }

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

    for (int k : arr) {
        System.out.print(k+" ");
    }
    System.out.println();
}
for (int i : arr) {
    System.out.print(i+" ");
}

选择排序分析

每一次做循环 判断 假设当前a[i]为最小值
并把i存入 minIndex变量中
每次循环（当前位置的后面开始 即i+1）
找到其中最小的值 并把角标记录给minIndex
最后将a[i]赋值为a[minIndex]

插入排序

int [] arr = new int[]{10,5,2,18,30,50,100,-3};

for (int i = 0; i < arr.length-1; i++) {
    int preIndex = i;
    int current = arr[i+1];

    while (preIndex>=0 && arr[preIndex]>current){
        arr[preIndex+1]=arr[preIndex];
        preIndex--;
    }
    arr[preIndex+1]=current;
    for (int k : arr) {
        System.out.print(k+" ");
    }
    System.out.println();
}

插入排序分析

{5,4,3,2,1}指针preIndex从第一个位置往后遍历
假设第一位是最小的，若arr[preIndex+1] > arr[preIndex]
则将arr[preIndex]往前移动至下标preIndex的位置

// 创建一个等长的数组
// 把当前的数组的每一个元素倒着添加到新数组里
// 然后将新数组赋值给老数组
int[] arr = new int[]{1,2,3,4,5};
int [] newArr = new int[arr.length];

for (int i = 0; i < arr.length; i++) {
    newArr[i]=arr[arr.length-i-1];
}
arr = newArr; // 将老数组赋值为新数组
for (int i : arr) {
    System.out.print(i+" ");
}

public static void main(String[] args) {
    int [] nums = new int[]{3,4,6};
    int [] temp = new int[6];
    for (int i = 0; i < nums.length; i++) {
        temp[i]=nums[i];

    }
    nums=temp;
    for (int i : nums) {
        System.out.println(i+" ");
    }
}

扩容方式分析

新建temp[]数组，遍历原数组nums[]
将nuts[]的元素存入新数组temp[]内
循环结束后 nums=temp 即可完成 "扩容"