public static int find(int[] array, int aim) {// 初始化left = 最左侧, right = 最右侧int left = 0;int right = array.length - 1;// 当left > right则表示遍历完成while (left <= right) {// 获取中间的值int middle = (left + right) / 2;int middleValue = array[middle];if (middleValue == aim) {// 已经找到目标return middle;} else if (middleValue < aim) {// 目标在middle的右侧，重置leftleft = middle + 1;} else {// 目标在middle的左侧，重置rightright = middle - 1;}}return -1;
}

str1.compareTo(str2)

import java.util.ArrayList;
import java.util.Comparator;public class Address {public static int find(ArrayList<String> array, String aim) {// 初始化left = 最左侧, right = 最右侧int left = 0;int right = array.size();// 当left > right则表示遍历完成while (left <= right) {// 获取中间的值int middle = (left + right) / 2;String middleValue = array.get(middle);if (middleValue.equals(aim)) {// 已经找到目标return middle;} else if (middleValue.compareTo(aim) > 0) {// 目标在middle的左侧，重置rightright = middle - 1;} else {// 目标在middle的右侧，重置leftleft = middle + 1;}}return -1;}public static void main(String[] args) {ArrayList<String> array = new ArrayList<>();array.add("Allen");array.add("Emma");array.add("James");array.add("Jeanne");array.add("Kelly");array.add("Kevin");array.add("Mary");array.add("Natasha");array.add("Olivia");array.add("Rose");int result1 = find(array, "Kelly");if (result1 == -1) {System.out.println("Kelly 不存在名单中");} else {System.out.println("Kelly 存在名单中，位置是 " + result1);}int result2 = find(array, "Edith");if (result2 == -1) {System.out.println("Edith 不存在名单中");} else {System.out.println("Edith 存在名单中，位置是 " + result2);}}
}

数字数组为：[0, 8, 2, 3, 5, 6, 2, 2, 10, 8]重复数字为：[8, 2]

public static ArrayList<Integer> repeat(int[] array) {ArrayList<Integer> result = new ArrayList<>();for(int i = 0; i < array.length; i++){// 以此判断i位置元素和后面j位置元素是否相等for(int j = i + 1; j < array.length; j++){if(array[i] == array[j]){// 如果之前result没有，则进行添加if(!result.contains(array[i])){result.add(array[i]);}}}}return result;
}

exists[0] = 1

exists[8] = 1

public static ArrayList<Integer> repeat(int[] array) {ArrayList<Integer> result = new ArrayList<>();int[] exists = new int[11];for (int i = 0; i < array.length; i++) {int value = array[i];// 只有当前位置已经为1，标示重复，并且输出，>1情况则不输出了if (exists[value] == 1) {result.add(value);}// 用exists标示记录exists[value]++;}return result;
}

数组

计算机内存管理

计算机的程序都是运行在内存中。

内存的工作原理

我们可以简单的将内存当做寄存柜。假设我们去游泳，需要将东西先寄存起来，寄存处有几个大箱子，每个箱子都有很多抽屉。

每个抽屉里可以放一样东西，如果你有 4 样东西，就需要放在 4 个抽屉里。 每个抽屉都有自己的编号，方便你查找和记录。 接下来，你就去游泳了，当你结束的时候，再将 4 个抽屉里面的东西带走。

这其实就是计算机内存的工作原理。

每个抽屉都可以当做内存的一个存储单元，而抽屉编号可以当做每个存储单元的内存地址。

为什么连续两个方格内存地址差 8？

因为我们现在电脑基本是 64 位，64 位表示内存存储最小使用单位为64个bit，也就是8个byte。

数组 - 存储和读取

为什么数组的索引从 0 开始？

数组是计算机中最基础的数据结构，每个编程语言中基本都有数组。

数组存储

要回答上面这个问题，首先得明白数组到底是怎么在内存中存储的。

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

• 线性数据结构：表示数组中数据都是按前后这种线性顺序排列的。 
• 相同数据类型：数组中的每个值的数据类型都相同。

连续内存空间

举个生活中的例子，现在有 4 个人去电影院看电影，希望坐靠前的位置并挨着坐在一排

那如果变成 5 个人了呢？那就选择第三排。

如果把每个座位当做一块内存空间，那边连续位置就相当于数组的连续内存空间。

数组读取

理解了数组的内存存储，接下来看看如何获取数组某个索引下的值？

每个数组都有对应的内存地址，将其称作为数组开始地址 --- start_address。

数组在定义的时候已经确定每个数组元素的数据类型，也就是知道每个元素需要的内存空间大小，称为 --- item_size。

那么数组里每个元素内存地址s都能被计算出来：

// 第一个元素地址
start_address// 第二个元素地址
start_address + item_size * 1// 第三个元素地址
start_address + item_size * 2

第 N 个元素地址公式如下:

// 第N个元素地址
start_address + item_size * (N - 1)

从这个公式可以得到两点信息：

• 数组的索引访问的时间复杂度是O(1)
• 内存地址的计算规则决定开始地址为start_address + item_size * 0，在计算机中为了方便位置的计算，所以数组索引从 0 开始。

补充：获取数组长度

public class ArrayLengthExample {public static void main(String[] args) {int[] array = {1, 2, 3, 4, 5};int length = array.length;System.out.println("数组的长度为: " + length);}}

数组获取索引值

   public class ArrayIndexAccess {public static void main(String[] args) {int[] array = {10, 20, 30, 40};int index = 2;int element = array[index];System.out.println("索引 " + index + " 处的元素是: " + element);}}

数组 - 插入和删除

数组插入

往数组里面插入一个元素的速度，取决于你需要把它插入到哪个位置上。

假设为周末的事情做规划，暂定规划如下

eat breakfast  // 吃早饭
shopping       // 购物
have lunch     // 吃午饭
have dinner    // 吃晚饭

如果把安排设置一个类，预留明天 20 个任务，那么代码如下：

public class Schedule {String[] array = new String[20];private int size = 0;// 内置4个安排public Schedule(){array[0] = "eat breakfast";array[1] = "shopping";array[2] = "have lunch";array[3] = "have dinner";this.size = 4;}public void print(){for(int i = 0; i < this.size; i++){System.out.print(this.array[i] + " ");}}public static void main(String[] args) {Schedule schedule = new Schedule();schedule.print();}
}

代码中内置了明天 4 个安排任务，并且设置任务数量size为 4。

尾部插入

如果现在突然想在吃完饭之后去看场电影（watch movie）：

public class Schedule {String[] array = new String[20];private int size = 0;// 内置4个安排public Schedule(){array[0] = "eat breakfast";array[1] = "shopping";array[2] = "have lunch";array[3] = "have dinner";this.size = 4;}public void add(String task){this.array[this.size] = task;this.size++;}public void print(){for(int i = 0; i < this.size; i++){System.out.print(this.array[i] + " ");}}public static void main(String[] args) {Schedule schedule = new Schedule();schedule.add("watch movie");schedule.print();}
}

在尾部插入元素很容易计算，尾部插入元素内存地址为

start_address + item_size * n  // n 为当前数组的个数

中间插入

如果希望在下午吃了午饭后喝一个下午茶（afternoon tea），那应该怎么处理呢？

我们知道，需要在数组中间部分插入数据，但是为了保证数组的顺序和连续的内存空间，插入地方后面部分数据，需要往后依次移动，如图所示：

一共需要几步呢？

1. 移动watch movie
2. 移动have dinner
3. 插入afternoon tea

如果插入在开始地方，则需要 N 步。

因此平均步数为 (1 + 2 + 3 + ... + N) / N 最终时间复杂度为O(N)，也就是数组的插入时间复杂度为线性时间复杂度。

可以新增一个insert3Position在索引位置为 3 的地方，插入一项任务：

// 第三个位置插入
public void insert3Position(String task) {// 索引值为3的地方int index = 3;// 第一步：从右侧开始依次右移for (int i = this.size - 1; i >= index; i--) {this.array[i + 1] = this.array[i];}// 第二步：插入元素this.array[index] = task;// 调整sizethis.size++;
}

空间不够

上面我们讨论都是正常情况，如果空间不够了呢？我们再次回顾下电影院的例子：

当我们有 4 个朋友的时候，当前位置是满足要求的。如果突然多来了一个朋友，位置不够了，这个时候需要重新找寻满足 5 个人位置的空间。

这和数组空间不够的原理是一样的，需要通过 3 步完成：

如上图所示，我们一起移动到下一排：

1. 开辟新的内存空间
2. 复制原来的数组到新的内存空间
3. 再进行插入操作

如果所有的内存空间都不足以存储到数组，这个时候系统就会抛出异常 --- Out Of Memory 内存不够。

举例：

public class YKDArrayList {// 此处需要声明一个数组，作为底层存储int[] array = new int[20];int size = 0;public YKDArrayList() {}// 获取数组的长度public int size() {return this.size;}// 数组获取某个索引值public int get(int index) {return this.array[index];}// 添加元素在末尾 public void add(int element) {//相当于调用传入this.sizethis.add(this.size, element);}// 添加元素在中间public void add(int index, int element) {if (index < 0 || index > this.size) {return;}// 支持扩容this.judgeMemory(this.size + 1);// 元素依次右移for (int i = this.size - 1; i >= index; i--) {this.array[i + 1] = this.array[i];}// 插入元素this.array[index] = element;// 调整sizethis.size++;}// 删除元素public void remove(int index) {if (index < 0 || index > this.size - 1) {return;}// 元素依次左移for (int i = index; i < this.size - 1; i++) {this.array[i] = this.array[i + 1];}// 删除最后一个元素this.array[this.size - 1] = 0;// 调整sizethis.size--;}private void judgeMemory(int size) {// 如果内存不满足，则需要扩容if (size > this.array.length) {// 申明两倍空间int[] newArray = new int[this.array.length * 2];// 拷贝操作this.copy(this.array, newArray);// 新数组赋值给原数组this.array = newArray;}}// 拷贝操作private void copy(int[] source, int[] aim) {for (int i = 0; i < source.length; i++) {aim[i] = source[i];}}public static void main(String[] args) {YKDArrayList ykdArrayList = new YKDArrayList();ykdArrayList.add(1);ykdArrayList.add(2);ykdArrayList.add(3);ykdArrayList.add(4);ykdArrayList.add(0, 5);ykdArrayList.remove(3);}
}

数组删除

数组的删除操作和插入操作刚好相反。

如果是删除尾部元素，则直接删除；

如果是删除中间元素通过两步执行：

1. 删除中间元素
2. 元素右侧其他元素依次左移

因此我们可以得知数组删除的时间复杂度也为O(N)。

总结

数组优势：数组的查询数据特别快，时间复杂度是 O(1)

数组劣势：数组的插入和删除比较慢，时间复杂度是 O(N) 数组需要连续内存空间，并且会申请额外的内存空间便于其扩展，这种数据结构对内存要求比较高，利用率低。

因为这些优势和劣势，我们在高频查询，低频插入和删除的情况下，可以选择数组作为底层数据结构。同时我们知道 Java 中的ArrayList，实际上在底层就是利用数组实现的。

入门排序算法

冒泡排序

一个数组变成一个有序数组需要排序算法。

冒泡排序

冒泡排序是最基础，最经典的排序算法。

如果水里有很多气泡，这些气泡都会慢慢升起，冒出水面。 并且越大的气泡，升起的速度越快，这就是冒泡的原理：对于一个数组，每一次循环让最大的元素冒泡到最后面。

核心规则有 4 点：

1. 指向数组中两个相邻的元素（最开始是数组的头两个元素），并且比较他们的大小。
2. 如果前者比后者大，则交换他们的位置。
3. 如果后者比前者大，则不交换。
4. 然后依次后移，每次循环将最大元素移动最后一个位置。

实战案例

假设有一个数组为9, 2, 4, 7, 5, 3，希望将其变成自小而大的排列。

代码实现

// 冒泡排序
public static void bubbleSort(int[] array) {// 1. 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次for (int i = 0; i < array.length; i++) {// 2. 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了for (int j = 0; j < array.length - i - 1; j++) {//3. 交换元素if (array[j] > array[j + 1]) {//倒序把>改为<即可int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}}}
}

• 如果要将整个数组都排好序，需要冒泡数组个数次。
• 特别注意结束条件，array.length - i - 1。第一次遍历需要到数组结束为止，这时候已经得到最大元素9，并且放在数组末尾。第二次只需要遍历到倒数第二个元素即可。
• 交换数组中的两个元素使用擂台法：

1. 用临时变量存储第一个变量值
2. 将第二个变量赋值给第一个变量
3. 将临时变量赋值给第二个变量

最终看到排序以后的结果，从代码中可以看出比较的次数为:

N + (N - 1) + ... + 2 + 1 = (N^2 + N) / 2

最坏的情况下每次比较都需要交换，交换的次数也为(N^2 + N) / 2 所以整体的步数介于(N^2 + N) / 2和(N^2 + N)之间。用大 O 记法，最终的结果为O(N^2)。

选择排序

重点在选择，每次在剩余数组中，选择最大或者最小的一个，放在数组的一端。

import java.util.Arrays;
public class Sort {// 选择排序public static void selectSort(int[] array) {// 遍历N次，每次选择数组剩余元素中最大的元素for (int i = 0; i < array.length; i++) {// 暂时把第一个元素当做最大元素，并且记录最大元素的索引int maxIndex = 0;int max = array[0];// 注意 j 从 索引1 开始，到 array.length - i 截止for (int j = 1; j < array.length - i; j++) {// 如果元素大于当前最大值，则替换 max，maxIndexif (array[j] > max) {max = array[j];maxIndex = j;}}// 交换最大值元素 和 数组末尾元素int temp = array[maxIndex];array[maxIndex] = array[array.length - i - 1];array[array.length - i - 1] = temp;}}public static void main(String[] args) {int[] array = {9, 2, 4, 7, 5, 3};// Arrays.toString 可以方便打印数组内容System.out.println(Arrays.toString(array));selectSort(array);System.out.println(Arrays.toString(array));}
}

核心规则有 4 点：

1. 利用两个变量，一个存储当前最大值，一个存储当前最大值所在的索引。
2. 依次比较后面的元素，如果发现比当前最大值大，则更新最大值，并且更新最大值所在的索引。
3. 直到遍历结束，将最大值放在数组的最右边，也就是交换最右边元素和当前最大值元素。
4. 重复上面的步骤

时间复杂度

时间复杂度和冒泡排序一样，执行次数如下

N + (N - 1) + ... + 2 + 1

最终的结果为O(N^2)。

冒泡排序 vs 选择排序

虽然两个排序算法的时间复杂度都为O(N^2)，但很明显能感受到选择排序更快一点点。因为冒泡需要频繁的交换相邻两个元素，而选择排序每次遍历只需要交换一次，所以选择排序真实情况速度比冒泡排序快一倍。

插入排序

重点在插入，每次抽离一个元素当做临时元素，依次比较和移动之后的其他元素，最终将这个临时元素插入对应的位置。

import java.util.Arrays;
public class Sort {// 插入排序public static void insertSort(int[] array) {// 从倒数第二位开始，遍历到底0位，遍历 N-1 次for (int i = array.length - 2; i >= 0; i--) {// 存储当前抽离的元素int temp = array[i];// 从抽离元素的右侧开始遍历int j = i + 1;while (j <= array.length - 1) {// 如果某个元素，小于临时元素，则这个元素左移if (array[j] < temp) {array[j - 1] = array[j];} else {// 如果大于，则直接将临时元素插入，然后退出循环。array[j - 1] = temp;break;}j++;}// 处理到达尾部的情况if (j == array.length) {array[j - 1] = temp;}}}public static void main(String[] args) {int[] array = {9, 2, 4, 7, 5, 3};// Arrays.toString 可以方便打印数组内容System.out.println(Arrays.toString(array));insertSort(array);System.out.println(Arrays.toString(array));}
}

核心规则有 4 点：

1. 在第一轮，抽离数组末尾倒数第二个元素，作为临时元素。
2. 用临时元素与数组后面的元素进行对比：如果 后面的元素 值小于临时元素，则 后面的元素 左移。
3. 如果后面的元素大于临时元素，或者已经移动到数组末尾，则将临时元素插入当前的空隙中。
4. 重复上面步骤，完成排序。

此处的核心逻辑已经不是选择最大元素了，而是通过每次迭代，将部分元素排好序，以达到最终全部排序的效果。

时间复杂度

最好的情况

如果所有的数组元素本身就是升序排列，每次迭代不需要进行移动，所以时间复杂度是 O(N)

最坏的情况

如果所以的数组元素都是按降序排列，每次迭代每次比较都需要移动，在这种情况下。比较的步数为 O((N^2 - N) / 2) ，移动的步数为 O((N^2 - N) / 2) 。因此最差的情况为 O(N^2 - N) ，忽略常数为 O(N^2) 。

冒泡排序 vs 选择排序 vs 插入排序

冒泡排序相比较而言肯定是较差的。 选择排序和插入排序得分情况而定，如果原始数组本身有很多元素按希望的顺序排好序，则选择插入排序(如上面最好极限情况，接近 O(N))，否则选择选择排序。