数据结构-数组
数据结构-数组
数组是使用最广泛的基础数据结构。数组是存放在连续内存空间上的相同类型数据的集合,可以方便的通过数字索引的方式获取到索引所对应的数据。需要注意的是数组的索引都是从0开始计算的。下图就是长度为3的字符数组的例子。
内存地址 | 1001 | 1002 | 1003 |
---|---|---|---|
数组元素 | ‘a’ | ‘b’ | ‘c’ |
数组索引 | 0 | 1 | 2 |
Java 使用数组
Java中的数组声明很简单:
1 | // 定义时初始化 |
数组提供了一个length参数,可以获取数组的长度。注意一旦创建数组的长度就不能再变化,只能通过重建新的数组扩容。访问数组元素通过索引方式访问和更新。
1 | int[] array = new int[3]; |
数组的查找和删除就稍微麻烦一点。对于查找,需要遍历数组,将目标值和每个元素对比。
1 | int search(int[] arr,int target) { |
对于删除,如果不知道索引的情况下,删除需要遍历数组,如果知道索引,可以通过指定索引的方式删除。但是这还没有结束,数组删除完值后,会留下一个空洞
,如果不想有空洞
存在,需要将后面的元素依次向前移动。
有序数组
假设一个数组,其元素按照值的固定顺序排序(升序或降序),那么这种数组被称为有序数组。在实际的算法使用中常常会对数组先进行排序,然后在进行处理。下面我们来介绍下一些排序算法。
简单排序算法
常见的简单排序算法有冒泡排序、选择排序、插入排序。
冒泡排序
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤1~3,直到排序完成。
1 | public static void bubbleSort(int[] arr) { |
在相邻元素相等时,它们并不会交换位置,所以,冒泡排序是稳定排序。在数据完全有序的时候展现出最优时间复杂度,为$O(n)$。其他情况下,几乎总是$O(n^2)$。因此,算法在数据基本有序的情况下,性能最好。
要使算法在最佳情况下有$O(n)$复杂度,需要做一些改进,增加一个swap的标志,当前一轮没有进行交换时,说明数组已经有序,没有必要再进行下一轮的循环了,直接退出。
1 | public static void bubbleSort(int[] arr) { |
选择排序
- 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
1 | public static void selectionSort(int[] arr) { |
用数组实现(就地排序)的选择排序是不稳定的,用链表实现(或者新开辟数组空间)的选择排序是稳定的。不过,一般提到排序算法时,大家往往会默认是数组实现(就地排序),所以选择排序是不稳定的。
1 | 2a 2b 1 3 |
插入排序
- 把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
- 从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
- 重复上述过程直到最后一个元素被插入有序子数组中。
1 | public static void insertionSort(int[] arr){ |
由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是稳定的排序方法。
归并排序
- 递归法(Top-down)
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
- 迭代法(Bottom-up)
- 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个子序列,排序后每个序列包含两/一个元素
- 若此时子序列数不是1个则将上述序列再次归并,形成ceil(n/4)个子序列,每个序列包含四/三个元素
- 重复步骤2,直到所有元素排序完毕,即子序列数为1
1 | // 递归法 |
因为我们在遇到相等的数据的时候必然是按子序列顺序“抄写”到辅助数组上的,所以,归并排序同样是稳定算法。归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。