数据结构-数组

数组是使用最广泛的基础数据结构。数组是存放在连续内存空间上的相同类型数据的集合,可以方便的通过数字索引的方式获取到索引所对应的数据。需要注意的是数组的索引都是从0开始计算的。下图就是长度为3的字符数组的例子。

内存地址100110021003
数组元素‘a’‘b’‘c’
数组索引012

Java 使用数组

Java中的数组声明很简单:

1
2
3
4
5
// 定义时初始化
int[] array = new int[]{0,0,0};
// 通过长度定义, 元素会被初始化为默认值
// int的默认值是0
int[] array = new int[3];

数组提供了一个length参数,可以获取数组的长度。注意一旦创建数组的长度就不能再变化,只能通过重建新的数组扩容。访问数组元素通过索引方式访问和更新。

1
2
3
4
int[] array = new int[3];
int arrayLength = array.length;
int head = array[0];
array[1] = 3;

数组的查找和删除就稍微麻烦一点。对于查找,需要遍历数组,将目标值和每个元素对比。

1
2
3
4
5
6
7
8
int search(int[] arr,int target) {
for (int i = 0; i < arr.length; i++) {
if(arr[i] == target){
return i;
}
}
throw new IllegalArgumentException("not found");
}

对于删除,如果不知道索引的情况下,删除需要遍历数组,如果知道索引,可以通过指定索引的方式删除。但是这还没有结束,数组删除完值后,会留下一个空洞,如果不想有空洞存在,需要将后面的元素依次向前移动。

有序数组

假设一个数组,其元素按照值的固定顺序排序(升序或降序),那么这种数组被称为有序数组。在实际的算法使用中常常会对数组先进行排序,然后在进行处理。下面我们来介绍下一些排序算法。

排序算法

算法代码位置

简单排序算法

常见的简单排序算法有冒泡排序、选择排序、插入排序。

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] arr) {
int temp = 0;
for (int i = arr.length - 1; i > 0; i--) {
// 每次需要排序的长度
for (int j = 0; j < i; j++) {
// 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) { // 此处是大于,相等的情况不交换位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

在相邻元素相等时,它们并不会交换位置,所以,冒泡排序是稳定排序。在数据完全有序的时候展现出最优时间复杂度,为 O(n)O(n)。其他情况下,几乎总是 O(n2)O(n^2)。因此,算法在数据基本有序的情况下,性能最好。

要使算法在最佳情况下有 O(n)O(n) 复杂度,需要做一些改进,增加一个swap的标志,当前一轮没有进行交换时,说明数组已经有序,没有必要再进行下一轮的循环了,直接退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bubbleSort(int[] arr) {
int temp = 0;
boolean swap;
for (int i = arr.length - 1; i > 0; i--) {
// 每次需要排序的长度
swap=false;
for (int j = 0; j < i; j++) {
// 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap=true;
}
}
if (swap==false){
break;
}
}
}

选择排序

  1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] arr) {
int temp, min = 0;
for (int i = 0; i < arr.length - 1; i++) {
min = i;
// 循环查找最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}

用数组实现(就地排序)的选择排序是不稳定的,用链表实现(或者新开辟数组空间)的选择排序是稳定的。不过,一般提到排序算法时,大家往往会默认是数组实现(就地排序),所以选择排序是不稳定的。

1
2
3
2a 2b 1 3
选择排序后 1 2b 2a 3
显然是不稳定的

插入排序

  1. 把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。
  2. 从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
  3. 重复上述过程直到最后一个元素被插入有序子数组中。
1
2
3
4
5
6
7
8
9
10
11
public static void insertionSort(int[] arr){
for (int i=1; i<arr.length; ++i){
int value = arr[i];
int position=i;
while (position>0 && arr[position-1]>value){
arr[position] = arr[position-1];
position--;
}
arr[position] = value;
}
}

由于只需要找到不大于当前数的位置而并不需要交换,因此,直接插入排序是稳定的排序方法。

归并排序

  • 递归法(Top-down)
    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤3直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 迭代法(Bottom-up)
    1. 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个子序列,排序后每个序列包含两/一个元素
    2. 若此时子序列数不是1个则将上述序列再次归并,形成ceil(n/4)个子序列,每个序列包含四/三个元素
    3. 重复步骤2,直到所有元素排序完毕,即子序列数为1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 递归法
public static void mergeSort(int[] arr){
int[] temp =new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
//当left==right的时,已经不需要再划分了
if (left<right){
int middle = (left+right)/2;
internalMergeSort(arr, temp, left, middle); //左子数组
internalMergeSort(arr, temp, middle+1, right); //右子数组
mergeSortedArray(arr, temp, left, middle, right); //合并两个子数组
}
}
// 合并两个有序子序列
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while (i<=middle && j<=right){
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <=middle){
temp[k++] = arr[i++];
}
while ( j<=right){
temp[k++] = arr[j++];
}
//把数据复制回原数组
for (i=0; i<k; ++i){
arr[left+i] = temp[i];
}
}

因为我们在遇到相等的数据的时候必然是按子序列顺序“抄写”到辅助数组上的,所以,归并排序同样是稳定算法。归并排序在数据量比较大的时候也有较为出色的表现(效率上),但是,其空间复杂度O(n)使得在数据量特别大的时候(例如,1千万数据)几乎不可接受。而且,考虑到有的机器内存本身就比较小,因此,采用归并排序一定要注意。

参考