数据结构学习笔记

Stack

1. public Stack() 创建一个空堆栈
2. public boolean empty() 测试堆栈是否为空
3. public E pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象
4. public E push(E item) 把项压入堆栈顶部
5. public E peek() 查看堆栈顶部的对象，但不从堆栈中移除它
6. public boolean empty() 测试堆栈是否为空

Queue

1. boolean add() 增加一个元索，如果队列已满，则抛出一个 IIIegaISlabEepeplian 异常
2. boolean offer() 添加一个元素并返回true，如果队列已满，则返回false
3. void put() 添加一个元素，如果队列满，则阻塞

4. E remove() 移除并返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常
5. E poll() 移除并返问队列头部的元素，如果队列为空，则返回null
6. E take() 移除并返回队列头部的元素，如果队列为空，则阻塞

7. E element() 返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常
8. E peek() 返回队列头部的元素，如果队列为空，则返回null

二叉树

类型

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点，节点数为 2^h-1。

完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。一棵完全二叉树的两棵子树，至少有一棵是满二叉树。

大顶堆/小顶堆

任一结点的值是其子树所有结点的最大值或最小值：

1. 最大值时，称为“最大堆”，也称大顶堆；
2. 最小值时，称为“最小堆”，也称小顶堆；

二叉查找树

也称为二叉搜索树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(log n)。

平衡二叉树

空树或者左右两个子树的高度差绝对值不超过1且左右两个子树也都是平衡树。

当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

随着树的高度的增加，动态插入和删除的代价也随之增加。

节点数

普通二叉树

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

时间复杂度: O(N)

满二叉树

public int countNodes(TreeNode root) {
    int h = 0;
    // 计算树的高度
    while (root != null) {
        root = root.left;
        h++;
    }
    // 节点数为 2^h - 1
    return (int) Math.pow(2, h) - 1;
}

时间复杂度: O(logN)

完全二叉树

public int countNodes(TreeNode root) {
    TreeNode l = root, r = root;
    // 记录左、右子树的高度
    int hl = 0, hr = 0;
    while (l != null) {
        l = l.left;
        hl++;
    }
    while (r != null) {
        r = r.right;
        hr++;
    }
    // 如果左右子树的高度相同，则是一棵满二叉树
    if (hl == hr) {
        return (int)Math.pow(2, hl) - 1;
    }
    // 如果左右高度不同，则按照普通二叉树的逻辑计算
    return 1 + countNodes(root.left) + countNodes(root.right);
}

因为一棵完全二叉树的两棵子树，至少有一棵是满二叉树，因此时间复杂度: O(logN*logN) 而不是 O(N*logN)。

遍历

前序	中	左	右
中序	左	中	右
后序	左	右	中

中序遍历

递归算法：中序遍历的顺序为leftTree， root， rightTree，显然先遍历左子树，然后是根，最后右子树。中序遍历的递归算法自然也就出来了。

public List<Integer> inOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

public void inOrder(TreeNode node, List<Integer> result) {
    if (node != null) {
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

非递归算法：按从左到右进行访问。先指针往左探寻到底，然后观察最后一个非空节点是否有右节点，若有，将该右节点作为新的探寻起点，再进行下一轮的探寻,需要使用stack来帮助缓存之前的节点。

public List<Integer> inOrderTraversal(TreeNode node) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (node != null || !stack.empty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
    }
    return result;
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

前序遍历

递归算法

public List<Integer> preOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preOrder(root, result);
    return result;
}

public void preOrder(TreeNode node, List<Integer> result) {
    if (node != null) {
        result.add(node.val);
        preOrder(node.left, result);
        preOrder(node.right, result);
    }
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

非递归算法

public List<Integer> preOrderTraversal(TreeNode node) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    while (node != null || !stack.empty()) {
        if (node != null) {
            result.add(node.val);
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            node = node.right;
        }
    }
    return result;
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

后序遍历

递归算法

public List<Integer> postOrderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postOrder(root, result);
    return result;
}

public void postOrder(TreeNode node, List<Integer> result) {
    if (node != null) {
        postOrder(node.left, result);
        postOrder(node.right, result);
        result.add(node.val);
    }
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

非递归算法：和之前中序和前序算法不同，后续遍历的root节点要最后才能被访问，因此，我们若想访问某节点，那么我们需要知道该节点的右节点是否已经被访问过。只有该节点的右节点为null，或者已被访问过，那么该节点才能被访问；否则需要先将右节点访问完。为了判断该节点的右节点是否已经被访问过，需另外设一个记录指针last来指示已经访问过的节点，如果之前访问过的节点last恰为该节点的右节点，说明其右子树已经访问完，应该访问该节点。

public List<Integer> postOrderTraversal(TreeNode node) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode last = null;
    while (node != null || !stack.empty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (node.right == null || node.right == last) {
            result.add(node.val);
            last = node;
            node = null;
        } else {
            stack.push(node);
            node = node.right;
        }
    }
    return result;
}

• 时间复杂度: O(n)，其中 n 是二叉树的节点数，每一个节点恰好被遍历一次。
• 空间复杂度: O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

层序遍历

借助队列实现，且没有递归算法。初始时，根结点入队列；然后 while 循环判断队列不空时，弹出一个结点并访问它，并把它的孩子结点入队列。

public List<Integer> levelOrder(TreeNode node) {
    List<Integer> result = new ArrayList<>();
    if (node == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(node);
    while (!queue.isEmpty()) {
        node = queue.poll();
        if (node != null) {
            result.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return result;
}

排序算法

概述

排序算法大体可分为两种：

• 比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
• 非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

排序算法的稳定性:如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的.

冒泡排序

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个flag来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++) {         // 每次最大元素就像气泡一样"浮"到数组的最后
        for (int i = 0; i < n - 1 - j; i++) { // 依次比较相邻的两个元素,使较大的那个向后移
            if (A[i] > A[i + 1]) {           // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
                Swap(A, i, i + 1);
            }
        }
    }
}

鸡尾酒排序(冒泡排序改进)

此算法与冒泡排序的不同处在于从低到高然后从高到低。

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void CocktailSort(int A[], int n) {
    int left = 0;                            // 初始化边界
    int right = n - 1;
    while (left < right) {
        for (int i = left; i < right; i++) {   // 前半轮,将最大元素放到后面
            if (A[i] > A[i + 1])
            {
                Swap(A, i, i + 1);
            }
        }
        right--;
        for (int i = right; i > left; i--) {  // 后半轮,将最小元素放到前面
            if (A[i - 1] > A[i]) {
                Swap(A, i - 1, i);
            }
        }
        left++;
    }
}

选择排序

初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(n^2)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void SelectionSort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)         // i为已排序序列的末尾
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     // 未排序序列
        {
            if (A[j] < A[min])              // 找出未排序序列中的最小值
            {
                min = j;
            }
        }
        if (min != i)
        {
            Swap(A, min, i);    // 放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
        }
    }
}

插入排序

// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void InsertionSort(int A[], int n)
{
    for (int i = 1; i < n; i++)         // 类似抓扑克牌排序
    {
        int get = A[i];                 // 右手抓到一张扑克牌
        int j = i - 1;                  // 拿在左手上的牌总是排序好的
        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
        {
            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大，就将其右移
            j--;
        }
        A[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等)，将抓到的牌插入到该手牌右边(相等元素的相对次序未变，所以插入排序是稳定的)
    }
}

二分插入排序(插入排序)

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void InsertionSortDichotomy(int A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int get = A[i];                    // 右手抓到一张扑克牌
        int left = 0;                    // 拿在左手上的牌总是排序好的，所以可以用二分法
        int right = i - 1;                // 手牌左右边界进行初始化
        while (left <= right)            // 采用二分法定位新牌的位置
        {
            int mid = (left + right) / 2;
            if (A[mid] > get)
                right = mid - 1;
            else
                left = mid + 1;
        }
        for (int j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j + 1] = A[j];
        }
        A[left] = get;                    // 将抓到的牌插入手牌
    }
}

希尔排序(插入排序)

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 根据步长序列的不同而不同。已知最好的为O(n(logn)^2)
// 最优时间复杂度 ---- O(n)
// 平均时间复杂度 ---- 根据步长序列的不同而不同。
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

void ShellSort(int A[], int n)
{
    int h = 0;
    while (h <= n)                          // 生成初始增量
    {
        h = 3 * h + 1;
    }
    while (h >= 1)
    {
        for (int i = h; i < n; i++)
        {
            int j = i - h;
            int get = A[i];
            while (j >= 0 && A[j] > get)
            {
                A[j + h] = A[j];
                j = j - h;
            }
            A[j + h] = get;
        }
        h = (h - 1) / 3;                    // 递减增量
    }
}

归并排序

归并排序的实现分为递归实现与非递归(迭代)实现。

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(n)
// 稳定性 ------------ 稳定

// 合并两个已排好序的数组[left...mid]和[mid+1...right]
private void merge(int[] arr, int left, int mid, int right) {
    int len = right - left + 1;
    int i = left;   // 前一数组的起始元素
    int j = mid + 1; // 后一数组的起始元素
    int[] tmp = new int[len];
    int index = 0;
    while (i <= mid && j <= right) {
        tmp[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) {
        tmp[index++] = arr[i++];
    }
    while (j <= right) {
        tmp[index++] = arr[j++];
    }
    for (int k = 0; k < len; k++) {
        arr[left++] = tmp[k];
    }
}

public void mergeSort(int[] arr, int left, int right) {
    if (left == right) {
        return; // 当待排序的序列长度为1时，递归开始回溯，进行merge操作
    }
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

堆排序

1. 由输入的无序数组构造一个最大堆，作为初始的无序区
2. 把堆顶元素（最大值）和堆尾元素互换
3. 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
4. 重复步骤2，直到堆的尺寸为1

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定
public void heapSort(int[] arr) {
    int heapSize = buildHeap(arr); // 建立一个最大堆
    while (heapSize > 1) { // 堆（无序区）元素个数大于1，未完成排序
        // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
        swap(arr, 0, --heapSize);
        heapify(arr, 0, heapSize);
    }
}

// 建堆，时间复杂度O(n)
private int buildHeap(int[] arr) {
    int heapSize = arr.length;
    // 从每一个非叶结点开始向下进行堆调整
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
        heapify(arr, i, heapSize);
    }
    return heapSize;
}

// arr[i]向下进行堆调整
private void heapify(int[] arr, int i, int heapSize) {
    int left = 2 * i + 1;   // 左孩子
    int right = 2 * i + 2;  // 右孩子
    int max = i;
    if (left < heapSize && arr[left] > arr[max]) {
        max = left;
    }
    if (right < heapSize && arr[right] > arr[max]) {
        max = right;
    }
    if (max != i) {
        swap(arr, i, max); // 把当前结点和它的最大(直接)子节点进行交换
        heapify(arr, max, heapSize); // 递归调用，继续从当前结点向下进行堆调整
    }
}

快速排序

以第一个数字6作为基数，使用双指针i, j进行双向遍历：

1. i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
2. 找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
3. 最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；

// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)
// 稳定性 ---------- 不稳定
public void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = patition(arr, left, right);
    quickSort(arr, left, index - 1);
    quickSort(arr, index + 1, right);
}

private int patition(int[] arr, int left, int right) {
    int key = arr[left];    // 第一个数作为基准
    int i = left;
    int j = right;
    while (i < j) {
        while (arr[j] >= key && i < j) {
            j--;  // 从右往左找第一个小于基数的数
        }
        while (arr[i] <= key && i < j) {
            i++;
        }
        swap(arr, i, j);
    }
    swap(arr, left, i);
    return i;
}

计数排序

1. 统计数组A中每个值A[i]出现的次数，存入C[A[i]]
2. 从前向后，使数组C中的每个值等于其与前一项相加，这样数组C[A[i]]就变成了代表数组A中小于等于A[i]的元素个数
3. 反向填充目标数组B：将数组元素A[i]放在数组B的第C[A[i]]个位置（下标为C[A[i]] - 1），每放一个元素就将C[A[i]]递减

// 分类 ------------ 内部非比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- O(n + k)
// 最优时间复杂度 ---- O(n + k)
// 平均时间复杂度 ---- O(n + k)
// 所需辅助空间 ------ O(n + k)
// 稳定性 ----------- 稳定


const int k = 100;   // 基数为100，排序[0,99]内的整数
int C[k];            // 计数数组

void CountingSort(int A[], int n)
{
    for (int i = 0; i < k; i++)   // 初始化，将数组C中的元素置0(此步骤可省略，整型数组元素默认值为0)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)   // 使C[i]保存着等于i的元素个数
    {
        C[A[i]]++;
    }
    for (int i = 1; i < k; i++)   // 使C[i]保存着小于等于i的元素个数，排序后元素i就放在第C[i]个输出位置上
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int *)malloc((n) * sizeof(int));// 分配临时空间,长度为n，用来暂存中间数据
    for (int i = n - 1; i >= 0; i--)    // 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变)
    {
        B[--C[A[i]]] = A[i];      // 把每个元素A[i]放到它在输出数组B中的正确位置上
                                  // 当再遇到重复元素时会被放在当前元素的前一个位置上保证计数排序的稳定性
    }
    for (int i = 0; i < n; i++)   // 把临时空间B中的数据拷贝回A
    {
        A[i] = B[i];
    }
    free(B);    // 释放临时空间 
}

基数排序

// 分类 ------------- 内部非比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n * dn)
// 最优时间复杂度 ---- O(n * dn)
// 平均时间复杂度 ---- O(n * dn)
// 所需辅助空间 ------ O(n * dn)
// 稳定性 ----------- 稳定

const int dn = 3;                // 待排序的元素为三位数及以下
const int k = 10;                // 基数为10，每一位的数字都是[0,9]内的整数
int C[k];

int GetDigit(int x, int d)          // 获得元素x的第d位数字
{
    int radix[] = { 1, 1, 10, 100 };// 最大为三位数，所以这里只要到百位就满足了
    return (x / radix[d]) % 10;
}

void CountingSort(int A[], int n, int d)// 依据元素的第d位数字，对A数组进行计数排序
{
    for (int i = 0; i < k; i++)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        C[GetDigit(A[i], d)]++;
    }
    for (int i = 1; i < k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int*)malloc(n * sizeof(int));
    for (int i = n - 1; i >= 0; i--)
    {
        int dight = GetDigit(A[i], d);  // 元素A[i]当前位数字为dight   
        B[--C[dight]] = A[i];           // 根据当前位数字，把每个元素A[i]放到它在输出数组B中的正确位置上
        // 当再遇到当前位数字同为dight的元素时，会将其放在当前元素的前一个位置上保证计数排序的稳定性
    }
    for (int i = 0; i < n; i++)
    {
        A[i] = B[i];
    }
    free(B);
}

void LsdRadixSort(int A[], int n)     // 最低位优先基数排序
{
    for (int d = 1; d <= dn; d++)     // 从低位到高位
        CountingSort(A, n, d);        // 依据第d位数字对A进行计数排序
}

int main()
{
    int A[] = { 20, 90, 64, 289, 998, 365, 852, 123, 789, 456 };// 针对基数排序设计的输入
    int n = sizeof(A) / sizeof(int);
    LsdRadixSort(A, n);
    printf("基数排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且如果适当的选择基数，dn一般不大于log n，所以基数排序一般要快过基于比较的排序，比如快速排序。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序并不是只能用于整数排序。

桶排序

桶排序也叫箱排序。工作的原理是将数组元素映射到有限数量个桶里，利用计数排序可以定位桶的边界，每个桶再各自进行桶内排序（使用其它排序算法或以递归方式继续使用桶排序）。

// 分类 ------------- 内部非比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- O(nlogn)或O(n^2)，只有一个桶，取决于桶内排序方式
// 最优时间复杂度 ---- O(n)，每个元素占一个桶
// 平均时间复杂度 ---- O(n)，保证各个桶内元素个数均匀即可
// 所需辅助空间 ------ O(n + bn)
// 稳定性 ----------- 稳定

/* 本程序用数组模拟桶 */
const int bn = 5;    // 这里排序[0,49]的元素，使用5个桶就够了，也可以根据输入动态确定桶的数量
int C[bn];           // 计数数组，存放桶的边界信息

void InsertionSort(int A[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)  // 从第二张牌开始抓，直到最后一张牌
    {
        int get = A[i];
        int j = i - 1;
        while (j >= left && A[j] > get)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = get;
    }
}

int MapToBucket(int x)
{
    return x / 10;    // 映射函数f(x)，作用相当于快排中的Partition，把大量数据分割成基本有序的数据块
}

void CountingSort(int A[], int n)
{
    for (int i = 0; i < bn; i++)
    {
        C[i] = 0;
    }
    for (int i = 0; i < n; i++)     // 使C[i]保存着i号桶中元素的个数
    {
        C[MapToBucket(A[i])]++;
    }
    for (int i = 1; i < bn; i++)    // 定位桶边界：初始时，C[i]-1为i号桶最后一个元素的位置
    {
        C[i] = C[i] + C[i - 1];
    }
    int *B = (int *)malloc((n) * sizeof(int));
    for (int i = n - 1; i >= 0; i--)// 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变)
    {
        int b = MapToBucket(A[i]);  // 元素A[i]位于b号桶
        B[--C[b]] = A[i];           // 把每个元素A[i]放到它在输出数组B中的正确位置上
                                    // 桶的边界被更新：C[b]为b号桶第一个元素的位置
    }
    for (int i = 0; i < n; i++)
    {
        A[i] = B[i];
    }
    free(B);
}

void BucketSort(int A[], int n)
{
    CountingSort(A, n);          // 利用计数排序确定各个桶的边界（分桶）
    for (int i = 0; i < bn; i++) // 对每一个桶中的元素应用插入排序
    {
        int left = C[i];         // C[i]为i号桶第一个元素的位置
        int right = (i == bn - 1 ? n - 1 : C[i + 1] - 1);// C[i+1]-1为i号桶最后一个元素的位置
        if (left < right)        // 对元素个数大于1的桶进行桶内插入排序
            InsertionSort(A, left, right);
    }
}

int main()
{
    int A[] = { 29, 25, 3, 49, 9, 37, 21, 43 };// 针对桶排序设计的输入
    int n = sizeof(A) / sizeof(int);
    BucketSort(A, n);
    printf("桶排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

Arrays.sort()

Java 中ArrayList和Collections的sort方法都是调用了Arrays.sort()方法,对于基础类型的排序,使用了更为高效的快速排序(不稳定).而对于非基础类型,在jdk1.8之前使用了归并排序,后来弃用,使用了TimSort.sort()

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

public static <T> void sort(T[] a, int fromIndex, int toIndex,
                            Comparator<? super T> c) {
    if (c == null) {
        sort(a, fromIndex, toIndex);
    } else {
        rangeCheck(a.length, fromIndex, toIndex);
        // Android-changed: LegacyMergeSort is no longer supported
        // if (LegacyMergeSort.userRequested)
        //     legacyMergeSort(a, fromIndex, toIndex, c);
        // else
            TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
    }
}

查找算法

顺序查找

时间复杂度为O(n)。

二分查找

最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)。折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

插值查找

查找成功或者失败的时间复杂度均为O(log2(log2n))。

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}

斐波那契查找

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。

斐波那契查找是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

1. 相等，mid位置的元素即为所求
2. >，low=mid+1,k-=2;
   • 说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= F(k)-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
3. <，high=mid-1,k-=1。
   • 说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

树表查找

二叉树查找

复杂度分析：

• 它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡

二叉查找树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。

二叉查找树性质：

• 对二叉查找树进行中序遍历，即可得到有序的数列。

平衡查找树之2-3查找树

平衡查找树之红黑树

B树和B+树

总结

二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。

除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。

分块查找

算法思想：将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

1. 先选取各块中的最大关键字构成一个索引表；
2. 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

哈希查找

算法思想：

• 如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

1. 用给定的哈希函数构造哈希表；
2. 根据选择的冲突处理方法解决地址冲突；
3. 在哈希表的基础上执行哈希查找。

复杂度分析：

• 单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

算法设计思想

贪心算法，分治算法，动态规划算法，随机划分算法，回溯算法等。

Lru算法

参考 LinkedHashMap 可知，LinkedHashMap 保存了记录的插入顺序，还可以在此基础上再根据访问顺序(get,put)来排序，可以用来实现 Lru 算法。它继承自 HashMap, 查看 HashMap 的 put 方法可知在 putVal 方法最后会调用 afterNodeInsertion 方法：

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMapEntry<K,V> first;
    // 若 removeEldestEntry 返回 true 则删除第一个节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

因此可以重写 removeEldestEntry() 方法，当 map 里面的元素个数大于缓存最大容量则删除链表的顶端元素：

public class LruLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private int capacity;

    LruLinkedHashMap(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

深度/广度优先