数据结构_数组，链表

JI,XIAOYONG...大约 2 分钟

前言

本文介绍了数组、链表等数据结构。

设定所有排序：小 → 大。

数组

数组（array）是一组具有相同类型元素的集合，用一段连续的内存来保存。使用下标来访问保存的元素，如a[0]。

数组是一种数据存储结构。

int a[] = new int[10];

数组大小固定，对指定下标元素读写快 O(1)，但是查找慢 O(N)，删除元素慢 O(N)。

有序数组

在每次插入的时候对元素进行排序，就得到有序数组。

有序数组查找快 O(LogN)，但插入慢 O(N)，删除元素慢 O(N)。

有序数组插入：

fun insertSort(key: Int) {
    if (size >= sortArr.size) {
        return
    }
    if (size == 0) {
        sortArr[size++] = key
        return
    }
    var insertIndex = ++size - 1
    while (key < sortArr[insertIndex - 1]) {
        sortArr[insertIndex] = sortArr[insertIndex - 1]
        insertIndex--
        if (insertIndex == 0) {
            break
        }
    }
    sortArr[insertIndex] = key
}

在有序数组要找到某个元素 t 可以使用二分查找，其思想是：

选取一个中间值 n 将当前数组一分为二。
如果t==n那么查找结束，如果t<n,那么在右半部分数组查找，否则在左半部分数组查找。
重复步骤1,2，直到找到 n 或者数组已经不可再分（不存在 n），结束查找。

二分法查找：

fun dichotomy(array: IntArray, key: Int): Int {
    if (array.size < 2) {
        return -1
    }
    var centerIndex = array.size / 2
    var centerKey = array[centerIndex]
    return when {
        key == centerKey -> centerIndex
        key < centerKey -> dichotomy(array.copyOfRange(0, centerIndex), key)
        else -> dichotomy(array.copyOfRange(centerIndex - 1, array.size), key)
    }
}