数据结构-3.数组数据结构

2020-06-19 本文已影响0人爱吃火锅的金先生

1. 属性

（1）一个数组就是一系列的插槽，每一个插槽都包含一个元素（值或对象）

（2）每个插槽都有一个固定的索引，这些索引是连续的整数

（3）一个数组的长度就是插槽的个数，长度是在创建这个数组的时候就固定的

（4）使用索引可以有效地访问每个插槽，每次访问的时间是 O(1)

（5）排序数组：如果数组中的元素按照升序排列，即每个元素小于或等于其右侧的元素，这个数组就是被排序好的数组

对于数字，x is less than y，意味着 x 在数值上小于 y

对于字符串，x is less than y，意味着 x 在字典上位于 y 前面，比如 bat 小于 bath，又都小于 bay

compareable 接口

comparable 接口中必须被实现的方法是 compareTo 方法

2. 数组中的方法

comparable 接口中的 compareTo 方法

如果一个类实现了 comparable 接口，那它必须实现其中的 compareTo 方法，String 和 Integer 中自带的 compareTo 方法，就是实现自这个类

二分法查找元素索引

a 为需要查找元素的数组，key 为想要查找的值

（1）如果数组中含有这个值，那么直接返回其索引

（2）如果数组中不含有这个值，那么这个值的索引为 “ - （元素应该插入的位置 + 1） ”，

int arr [] =newint[]{1,3,4,5,8,9};

Arrays.sort(arr);

int index1 = Arrays.binarySearch(arr,6);

6 不在数组中，取代 8 称为新的索引为 4 的元素，所以，返回值为 -(4 + 1) 即为 -5

int index2 = Arrays.binarySearch(arr,4);

4 在数组中，返回 4 的索引 2

int index3 = Arrays.binarySearch(arr,0);

0 不在数组中，取代 1 称为新的索引为 0 的元素，所以，返回值为 -(0 + 1) 即为 -1

int index4 = Arrays.binarySearch(arr,10);

10 不在数组中，应插在 9 之后，成为索引为 6 的元素，所以，返回值为 -(6 + 1) 即为 -7

注意：还有一种 4 参数的二分法查找索引法

binarySearch(Object[] a, int fromIdex, int toIndex, Object Key)

a 为需要查找元素的数组，fromIndex 为查找起始的索引（包含在内），toIndex 为查找结束的索引（不包含在内），Key 为需要查找的元素

（1）如果范围中包含该元素，直接返回其索引

（2）如果范围中不包含该元素，返回值为 “ - （元素应该插入的位置 + 1） ”

int arr [] =newint[]{1,3,4,5,8,9};

Arrays.sort(arr);

int index5 = Arrays.binarySearch(arr,1, 4, 6);

6 不在范围中，应插在 5 后面，成为新的 4 索引元素，所以，返回值为 -（4 + 1），即为 -5

int index6 = Arrays.binarySearch(arr,1, 4, 4);

4 在范围中，返回其索引 2

int index7 = Arrays.binarySearch(arr,1, 4 ,2);

2 不在范围中，应插在 3 前面，成为新的 1 索引元素，所以，返回值为 -（1 + 1），即为 -2

int index8 = Arrays.binarySearch(arr,1, 3, 10);

10 不在范围中，应插在 4 后面，成为新的 3 索引元素，所以，返回值为 -（3 + 1），即为 -4

int index9 = Arrays.binarySearch(arr,1, 3, 0);

0 不在范围中，应插在 3 前面，成为新的 1 索引元素，所以，返回值为 -（1 + 1），即为 -2

注意：由于在查找时，使用的是二分法，是从中间开始查找，所以如果出现相同元素，不同索引时，查找该元素时，会返回更接近中间的索引值

复制数组生成新长度的数组

original 为原数组，newLength 为新数组的长度

int[] original = new int[] {1,2,3,4,5}

int[] newArray = Arrays.copyOf(original,5)

则 newArray 为 1，2，3，4，5

int[] newArray = Arrays.copyOf(original,3)

则 newArray 为 1，2，3

int newArray = Arrays.copyOf(original,10)

则 newArray 为 1，2，3，4，5，0，0，0，0，0

不生成新数组，排序数组

前者中 a 为需要排序的整数数组，排序后的数组元素升序排列

结果是 0，1，2，3，4，5，6，7，8，9

注意：还有一种进阶版排序 sort(int[] a, int fromIndex, int toIndex)

只对 fromIndex 起始索引到 toIndex 结束索引中间的元素进行排序，包括起始索引，不包括结束索引

结果是 7，8，9，2，3，4，1，0，6，5

后者是对泛型进行特定顺序排序，既可为升序，也可为降序

继承 comparator 接口，并重写里面的类，使小于返回正数，大于返回负数

通过新的自定义比较器，实现反向排序数组，结果为 9，8，7，6，5，4，3，2，1，0

3. 插入 insertion

将插入索引后的元素，依次先后平移一个索引

我们假设 n = right - left + 1 为数组的长度

其中，第 1 步是将索引从 ins 到 right - 1 的元素复制到 ins + 1 到 right，其 copy 的最多次数为 n - 1 - 0 次，最少次数为 0 次，其平均次数为 $\frac{n - 1}{2}$ 次，第 2 步是将插入元素复制到插入索引处，复制了 1 次

总共平均复制 $\frac{n-1}{2}+1= \frac{n}{2}+\frac{1}{2} \approx \frac{n}{2}$ 次，时间复杂度为 O(n)

4. 删除 deletion

删除指定索引位置的元素，将后面的元素依次向前移动

同理，第 1 步平均复制 $\frac{n-1}{2}$ 次，第二步无需复制，总共平均复制 $\frac{n-1}{2}=\frac{n}{2}-\frac{1}{2} \approx \frac{n}{2}$ 次，时间复杂度为 O(n)

5. 搜索 searching

（1）线性：

线性搜索算法

我们假设 n = right - left + 1 为数组的长度

最快查找，即第一次就查找成功，需要查找 1 次

最慢查找，即最后依次才查找成功，或是遍历整个数组后没查找到，返回了 null，需要查找 n 次

平均查找次数 $\frac{n+1}{2}$ $\approx \frac{n}{2}$ 次，时间复杂度为 O(n)

（2）二分法：

首先，二分法查找法必须应用在排序好的数组之上

二分法搜索算法

由于其多次查找增长时间不是线性的，所以不能用求平均值方法来计算

其最大查找次数为 $floor(\log_2 n) +1$ $\approx \log_2 n$ 次时间，时间复杂度为 O(logn)

总结：

数组查找算法的复杂度

6. 融合 merging

给定两个排序好的数组，创建第三条排序好的数组包含前两个数组中的所有元素

思路：比较两个数组最左边的元素，哪个元素较小，就放进第三个数组中

数组排序方法

通过计算复制次数来确定时间复杂度：假设 n1 和 n2 分别是 a1 和 a2 的长度，a1 和 a2 中的每一个元素都复制了一次，复制到 a3 中，所以，复制的次数是 n = n1 + n2

时间复杂度为 O(n)

通过计算比较次数来确定时间复杂度：

融合的数组为 0 1 2 3 4

5 6 7 8 9 10

这是需要比较次数最少的情况，需要比较 5 次，融合部分融合后的长度是 10

融合的数组为 0 2 4 6 8

1 3 5 7 9 11

这是需要比较次数最多的情况，需要比较 9 次，融合部分融合后的长度是 10

假设需要融合部分融合后的长度是 n，至多需要比较 n - 1 次，所以时间复杂度为 O(n)

等差数列：

等差数列的求和方式 1，2，3，4，5，……，n

一共有 n 个数，因为是线性排列的，所以其平均数是 $\frac{n+1}{2}$ $=\frac{(n-1)+2}{2}$ ，所以和为 $\frac{n(n+1)}{2}$

7. 排序 sorting

现在给出一个没有排序的数组，重新安排其中的元素，使其达到升序排列

这是一个重要的算法，因为排序后的数组能更有效地查找元素和与其他数组融合

下面将介绍能够实现排序的多种算法：

（1）选择排序 selection sort

思路：找到数组中的最小元素，将其交换到最左边的插槽，重复此操作，每次忽略最左侧的插槽（因为它已经排序好了）

选择排序法

通过计算比较次数来分析时间复杂度：

令 n = right - left + 1 为数组的长度

第 1 个元素，需要和其他 n - 1 个元素进行比较，比较过后，将其放在最左侧，并在以后的比较中忽略它

第 2 个元素，需要和其他 n - 2 个元素进行比较，比较过后，将其放在最左侧，并在以后的比较中忽略它

最后一个元素，只和它自己比较 1 次

比较的次数为 (n - 1) + (n - 2) + (n - 3) + …… + 2 + 1 = $\frac{n^2 }{2}$ 次

时间复杂度为 $O(n^2)$

选择算法的基本实现框架

下面是一个例子：

选择算法的实现

最终的输出结果

注意：对许多问题需要进行分解并解决，对与困难的问题，将其分解为多个简单的问题，并逐步解决，最终将其组成最后的答案，在这过程中自然而然就要用到递归算法

（2）融合排序 merge sort

思路：将数组分成两个相同长度的子数组

分别将子数组排序

融合排序好的数组

融合排序法

融合排序法就是分步解决问题迭代组合答案的典型

通过计算比较次数来计算时间复杂度：

令 n = right - left + 1 为数组的长度

假设排序一个长度为 m 的数组所需要的比较次数为 comps(m)

那么对两个长度为 $\frac{n}{2}$ 的数组进行排序的比较次数为 2comps( $\frac{n}{2}$ )

两个长度为 $\frac{n}{2}$ 的数组，融合部分融合后的长度为 n，则至多需要比较 n - 1 次

因此，一共需要比较的次数是

comps(n) = 2 comps( $\frac{n}{2}$ ) + n - 1 (if n > 1)

comps(n) = 0 (if n <= 1)

如何计算 comps(n) 呢？

c(n) = 2 c( $\frac{n}{2}$ ) + n - 1 ---------------------------------------------------------------------------------- 1

=> c( $\frac{n}{2}$ ) = 2 c( $\frac{n}{4}$ ) + $\frac{n}{2}$ - 1 => c(n) = 4 c( $\frac{n}{4}$ ) + 2 n - 3 ------------------------------- 2

=> c( $\frac{n}{4}$ ) = 4 c( $\frac{n}{8}$ ) + $\frac{n}{4}$ - 1 => c(n) = 8 c( $\frac{n}{8}$ ) + 3 n -7 -------------------------------- 3

=> c(n) = $2^m c(\frac{n}{2^m }) + mn - (2^m - 1)$ --------------------------------------------------- m

取特殊值，令 $2^m = n$ ，则 $m = \log_2 n$ ，代入 m 式

=> c(n) = n c(1) + n $\log_2 n$ - n + 1

c(1) = 0 代入上式

=> c(n) = n $\log_2 n$ - n + 1

则时间复杂度为 $O(\log_2 n)$ ，此外，由于用到了新的数组，空间复杂度是 O(n)