数据结构和算法-2-数组

• 上一周只写了个数据结构和算法的开篇，主要是工作比较忙，app要发新版本，又对现有项目的客服sdk进行了升级和封装，周末又准备了一场内推的面试，到现在刚闲下来。
• 这一篇主要写一下数组，数组可以说是我们平时应用最广泛的数据存储结构了，而且使用非常简单，非常适合作为介绍数据结构的起步点。

普通数组

相信每个Android或java开发者都已经非常熟悉了，这里也就不再多说了。

有序数组 & 二分法查找

• 二分查找也称折半查找，是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
• 有序数组及二分查找实现如下

public class OrderedArray {
    private long[] array;
    private int mElems;

    public OrderedArray(int max) {
        array = new long[max];
        mElems = 0;
    }

    public int size() {
        return mElems;
    }

    /**
     * 二分法查找
     * <p>
     * 数组越大，二分查找的优势就越明显
     * <p>
     * 公式：2的n次幂>=arr.size, n为查找所需次数 ,2的n次幂为n次查找可覆盖的范围
     * 即 范围是次数的指数，次数是范围的对数
     *
     * @param searchValue 要查找的值
     * @return 查找结果，该值对应的角标，-1表示未找到
     */
    public int find(long searchValue) {
        int lowerIndex = 0;
        int upperIndex = mElems - 1;
        int currIndex;
        while (true) {
            currIndex = (lowerIndex + upperIndex) / 2;
            System.out.println("array[" + currIndex + "]=" + array[currIndex]);
            if (lowerIndex > upperIndex) {
                return -1;
            } else if (array[currIndex] == searchValue) {
                return currIndex;
            } else if (array[currIndex] < searchValue) {
                lowerIndex = currIndex + 1;
            } else {
                upperIndex = currIndex - 1;
            }
        }
    }

    /**
     * 使用递归实现二分法查找
     *
     * 代码更简洁,但效率稍差
     */
    public int find(long searchValue, int fromIndex, int toIndex) {
        System.out.println("searchValue:" + searchValue + "_fromIndex:" + fromIndex + "_toIndex:" + toIndex);
        int currentIndex = (fromIndex + toIndex) / 2;
        if (array[currentIndex] == searchValue)
            return currentIndex;
        else if (fromIndex > toIndex)
            return -1;
        else if (array[currentIndex] < searchValue)
            return find(searchValue, currentIndex + 1, toIndex);
        else
            return find(searchValue, fromIndex, currentIndex - 1);
    }

    /**
     * 插入数据
     *
     * @param value
     */
    public void insert(long value) {
        int i;
        for (i = 0; i < mElems; i++) {
            if (array[i] > value)
                break;
        }
        for (int j = mElems; j > i; j--) {
            array[j] = array[j - 1];
        }
        array[i] = value;
        mElems++;
    }

    /**
     * 删除
     *
     * @param value
     * @return
     */
    public boolean delete(long value) {
        int i = find(value);
        if (i == -1) {
            return false;
        } else {
            for (int j = i; j < mElems; j++) {
                array[j] = array[j + 1];
            }
            mElems--;
            return true;
        }
    }

    /**
     * 打印数组
     */
    public void display() {
        System.out.print("OrderedArray: ");
        for (int i = 0; i < mElems; i++) {
            System.out.print("[" + i + "]-->" + array[i] + "  ");
        }
        System.out.println();

    }
}

可以在java的main方法中调用下面方法进行测试

private static void testOrderedArray() {
        int[] arr = {
                31, 33, 35, 37, 39, 41,
                11, 13, 15, 17, 19,
                1, 3, 5, 7, 9,
                21, 23, 25, 27, 29,
        };
        //初始化数组
        OrderedArray orderedArray = new OrderedArray(100);
        //插入
        for (int item : arr) {
            orderedArray.insert(item);
        }
        //size
        System.out.println("orderedArray.size=" + orderedArray.size());
        //打印
        orderedArray.display();
        //查找
        System.out.print("请输入要查找的数字：");
        Scanner sc = new Scanner(System.in);
        if (sc.hasNext()) {
            String param = sc.next();
//            int resultIndex = orderedArray.find(Long.parseLong(param));
            int resultIndex = orderedArray.find(Long.parseLong(param), 0, orderedArray.size() - 1);
            System.out.println("resultIndex:" + resultIndex);
        }

        //删除
        System.out.print("请输入要删除的数字：");
        Scanner sc2 = new Scanner(System.in);
        if (sc2.hasNext()) {
            String param = sc2.next();
            boolean result = orderedArray.delete(Long.parseLong(param));
            System.out.println("result:" + result);
        }
        //size
        System.out.println("orderedArray.size=" + orderedArray.size());
        //打印
        orderedArray.display();
    }

为什么不用数组表示一切？

为什么不用数组进行所有的数据存储？因为数组还是又许多缺点和不足的

1. 无序数组插入快，查找和删除慢；有序数组查找快，插入和删除慢；没有一个最优的解决方案。
2. 数组创建后大小是固定的，而程序开发中往往不知道一共有多少项数据，容易触发数组角标越界的异常。