数据结构-数组

发表于 更新于 分类于 ， 阅读次数： Changyan： 本文字数： 4.1k 阅读时长 ≈ 7 分钟

数据结构-数组

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

内存地址 1001 1002 1003
数组元素 ‘a’ ‘b’ ‘c’
数组索引 0 1 2

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^2)$。因此，算法在数据基本有序的情况下，性能最好。

要使算法在最佳情况下有$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千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

参考