数据结构与算法

数组

package com.data.utils;

public class ArraysInfo {
    public static void main(String[] args) {
        MyArray arr = new MyArray(30);
        arr.addByOrder(34);
        arr.addByOrder(1);
        arr.addByOrder(32);
        arr.addByOrder(332);
        arr.addByOrder(77);
        arr.addByOrder(717);
        arr.addByOrder(7);
        arr.display();
        System.out.println(arr.binaryFind(77));
    }
}

/**
 * 自定义封装数组,类似于java中的数组,下面的逻辑没有考虑扩容机制
 */
class MyArray{

    private long[] arr;
    /**
     *有效数据长度
     */
    private int elements;

    public MyArray(){
        arr = new long[50];
    }

    public MyArray(int maxSize){
        arr = new long[maxSize];
    }

    /**
     * 添加数据
     * @param value
     */
    public void add(long value){
        arr[elements] = value;
        elements++;
    }

    /**
     * 显示数据
     */
    public void display(){
        System.out.print("[");
        for (int i = 0; i < elements; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.print("]");
    }

    /**
     * 查找数据-线性查找法
     * @param value
     * @return
     */
    public int search(long value){
        int i;
        for (i = 0; i < elements; i++) {
            if(arr[i] == value){
                break;
            }
        }
        if(i == elements){
            return  -1;
        }
        return i;
    }

    /**
     * 根据索引获取元素
     * @param index
     * @return
     */
    public long get(int index){
        if(index>=elements || index<0){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            return  arr[index];
        }
    }

    /**
     * 删除元素
     * @param index
     */
    public void delete(int index){
        if(index>=elements||index<0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            for (int i = index; i < elements; i++) {
                arr[i] = arr[i+1];
            }
            elements--;
        }
    }

    /**
     * 更新数据
     * @param index
     * @param value
     */
    public void update(int index,long value){
        if(index>=elements||index<0){
            throw new ArrayIndexOutOfBoundsException();
        }else {
            arr[index] = value;
        }
    }

    /**
     * 有序数组的添加方法，有序数组只需要修改添加方法即可
     * @param value
     */
    public void addByOrder(long value){
        int i;
        for (i = 0; i < elements; i++) {
            if (arr[i] > value) {
                break;
            }
        }
        for (int j = elements; j > i ; j--) {
            arr[j] = arr[j-1];
        }
        arr[i] = value;
        elements++;
    }


    /**
     * 有序数组的查找-二分查找法
     * @param value
     * @return
     */
    public int binaryFind(long value){
        int middle;
        int start = 0;
        int end = elements;

        while (true){
            middle = (start+end)/2;
            if(arr[middle] == value){
                return middle;
            }else if(end < start){
                return -1;
            }else{
                if(arr[middle]>value){
                    end = middle-1;
                }else{
                    start = middle+1;
                }
            }
        }
    }
}

简单排序

冒泡排序（BubbleSort）

/**
* 冒泡排序：相邻两个比较交换
* @param arr
 */
public static void bubbleSort(long[] arr){
    long temp = 0;
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        for (int j = len-1; j > i; j--) {
            if(arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
    show(arr,"冒泡");
}

public static void show(long[] arr,String str){
    StringBuilder sb = new StringBuilder(str+"[");
    for (int i = 0; i < arr.length; i++) {
        sb.append(arr[i]);
        if(i != arr.length-1){
            sb.append(",");
        }
    }
    sb.append("]");
    System.out.println(sb.toString());
}

选择排序

/**
 * 选择排序：选择未排序中最小的索引，然后交换
 * @param arr
 */
public static void selectionSort(long[] arr){
    int k = 0;
    long temp = 0;
    for (int i = 0; i < arr.length; i++) {
        k = i;
        for (int j = i+1; j < arr.length; j++) {
            if(arr[k]>arr[j]){
                k = j;
            }
        }
        if(k!=i){
            temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    show(arr,"选择");
}

插入排序

/**
 * 插入排序：每次排序前面已经有序，找到的一个比tmp大的交换
 * @param arr
 */
public static void insertSort(long[] arr){
    long temp = 0;
    for (int i = 1; i < arr.length; i++) {
        temp = arr[i];
        int j = i;
        while(j>0 && arr[j-1]>=temp){
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
    show(arr,"插入");
}

插入排序的比较次数仍然是n的平方，但在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点