Skip to content

Latest commit

 

History

History
1069 lines (617 loc) · 46.3 KB

数据结构与算法.md

File metadata and controls

1069 lines (617 loc) · 46.3 KB

一、数据结构

1. 什么是数据结构

数据结构表示数据在计算机中的存储和组织形式，主要描述数据元素之间和位置关系等。选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。（数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。）

2. 数据结构分类

我们可以从两个维度来理解数据结构：逻辑结构 + 存储结构。

  • 逻辑结构 是从数据之间的逻辑关系，大概可以分为两种：线性结构和非线性结构。

    常用的线性结构有：一维数组、栈、队列、链表。

    常用的非线性结构有：树、图、多维数组

  • 存储结构 是逻辑结构用计算机语言的实现，数据之间的存储关系。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。

数据结构

3. 常用数据结构

常用的数据结构

数组（线性结构）

说明：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。

优点：查找快，时间复杂度为 O(1)

缺点：新增或删除慢，时间复杂度为 O(n);

案例：

链表 （线性结构）

说明：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

分类：单向链表、双向链表、循环链表

优点：新增或删除慢，时间复杂度 O(1)

缺点：查找慢，时间复杂度 O(n)

案例：

栈（线性结构）

说明：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。即“后进先出”的结构，我们称为Last InFirst Out，简称LIFO。

应用场景：深度优先搜索

案例：

队列（线性结构）

说明：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。即“先进先出”的结构，我们称为FirstIn First Out，简称FIFO。

应用场景：广度优先搜索

哈希表

说明：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

哈希表存储的是由键（key）和值（value）组成的数据。在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储。这样一来，不管数据量为多少，我们都能够灵活应对。如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要。

在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。

查找、插入、删除的时间复杂度都为 O(1)，但是空间复杂度为O(n)

举例

堆

  • 说明

    堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”（node），数据就存储在这些结点中。

    堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。

    堆分为最大堆和最小堆，最大堆的根节点是最大元素，最小堆的根节点是最小元素。在堆中存储数据时必须遵守这样一条规则：子结点必定小于/大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。

  • 添加和取出操作

  • 时间复杂度

    堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都为O（1）。另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为n，根据堆的形状特点可知树的高度为log2n，那么重构树的时间复杂度便为O（logn）。添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度成正比，也是O（logn）。

  • 用途

    如果需要频繁地从管理的数据中取出最大值或最小值，那么使用堆来操作会非常方便。

树|二叉树

  • 说明

    1. 树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。

    2. 二叉查找树/二叉搜索树

      • 有两个特征：第一个是每个结点的值均大于其左子树上任意一个结点的值；第二个是每个结点的值均小于其右子树上任意一个结点的值。

      • 结论：二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。

      • 添加和删除操作

        添加：

        删除：删除的结点只有一个子点，那么先删掉目标结点，然后把子结点移到被删除结点的位置上即可。如果需要删除的结点有两个子结点，那么先删掉目标结点，然后在被删除结点的左子树中寻找最大结点，最后将最大结点移到被删除结点的位置上。

      • 时间复杂度

        我们可以把二叉查找树当作是二分查找算法思想的树形结构体现（二分查找的详细说明在3-2节）。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移动了。比较的次数取决于树的高度。所以如果结点数为n，而且树的形状又较为均衡的话，比较大小和移动的次数最多就是log2n。因此，时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了O（n）。

    3. 平衡二叉查找树

      • 是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。又有AVL树和红黑树。

      • AVL树

      • 红黑树

        红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

    4. 完全二叉树

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

    5. B树

  • 二叉树遍历

    • 遍历方式

      前序遍历：根结点 ---> 左子树 ---> 右子树

      中序遍历：左子树---> 根结点 ---> 右子树

      后序遍历：左子树 ---> 右子树 ---> 根结点

      层次遍历：只需按层次遍历即可 ，参考：BFS 的使用场景总结：层序遍历、最短路径问题)

    • 递归遍历二叉树

      前序遍历的递推公式： preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)

      中序遍历的递推公式： inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)

      后序遍历的递推公式： postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r

    • 二叉树递归和非递归遍历方法： Java 实现的二叉树的递归、非递归遍历

  • 两种搜索方法

    • DFS

    • BFS

  • 案例

图（TODO）

说明：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。

加权图

有向图

数据结构比较

数据结构比较2

二、算法基础

1. 基础概念

  • 时间复杂度

    时间复杂度是一个可以描述运算时间的函数，常用大O符号来表达。O这个符号的意思是“忽略重要项以外的内容”，读音同Order。O（n2）的含义就是“算法的运行时间最长也就是n2的常数倍”。

2. 常用排序算法

冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。在这个过程中，数字会像泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。

在冒泡排序中，第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为（n-1）+（n-2）+…+1≈n2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。因此，冒泡排序的时间复杂度为O（n2）。

package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * Created by zhoujunfu on 2018/8/2.
 */
public class BubbleSort {
    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        //外层：需要length-1次循环比较
        for (int i = 0; i < length - 1; i++) {
            //内层：每次循环需要两两比较的次数，每次比较后，都会将当前最大的数放到最后位置，所以每次比较次数递减一次
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    //交换数组array的j和j+1位置的数据
                    swap(array, j, j+1);
                }
            }
        }
    }

    /**
     * 交换数组array的i和j位置的数据
     * @param array 数组
     * @param i 下标i
     * @param j 下标j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

选择排序

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。在序列中寻找最小值时使用的是线性查找。

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。

public class SelectSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j ++) { //选出之后待排序中值最小的位置
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (min != i) {
                arr[min] = arr[i] + arr[min];
                arr[i] = arr[min] - arr[i];
                arr[min] = arr[min] - arr[i];
            }
        }
    }

插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为O（n2）。和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况。

移位法：

public static void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int j = i - 1;
            int temp = a[i]; // 先取出待插入数据保存，因为向后移位过程中会把覆盖掉待插入数
            while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大，就后移
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp; // 找到比待插入数据小的位置，将待插入数据插入
        }
    }

交换法：

  public static void sort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 1; i < arr.length; i ++) {
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[i]) {
                arr[j + 1] = arr[j] + arr[j+1];      //只要大就交换操作
                arr[j] = arr[j + 1] - arr[j];
                arr[j + 1] = arr[j + 1] - arr[j];
                System.out.println("Sorting:  " + Arrays.toString(arr));
            }
        }
    }

堆排序

堆排序的特点是利用了数据结构中的堆。从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。

堆排序一开始需要将n个数据存进堆里，所需时间为O（nlogn）。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于log2n，所以插入1个数据所需要的时间为O（logn）。每轮取出最大的数据并重构堆所需要的时间为O（logn）。由于总共有n轮，所以重构后排序的时间也是O（nlogn）。因此，整体来看堆排序的时间复杂度为O（nlogn）。这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O（n2）都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

    // 堆排序（最小堆）
    public static void sort(int[] array) {

        if (array == null || array.length == 0) {
            return;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(array.length);

        for(int i : array) {
            queue.offer(i);
        }

        int i = 0;
        while (queue.size() != 0) {
            array[i++] = queue.poll();
        }
    }

归并排序 （递归、分治）

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。看一下上面的图便能得知，无论哪一行都是n个数据，所以每行的运行时间都为O（n）。而将长度为n的序列对半分割直到只有一个数据为止时，可以分成log2n行，因此，总共有log2n行。也就是说，总的运行时间为O（nlogn），这与前面讲到的堆排序相同。

package com.fufu.algorithm.sort;

import java.util.Arrays;

/**
 * Created by zhoujunfu on 2018/8/10.
 */
public class MergeSort {

    public static int[] sort(int [] a) {
        if (a.length <= 1) {
            return a;
        }
        int num = a.length >> 1;
        int[] left = Arrays.copyOfRange(a, 0, num);
        int[] right = Arrays.copyOfRange(a, num, a.length);
        return mergeTwoArray(sort(left), sort(right));
    }

    public static int[] mergeTwoArray(int[] a, int[] b) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据

        while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length) { //序列a中多余的元素移入新数组
            result[k++] = a[i++];
        }
        while (j < b.length) {//序列b中多余的元素移入新数组
            result[k++] = b[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] b = {3, 1, 5, 4};
        System.out.println(Arrays.toString(sort(b)));
    }
}

快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。[比基准值小的数] 基准值 [比基准值大的数]

实现方式：填坑法、交换法、顺序遍历法

填坑法

  /**
     *  快速排序（挖坑法递归）
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void sort(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;
        int temp = arr[left]; //挖坑1：保存基准的值

        while (left < right) {
            while (left < right && arr[right] >= temp) {
                right--;
            }
            arr[left] = arr[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
            while (left < right && arr[left] <= temp) {
                left ++;
            }
            arr[right] = arr[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
        }
        arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort(arr, low, left-1);
        sort(arr, left + 1, high);
    }

交换法

/**
 * 快速排序
 * Created by zhoujunfu on 2018/8/6.
 */
public class QuickSort {
    /**
     * 快速排序（左右指针法）
     * @param arr 待排序数组
     * @param low 左边界
     * @param high 右边界
     */
    public static void sort2(int arr[], int low, int high) {
        if (arr == null || arr.length <= 0) {
            return;
        }
        if (low >= high) {
            return;
        }

        int left = low;
        int right = high;

        int key = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= key) {
                right--;
            }
            while (left < right && arr[left] <= key) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        swap(arr, low, left);
        System.out.println("Sorting: " + Arrays.toString(arr));
        sort2(arr, low, left - 1);
        sort2(arr, left + 1, high);
    }

    public static void swap(int arr[], int low, int high) {
        int tmp = arr[low];
        arr[low] = arr[high];
        arr[high] = tmp;
    }
}

顺序遍历法

    // 顺序遍历法
    public static void sort3(int[] array, int low, int high) {

        if(array == null && array.length == 1) {
            return;
        }

        if(low >= high) {
            return;
        }

        int povit = array[high];
        int left = low , right = low;

        while (right < high) {
            while (right < high && array[right] >= povit) {
                right++;
            }

            if (right < high) {
                SwapUtil.swapByTmp(array, left, right);
                left++;
            }
        }

        SwapUtil.swapByTmp(array, left, high);

        sort3(array, low, left - 1);
        sort3(array, left + 1, high);
    }

总结

3. 常用查找算法

线性查找

线性查找是一种在数组中查找数据的算法。线性查找的操作很简单，只要在数组中从头开始依次往下查找即可。若数据量为n，线性查找的时间复杂度便为O（n）。

二分查找

二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。

二分查找利用已排好序的数组，每一次查找都可以将查找范围减半。查找范围内只剩一个数据时查找结束。数据量为n的数组，将其长度减半log2n次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作log2n次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为O（logn）。

    // 二分查找(递归)
    private static int search(int key, int[] array, int low, int high) {

        if (low > high) {
            return  -1;
        }

        int mid = low + (high - low) / 2;

        if (array[mid] == key) {
            return mid;
        } else {
            if (array[mid] > key) {
                return search(key, array, low, mid - 1);
            } else {
                return search(key, array, mid + 1, high);
            }
        }

    }

哈希查找

二叉查找树

4. 其他算法概念

1. 枚举法（穷举法）

  • 概念：本质是搜索算法，指的是从问题所有可能的解的集合中一一枚举各元素。
  • 优点：算法简单，在局部地方使用枚举法，效果十分的好
  • 缺点：运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢

2. 递归法 -- done

  • 概念：用一句话来形容递归算法的实现，就是在函数或者子过程的内部，直接或间接的调用自己算法。递归算法实际上是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最终获得最终的解。

  • 三个要素：

    递归边界：算法要有一个边界出口，能结束程序

    参数收敛：每次调用参数都是收敛于递归边界

    自身调用

3. 分治算法

  • 概念：将原问题分成n个规模较小而结构与原问题相似的子问题。递归地对这些子问题求解，然后合并其结果就得到原问题的解。n=2时的分治法又称为二分法。

  • 步骤

    分解——将原问题分解成一系列子问题 解决——递归地解各子问题

    合并——将子问题的结果合并成原问题的解

  • 案例

4. 贪心算法

  • 概念

    贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

  • 步骤

    步骤1：从某个初始解出发； 步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模； 步骤3：将所有解综合起来。

  • 案例

5. 滑动窗口算法 -- done

6. 双指针 -- done

7. 单调栈 -- done

8. 动态规划算法

9. 回溯算法 ， [决策树] -- done

  • 概念

    回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

  • 用途

    可用于解决寻找所有可行解的题 ；

  • 模板

    result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

    其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

10. 搜索算法 -- done

  • BFS （广度优先遍历/搜索）Breadth First Search

    • 概念

    • 用途

      • 层序遍历
      • 最短路径 （在一棵树中，一个结点到另一个结点的路径是唯一的，但在图中，结点之间可能有多条路径，其中哪条路最近呢？这一类问题称为最短路径问题）

    • 实现

      广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

      1. 把根节点放到队列的末尾。
      2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
      3. 找到所要找的元素时结束程序。
      4. 如果遍历整个树还没有找到，结束程序。

    • 案例

  • DFS （深度优先遍历/搜索）

    • 概念

    • 用途

    • 实现

      深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：

      1. 把根节点压入栈中。
      2. 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
      3. 找到所要找的元素时结束程序。
      4. 如果遍历整个树还没有找到，结束程序。

    • 案例

11. 中心扩散算法

12. KMP算法是一种改进的字符串匹配算法

  • 概念

    常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

  • 案例

三、数学运算符

  1. 异或操作

    异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。

    运算定律

    归零律：img

    恒等律：img

    交换律： img

    结合律：img

    自反：img

  2. 对数函数 (logab)

案例

参考

  1. 数据结构与算法（java）
  2. 面试必备：八种排序算法原理及Java实现