算法

快排

public static void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);

        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
}

private static int partition(int arr[], int left, int right) {
    int key = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] <= key) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, right);

    return i+1;
}

public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

归并排序

public void mergeSort(int[] arr, int left, int right) {
    int mid = (left + right) / 2;  // 中间下标
    if (left < right) {
        mergeSort(arr, left, mid); // 递归拆分左边
        mergeSort(arr, mid + 1, right); // 递归拆分右边
        sort(arr, left, mid, right); // 合并左右
    }
}

public void sort(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1]; // 临时数组，用来保存每次合并年之后的结果
    int i = left;
    int j = mid + 1;
    int k = 0; // 临时数组的初始下标
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int m = 0; m < temp.length; m++) {
        arr[m + left] = temp[m];
    }
}

堆排序

public static void heapSort(int[] nums) {
    if (nums == null) {
        return;
    }
    int len = nums.length;
    // 初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(nums, i, len);
    }
    // 将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
    for (int j = len - 1; j > 0; j--) {
        swap(nums, 0, j);
        adjustHeap(nums, 0, j);
    }
}

// 整理树让其变成堆
public static void adjustHeap(int[] arr, int i, int j) {
    int temp = arr[i];// 定义一个变量保存开始的结点
    // k就是该结点的左子结点下标
    for (int k = 2 * i + 1; k < j; k = 2 * k + 1) {
        // 比较左右两个子结点的大小，k始终记录两者中较大值的下标
        if (k + 1 < j && arr[k] < arr[k + 1]) {
            k++;
        }
        // 经子结点中的较大值和当前的结点比较，比较结果的较大值放在当前结点位置
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else { // 说明已经是大顶堆
            break;
        }
    }
    arr[i] = temp;
}

public static void swap(int[] arr, int num1, int num2) {
    int temp = arr[num1];
    arr[num1] = arr[num2];
    arr[num2] = temp;
}

两个队列实现栈

public class StackWithTwoQueue {
    ArrayDeque<Integer> queue;
    ArrayDeque<Integer> help;
    public StackWithTwoQueue(){
        queue = new ArrayDeque<>();
        help = new ArrayDeque<>();
    }
    public void push(int i){
        queue.add(i);
    }
    public int pop(){
        if (queue.isEmpty()){
            throw new RuntimeException("stack is empty");
        }
        while (queue.size() > 1){
            help.add(queue.poll());
        }
        int res = queue.poll();
        swap();
        return res;
    }
    public void swap(){
        ArrayDeque<Integer> temp = queue;
        queue = help;
        help = temp;
    }
}

两个栈实现队列

public class QueueWithTwoStack {
    ArrayDeque<Integer> stack;
    ArrayDeque<Integer> help;
    public QueueWithTwoStack(){
        stack = new ArrayDeque<>();
        help = new ArrayDeque<>();
    }

    public void push(int i){
        stack.push(i);
    }
    public int pop(){
        if (help.isEmpty()){
            if (stack.isEmpty()){
                return -1;
            }
            while (!stack.isEmpty()){
                help.add(stack.pop());
            }
        }
        return help.pop();
    }
}

BST

public static void insert(int data) {
    Node  newNode = new Node();
    newNode.val = data;
    if(root == null) {
        //如果是第一个节点，也就是根节点为null,直接创建一个新的节点即可　
        root = newNode;
    } else {
        Node cur = root;
        //current节点的父节点
        Node parent;
        //循环查找插入的位置
        while(true) {
            parent = cur;
            //如果插入的值小于当前节点的值，从左子树查找
            if(data < cur.val) {
                cur = cur.leftChild;
                //直到当前节点为null
                if(cur == null) {
                    //设置当前节点的父节点的左子节点为新创建的节点
                    parent.leftChild = newNode;
                    return;
                }

            }
            //如果插入的值大于当前节点的值，从右子树查找
            else {
                cur = cur.rightChild;
                //直到当前节点为null
                if(cur == null) {
                    //设置当前节点的父节点的右子节点为新创建的节点
                    parent.rightChild = newNode;
                    return;
                }
            }
        }
    }
}