SQL 查询需要花费一定时间，有时会长得让人心烦。

  为了尽可能缩短查询时间，提高效率，带来良好的用户体验，我们可以：

• 使用索引
• 升级硬件
• 挑选合适的数据类型
• 检查 MySQL 的查询优化程序
• 编写更好的查询 SQL 以影响服务器的调度机制

使用索引

  用来加快查询的技术有很多，其中最重要的是索引。通常，能够造成查询速度最大差异的是索引的正确使用。很多时候，当查询速度很慢时，添加上索引后就能迅速解决问题。但情况也不总是这样，因为优化并不总是一件简单的事情。然而，在许多情况下，假如你不使用索引，那么试图通过其他途径来提高性能则纯粹是浪费时间。你应该首先使用索引来最大程度地改进性能，然后再看是否还有其他技术可以采用。

  对索引的研究请参考 MySQL 数据库优化之索引。

升级硬件

  利用较好的硬件可使服务器运行得更快。

  通过硬件优化，最重要的原则与调整服务器参数时的原则一样——将尽可能多的信息快速储存起来，并且尽可能久地保存它们。

  对硬件配置的以下几个方面进行修改来改进服务器性能：

• 在机器里安装更多的内存。这会增加服务器的缓存和缓冲区的容量，从而允许数据在内存中能够保持更长的时间，较少需要从磁盘上获取信息。
• 如果你有足够的RAM可以让所有的数据交换都发生一个内存文件系统里，可以重新配置你的系统来删除所有的磁盘数据交换设备。要知道，即使你有足够的RAM，有些系统仍会与磁盘交换数据。
• 添加更快的磁盘来改善 I/O 等待时间。在这里，寻道时间通常是性能的主要决定因素。侧向移动磁头是比较慢的。当磁头位置确定以后，把信息从磁道上读出来相对要快一些。不过，要是你能在更多的内存和更快的磁盘之间做选择，应选更多的内存。内存永远比磁盘快，添加内存后可以使用较大的缓存并减少磁盘的活动量。
• 使用多处理器硬件。对于 MySQL 服务器这样的多线程程序来说，多处理器硬件可以同时执行多个线程
• （读写分离）在物理设备之间分散磁盘读写活动，提高并行度。通过多个物理设备将读和写分开，比在一个设备上读和写要快。例如，假设将数据库存储在一个设备上，将日志文件存储在另外一个设备上，那么对两个设备同时写入就要比数据库和日志文件都在同一个设备上时快一些。注意，在同一个物理设备上采用不同分区是没有用的，不能算并行，因为它们还是要竞争同一个物理资源（磁头）。

  简而言之，加内存！换磁盘！升 CPU！搞机器！即，打钱！！！

挑选合适的数据类型

  不同的数据类型也会影响查询的性能，因此：

• 尽量使用数值操作而少使用字符串操作，因为前者通常运算更快
• 若“小”类型够用，就不要选“大”类型，因为前者处理速度更快
• 若可选择数据行的存储格式，尽量选择最适合你的存储引擎格式
• 尽量把数据列声明为NOT NULL
• 考虑使用ENUM数据列
• 利用PROCEDURE ANALYSE()语句分析数据表，其可以提供声明建议

检查 MySQL 的查询优化程序

  在 MySQL ，我们可以通过命令来查看相关 SQL 的执行情况以决定如何优化 SQL 的执行效率，具体请参考 MySQL 数据库优化之分析执行计划

合适的 SQL 优化

ORDER BY 优化

• 根据排序字段建立合适的索引，多字段排序时，也遵循最左前缀法则。
• 尽量使用覆盖索引。
• 多字段排序，一个升序一个降序，此时需要注意联合索引在创建时的规则（ASC/DESC）。
• 如果不可避免的出现filesort，大数据量排序时，可以适当增大排序缓冲区大小sort_buffer_size（默认256k）。

GROUP BY 优化

• 在分组操作时，可以通过索引来提高效率
• 分组操作时，索引的使用也是满足最左前缀法则的

LIMIT 优化

  一个常见又非常头疼的问题就是limit2000000,10，此时需要MySQL排序前2000010记录，仅仅返回2000000-2000010的记录，其他记录丢弃，查询排序的代价非常大。

  LIMIT 走主键索引，过滤出小数据量，在多表联查

COUNT 优化

  count的几种用法如下：

• count(主键)：InnoDB 引擎会遍历整张表，把每一行的主键id 值都取出来，返回给服务层。服务层拿到主键后，直接按行进行累加（主键不可能为 NULL）
• count(字段)：
  • 有NOT NULL约束：InnoDB 引擎会遍历整张表把每一行的字段值都取出来，返回给服务层，直接按行进行累加
  • 无NOT NULL约束：InnoDB 引擎会遍历整张表把每一行的字段值都取出来，返回给服务层，服务层判断是否为 NULL，不为 NULL，计数累加
• count(1)：InnoDB引擎遍历整张表，但不取值。服务层对于返回的每一行，放一个数字“1”进去，直接按行进行累加
• count (*)：InnoDB引擎并不会把全部字段取出来，而是专门做了优化，不取值，服务层直接按行进行累加

  按照效率排序的话，count (*) ≈ count(1) > count(主键) > count(字段)，所以尽量使用count (*)。

参考

• Paul DuBois. MySQL 技术内幕 [M]. 人民邮电出版社, 2011

什么是事务？

  事务（transaction）是作为一个不可分割的逻辑单元而被执行的一组 SQL 语句。

什么是连接？

  SQL 中的连接（JOIN）语句用于将数据库中的两个或多个表组合起来。由”连接”生成的集合，可以被保存为表，或者当成表来使用。JOIN 语句的含义是把两张表的属性通过它们的值组合在一起。基于 ANSI 标准的 SQL 列出了五种 JOIN 方式：内连接（INNER），全外连接（FULL OUTER），左外连接（LEFT OUTER），右外连接（RIGHT OUTER）和交叉连接（CROSS）。在特定的情况下，一张表（基本表，视图，或连接表）可以和自身进行连接，成为自连接（self-join）。

阅读全文 »

什么是 SQL 的约束？

  约束（constraint）是一种限制，它通过对表的行或列的数据做出限制，来确保表的数据的完整性、唯一性。

  约束分为列级约束（对一个数据列创建的约束）和表级约束（对多个数据列创建的约束）。

  一般我们在创建数据表的时候都会加入一些约束，如主键约束，非空约束，默认约束。

什么是 SQL？

  SQL（Structured Query Language，结构化查询语言）是 MySQL 服务器能听懂的语言，共分为四大类：DDL、DQL、DML、DCL：

• 数据定义语言（Data Definition Language）——CREATE、ALTER、DROP 等语句
• 数据查询语言（Data Query Language）——SELECT、FROM、WHERE 及其组成语句
• 数据操作语言（Data Manipulation Language ）——UPDATE、INSERT、DELETE 语句
• 数据控制语言（Data Control Language ）——COMMIT、ROLLBACK、SET TRANSACTION

什么是 MySQL？

  MySQL 是一种使用 C 和 C++ 语言编写的关系型数据库管理系统。

目标

• 在一台 CentOS 7 的 ECS 云服务器上快速部署基于 Hexo 的博客站点
• 部署完成后可在本地快速发布博文到服务器上，进行个人站点展示

序言

  递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

  简单来讲，递归就是函数反复调用自身的过程。
  你肯定听过这个故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”
  上面的故事即是递归思想的体现。

算法概述

算法分类

  十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn) ，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度

  相关概念:

• 稳定：若 a 原本在 b 前面，而 a=b ，排序之后 a 仍然在 b 的前面。
• 不稳定：若 a 原本在 b 的前面，而 a=b ，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：描述算法的运行时间与输入数据 n 之间的关系，反映了当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

选择排序（Selection Sort）

  选择排序（Selection-sort）：首先在乱序序列中找到最小（大）元素存放到排序序列的起始位置，然后再从剩余乱序序列中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素排序完毕。

算法描述

   n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为 R[1..n] ，有序区为空；
• 第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R[1..i-1] 和 R(i..n） 。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少 1 个的新无序区；
• n-1 趟结束，数组有序化完成。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class SelectSort {
    public int[] selectSort(int[] arr) {
        // 定义最小数的索引及临时保存变量
        int minIndex, temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(selectSort(arr)));
    }
}

算法分析

  表现最稳定的排序算法之一，因为无论什么数据进去都是 O($n^2$) 的时间复杂度，所以用到它的时候，数据规模越小越好。
  选择排序唯一的好处可能就是不占用额外的内存空间。理论上讲，选择排序可能也是平时排序一般最容易想到的排序方式了。

冒泡排序（Bubble Sort）

  冒泡排序（Bubble Sort）：重复地走访过要排序的数列，一次比较两个元素，若它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
  这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  冒泡排序的步骤如下：

• 比较相邻的元素：若第一个比第二个大，就交换它们两个；
• 依次对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤 1~3 ，直到排序完成。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class BubbleSort {
    public int[] bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(bubbleSort(arr)));
    }
}

插入排序（Insertion Sort）

  插入排序（Insertion Sort）：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，类似于玩扑克牌。

算法描述

  一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 若该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class InsertionSort {
    public int[] insertionSort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            // 上面为简写，详见下面
            // for (int j = i; j > 0; j--) {
            //     if (arr[j] < arr[j - 1]) {
            //         temp = arr[j];
            //         arr[j] = arr[j - 1];
            //         arr[j - 1] = temp;
            //     } else {
            //         break;
            //     }
            // }
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(insertionSort(arr)));
    }
}

算法分析

  插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

希尔排序（Shell Sort）

  希尔排序（Shell Sort）是 1959 年由 Shell 发明，第一个突破 O(n2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
  希尔排序也叫缩小增量排序。

算法描述

  先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti > tj ，tk = 1 ；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

算法分析

  希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

快速排序（Quick Sort）

  快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

  快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 进行分区（partition）操作：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class QuickSort {
    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int l, int r) {
        // 终止条件
        if (l >= r) {
            return;
        }
        // 目的
        int p = partition(arr, l, r);
        // 递归排序
        quick(arr, l, p - 1);
        quick(arr, p + 1, r);
    }

    /**
     * 分区：该过程包含 3 部分，pivot ，小于 pivot 部分，大于 pivot 部分
     * 分区完成后左边部分小于中间的 pivot ，右边大于 pivot
     */
    private int partition(int[] arr, int l, int r) {
        // 设定基准值 pivot
        int pivot = arr[l];
        int i = l;
        for (int j = l + 1; j <= r; j++) {
            // 如果当前（索引为 j ）元素小于 pivot ，则交换
            if (arr[j] < pivot) {
                swap(arr, i + 1, j);
                i++;
            }// 否则(大于) j ++
        }
        // 交换 pivot（l） 及小于 pivot 部分末尾元素
        swap(arr, l, i);
        // 返回
        return i;
    }

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

归并排序（Merge Sort）

  归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

算法分析

  归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。

堆排序（Heap Sort）

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

计数排序（Counting Sort）

  计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

算法分析

  计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是 O(n+k) ，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序（Bucket Sort）

  桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

图片演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

算法分析

  桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序（Radix Sort）

  基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

算法分析

  基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

  基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k ，因此额外空间需要大概n个左右。

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            // 防止溢出
            int mid = l + (r - l) / 2;
            if (target == arr[mid]) {
                return mid;
            } else if (target < arr[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
}

参考资料

• 十大经典排序算法（动图演示）

文章信息