# algorithm

**Repository Path**: shark-dynamics/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 常见的数据结构和算法及Java实现
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-08-15
- **Last Updated**: 2021-08-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#### 整理中... 

### 1. 基础数据结构部分解释

#### 1.1 顺序表
> 注意插入后，数据超过原有大小时的resize操作

```java
public void insert(int idx, int value) {
    if (idx < 0 || idx > bufferSize) {
        return;
    }

    if (bufferSize >= buffer.length) {
        resize();
    }

    for (int i = bufferSize -1; i >= idx; i--) {
        buffer[i+1] = buffer[i];
    }
    buffer[idx] = value;
    bufferSize++;
}

public void resize() {
    int[] buffer = new int[this.buffer.length*2];
    System.arraycopy(this.buffer, 0, buffer, 0, this.buffer.length);
    this.buffer = buffer;
}
```

#### 1.2 链表
> 头插法建表，数据是倒序。插入12345，输出54321
```java
public void createAtHead(SqList data) {
    head = new LinkList();
    data.visit(value -> {
        LinkList node = new LinkList();
        node.value = value;
        node.next = head.next;
        head.next = node;
        nodeSize++;
    });
}
```
> 尾插法建表，数据是正序。插入12345，输出12345
```java
public void createAtRear(SqList data) {
    head = new LinkList();
    rear = head;
    data.visit(value -> {
        LinkList node = new LinkList();
        node.value = value;
        rear.next = node;
        rear = node;
        nodeSize++;
    });
```

#### 1.3 双向链表
> 注意边界条件以及前后多个指针的指向，以及从后向前操作时，注意边界条件。  
> 头插法
```java
public void createAtHead(SqList data) {
    head = new DuLinkList();
    DuLinkList p = head;
    data.visit(value -> {
        DuLinkList node = new DuLinkList();
        node.value = value;
        node.next = p.next;
        node.prior = p;

        if (p.next != null) {
            p.next.prior = node;
        } else {
            rear = node;
        }
        p.next = node;
        nodeSize++;
    });
}

```

> 尾插法

```java
public void createAtRear(SqList data) {
    head = new DuLinkList();
    final DuLinkList[] ps = {head};
    data.visit(value -> {
        DuLinkList p = ps[0];
        DuLinkList node = new DuLinkList();
        node.value = value;
        node.next = p.next;
        node.prior = p;

        if (p.next != null) {
            p.next.prior = node;
        }
        p.next = node;

        ps[0] = node;
        rear = node;
        nodeSize++;
    });
}
```

> 双向链表的反向查找
```java
public int findValueInverse(int value) {
    DuLinkList node = rear;
    for (int i = 0; i < nodeSize; i++) {
        int cv = node.value;
        if (cv == value) {
            return i;
        }
        node = node.prior;
    }
    return kInvalid;
}
```

> 插入删除时的指针操作，如插入

```java
public boolean insert(int idx, int value) {
    if (idx < 0 || idx > nodeSize) {
        return false;
    }

    DuLinkList node = head;
    for (int i = 0; i < idx; i++) {
        node = node.next;
    }

    DuLinkList newNode = new DuLinkList();
    newNode.value = value;

    //注意以下几句
    newNode.next = node.next;
    newNode.prior = node;

    if (node.next != null) {
        node.next.prior = newNode;
    }
    node.next = newNode;

    if (idx == nodeSize) {
        rear = newNode;
    }
    nodeSize++;
    return true;
}
```

#### 1.4 顺序栈
> 注意出栈与获取栈顶元素的区别，获取栈顶元素，不弹出
```java
public int pop() {
    if (top == 0) {
        System.out.println("stack empty");
        return kInvalid;
    }
    int v = data[--top];
    data[top] = 0;
    return v;
}

public int getTop() {
    if (top == 0) {
        return kInvalid;
    }
    return data[top-1];
}
```

#### 1.5 环形队列
> 注意头尾指针的位置变化以及带来的计算问题，包括入队，出队，计算长度等

```java
public void enQueue(int value) {
    if ((rear+1)%buffer.length == front) {
        System.out.println("Queue full");
        return;
    }
    buffer[rear++] = value;
}

public int deQueue() {
    if (front == rear) {
        System.out.println("Queue empty");
        return kInvalid;
    }
    return buffer[front++];
}

public int length() {
    return (rear - front + buffer.length) % buffer.length;
}
```

#### 1.6 链表二叉树

> 结构
```java

public class LinkBT implements IPrintable {

    public int data;
    public LinkBT left;
    public LinkBT right;

}
```

> 前序创建二叉树
```java
public static LinkBT create(SqList data) {
    int v = data.at(count++);
    if (v == IStruct.kInvalid || v == '#') {
        return null;
    }

    LinkBT bt = new LinkBT();
    bt.data = v;
    bt.left = create(data);
    bt.right = create(data);
    return bt;
}
```

> 三种遍历递归实现
```java
public static void preOrderVisit(LinkBT bt, IDataCallback cb) {
    if (bt == null) {
        return;
    }
    cb.onDataCallback((char)bt.data);
    preOrderVisit(bt.left, cb);
    preOrderVisit(bt.right, cb);
}

public static void inOrderVisit(LinkBT bt, IDataCallback cb) {
    if (bt == null) {
        return;
    }
    inOrderVisit(bt.left, cb);
    cb.onDataCallback((char)bt.data);
    inOrderVisit(bt.right, cb);
}

public static void postOrderVisit(LinkBT bt, IDataCallback cb) {
    if (bt == null) {
        return;
    }
    postOrderVisit(bt.left, cb);
    postOrderVisit(bt.right, cb);
    cb.onDataCallback((char)bt.data);
}

```

> !!! 递归创建二叉树的要求 !!!  
> 需要将二叉树补齐到每个节点都是两个孩子，补空，以#代替，如下所示

```java
/**
    *                 A
    *                / \
    *             B      D
    *            /     /  \
    *         E       H    J
    *          \     / \
    *           L   M   I
    *
    *  Pre : A BEL DHMIJ
    *  In  : ELB A MHIDJ
    *  Post: LEB MIHJD A
    *                 A
    *                / \
    *             B      D
    *            /     /  \
    *         E       H    J
    *       /  \     / \  / \
    *      #    L   M   I#  #
    *          / \ /\  /\
    *         #  ## # # #
    */     
LinkBT bt = LinkBTAlg.create(new SqList(new int[]{'A', 'B', 'E', '#', 'L', '#', '#', '#', 'D', 'H', 'M', '#', '#', 'I', '#', '#', 'J', '#', '#'}));
bt.print("Create");
```

#### 1.7 完全二叉树（顺序存储）
> 因为完全二叉树的特性，第 i 个节点的左孩子时 2乘i，右孩子是 2乘i+1，所以可按此规则在数组中直接索引。

```java
public class SqBT implements IPrintable, IStruct<SqBT> {

    public int[] buffer;
    public int size;

    public SqBT(int capacity) {
        buffer = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            buffer[i] = kInvalid;
        }
        size = 0;
    }

    public void setValue(int idx, int value) {
        buffer[idx] = value;
        if (idx >= size) {
            size = idx+1;
        }
    }

    public int getValue(int idx) {
        return buffer[idx];
    }
}

```

> 以中序遍历为例，看其遍历操作
```java
public static void inOrderVisit(SqBT bt, int pos, IDataCallback cb) {
    int idx = pos - 1;
    int value = bt.getValue(idx);
    if (value == IStruct.kInvalid) {
        return;
    }

    inOrderVisit(bt, pos*2, cb);
    cb.onDataCallback((char)value);
    inOrderVisit(bt, pos*2+1, cb);
}

```

#### 1.8 堆，同样的结构可实现堆排序，优先队列
> 本质还是完全二叉树的应用，主要是其元素上浮，下沉等操作

```java
public void downAdjust() {
    for (int i = size/2; i > 0; i--) {
        int parentIndex = i;
        while (parentIndex < size-1) {

            int childLeft = 2 * parentIndex;
            int childRight = childLeft + 1;
            if (childLeft > size-1) {
                break;
            }

            int childLeftValue = buffer[childLeft];
            int childRightValue = kInvalid;
            if (childRight < size) {
                childRightValue = buffer[childRight];
            }

            boolean smallIsLeftChild = true;
            int minValue = childLeftValue;
            if (childRightValue != kInvalid) {
                minValue = Math.min(childLeftValue, childRightValue);
            }
            if (minValue == childRightValue) {
                smallIsLeftChild = false;
            }

            int exChildIdx = 0;
            if (smallIsLeftChild) {
                exChildIdx = childLeft;
            } else {
                exChildIdx = childRight;
            }

            if (minValue != kInvalid) {
                if (buffer[parentIndex] > minValue) {
                    int t = buffer[exChildIdx];
                    buffer[exChildIdx] = buffer[parentIndex];
                    buffer[parentIndex] = t;
                }
            }
            parentIndex = exChildIdx;
        }
    }
}


```

### 2.常见排序算法

#### 2.1 冒泡
> 交换次数太多，稳定O(n^2)  
> 每一轮排序后，都能找到未排序中的最大值，有序队列从后往前  

```java
public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length-1-i; j++) {
            if (array[j] > array[j+1]) {
                int v = array[j];
                array[j] = array[j+1];
                array[j+1] = v;
            }
        }
    }
}
```

#### 2.2 选择
> 每一轮都能找到最小值，有序队列从前往后

```java
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i+1; j < array.length; j++) {
            if (array[i] > array[j]) {
                int v = array[i];
                array[i] = array[j];
                array[j] = v;
            }
        }
    }
}
```

#### 2.3 插入
> 如选择以第一个元素为参考点，有序队列从前往后

```java
public static void insertSort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int j = i + 1;
        int v = array[j];
        int idx = j;
        for (int k = i; k >= 0; k--) {
            int cv = array[k];
            if (cv > v) {
                array[k+1] = cv;
                idx = k;
            } else {
                break;
            }
        }
        array[idx] = v;
    }
}

```

#### 2.4 插入-二分
> 每一轮排序后，前面的队列都有序，因此可用二分查找在前面的有序队列中快速找位置。

```java
public static void insertBinarySort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int v = array[i+1];
        int idx = i+1;

        int low = 0;
        int high = i;
        while (low <= high) {
            int mid = (low+high) / 2;
            if (array[mid] > v) {
                high = mid-1;
            } else {
                low = mid+1;
            }
        }

        for (int j = idx; j > high+1; j--) {
            array[j] = array[j-1];
        }

        array[high+1] = v;
    }
}

```

#### 2.5 插入-希尔
> 解决一个队列趋向有序时，每次排序插入都需要交换很远  
> 故可以多次按不同步长进行标准插入排序，如5，3，1，最好是素数

```java
public static void insertShellSort(int[] array) {
    int[] delta = {5, 3, 1};
    for (int dk : delta) {
        shellSort(array, dk);
    }
}

private static void shellSort(int[] array, int dk) {
    for (int i = 0; i < array.length-dk; i += dk) {
        int j = i+dk;
        int v = array[j];
        int idx = j;
        for (int k = i; k >= 0; k -= dk) {
            int cv = array[k];
            if (cv > v) {
                array[k+dk] = cv;
                idx = k;
            } else {
                break;
            }
        }

        array[idx] = v;
    }
}

```

#### 2.6 快排
> 以某个元素分割，大的一边，小的一边，然后递归

```java
public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
           int partition = getQuickSortPartition(array, low, high);
           quickSort(array, low, partition-1);
           quickSort(array, partition+1, high);
    }
}

private static int getQuickSortPartition(int[] array, int low, int high) {
    int pivot = array[low];
    while (low < high) {
        while (low < high && pivot < array[high]) {
            high--;
        }
        array[low] = array[high];

        while (low < high && pivot > array[low]) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}
```

#### 2.7 基数排序
> 无需比较，分配-收集即有序。注意分配收集顺序，先分配，先收集。

```java
public static void baseNumSort(int[] array) {
    int[][] box = new int[10][10];;
    int[] collect = new int[array.length];

    for (int i = 0; i < 2; i++) {
        int max = (int) Math.pow(10, i+1);
        int min = (int) Math.pow(10, i);
        for (int[] arr : box) {
            Arrays.fill(arr, 0);
        }

        for (int j = 0; j < array.length; j++) {
            int left = (array[j]%max)/min;
            int insert = 0;
            for (int k = 0; k < 10; k++) {
                if (box[left][k] == 0) {
                    insert = k;
                    break;
                }
            }
            box[left][insert] = array[j];
        }

        int cSize = 0;
        for (int c = 0; c < box.length; c++) {
            for (int b = 0; b < box[0].length; b++) {
                if (box[c][b] == 0) {
                    break;
                }
                collect[cSize++] = box[c][b];
            }
        }

        System.arraycopy(collect, 0, array, 0, array.length);
    }
}
```

#### 2.8 堆排序
> 取出根节点，然后重新调整堆即可。排序就是每次调整为最大堆或者最小堆的过程。

```java
public static void heapSort(final int[] array) {
    SqHeap heap = new SqHeap(new SqList( array ));
    heap.downAdjust();
    heap.heapSort();
    final int[] idx = {0};
    heap.visit(v -> {
        if (v == IStruct.kInvalid) {
            return;
        }
        array[idx[0]++] = v;
    });
}
```

#### 2.9 归并
> 暴力二分，合并时按比较顺序重新排序

```java
public static void mergeSort(int[] array, int low, int high) {
    if (low < high) {
        int mid = (low+high)/2;
        mergeSort(array, low, mid);
        mergeSort(array, mid+1, high);
        merge(array, low, high, mid);
    }
}

private static void merge(int[] array, int low, int high, int mid) {
    int[] b = new int[high-low+1]; 
    int i = low, j = mid+1, k = 0;
    while (i <= mid && j <= high) {
        if (array[i] < array[j]) {
            b[k++] = array[i++];
        } else {
            b[k++] = array[j++];
        }
    }
    while (i <= mid) {
        b[k++] = array[i++];
    }
    while (j <= high) {
        b[k++] = array[j++];
    } 
    i = low;
    for (int m = 0; m < k; m++) {
        array[i++] = b[m];
    }
}
```

#### 待续..