前言
算法就是编程的灵魂，不会算法的程序员只配做码农。算法的学习也是有着阶段性的，从入门到简单，再到复杂，再到简单。最后的简单是当你达到一定高度之后对于问题能够准确的找到最简单的解答。
介绍
算法里边最常用也是最基本的就是排序算法和查找算法了，本文主要讲解算法里边最经典的十大排序算法。在这里我们根据他们各自的实现原理以及效率将十大排序算法分为两大类：
- 非线性比较类排序：非线性是指算法的时间复杂度不能突破(nlogn)，元素之间通过比较大小来决定先后顺序。
- 线性非比较类排序：算法的时间复杂度能够突破(nlogn)，并且不通过比较来对元素排序。
具体分类我们上图说明：
算法比较
这里给出算法的时间复杂度，空间复杂度以及稳定性的对比整理，同样通过图片的形式给出：
-
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
-
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
-
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
-
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
下面就一一对十大算法进行详细的讲解，会给出他们的基本思想，图片演示，以及带有详细注释的源码。（本文所有的排序算法都是升序排序）
1 冒泡排序
1.1 基本思想
冒泡排序可以说是最简单的排序之一了，也是大部分人最容易想到的排序。即对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序。
1.2 算法步骤
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1.3 动态演示
1.4 算法特性
当输入的数据已经是正序时，冒泡排序最快；当输入的数据是反序时，冒泡排序最慢。
1.5 代码展示
public static void bubbleSort(int[] arr) {
if (arr == null)
return;
int len = arr.length;
//i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for (int i = 0; i < len - 1; i++) {
// j控制比较次数，第i次循环内需要比较len-i次
// 但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
for (int j = 0; j < len - i - 1; j++) {
// 如果前一个数比后一个数大，则交换位置将大的数往后放。
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
复制代码2 选择排序
2.1 基本思想
选择排序可以说是冒泡排序的改良版，不再是前一个数跟后一个数相比较， 而是在每一次循环内都由一个数去跟所有的数都比较一次，每次比较都选取相对较小的那个数来进行下一次的比较，并不断更新较小数的下标。这样在一次循环结束时就能得到最小数的下标，再通过一次交换将最小的数放在最前面，通过n-1次循环之后完成排序。相对于冒泡排序来说，比较的次数并没有改变，但是数据交换的次数大大减少。
2.2 算法步骤
-
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
-
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
-
重复第二步，直到所有元素均排序完毕。
2.3 动态演示
2.4 算法特性
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
2.5 代码展示
public static void selectSort(int[] arr) {
if (arr == null)
return;
int len = arr.length;
// i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
for (int i = 0; i < len - 1; i++) {
// minIndex 用来保存每次比较后较小数的下标。
int minIndex = i;
// j控制比较次数，因为每次循环结束之后最小的数都已经放在了最前面，
// 所以下一次循环的时候就可以跳过这个数，所以j的初始值为i+1而不需要每次循环都从0开始，并且j<len即可
for (int j = i + 1; j < len; j++) {
//每比较一次都需要将较小数的下标记录下来
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 当完成一次循环时，就需要将本次循环选取的最小数移动到本次循环开始的位置。
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第" + (i + 1) + "次循环之后效果：" + Arrays.toString(arr));
}
}
复制代码3 插入排序
3.1 基本思想
插入排序的思想打牌的人肯定很容易理解，就是见缝插针。首先就默认数组中的第一个数的位置是正确的，即已经排序。然后取下一个数，与已经排序的数按从后向前的顺序依次比较， 如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。 重复上一步骤，直到找到合适的位置。 找到位置后就结束比较的循环，将该数放到相应的位置。
3.2 算法步骤
-
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
-
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
3.3 动态演示
3.4 代码展示
public static void insertSort(int[] arr) {
if (arr == null)
return;
int len = arr.length;
// i控制循环次数，因为已经默认第一个数的位置是正确的，所以i的起始值为1，i<len，循环len-1次
for (int i = 1; i < len; i++) {
int j = i;//变量j用来记录即将要排序的数的位置即目标数的原位置
int target = arr[j];//target用来记录即将要排序的那个数的值即目标值
// while循环用来为目标值在已经排好序的数中找到合适的位置，
// 因为是从后向前比较，并且是与j-1位置的数比较，所以j>0
while (j > 0 && target < arr[j - 1]) {
// 当目标数的值比它当前位置的前一个数的值小时，将前一个数的位置向后移一位。
// 并且j--使得目标数继续与下一个元素比较
arr[j] = arr[j - 1];
j--;
}
// 更目标数的位置。
arr[j] = target;
//打印每次循环结束之后数组的排序状态（方便理解）
System.out.println("第" + (i) + "次循环之后效果：" + Arrays.toString(arr));
}
}
复制代码4 希尔排序
4.1 基本思想
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
-
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
-
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
4.2 算法步骤
-
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
-
按增量序列个数 k，对序列进行 k 趟排序；
-
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.3 动态演示
4.4 代码展示
public static void shellSort(int[] arr) {
if (arr == null)
return;
int len = arr.length; // 数组的长度
int k = len / 2; // 初始的增量为数组长度的一半
// while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
// 增量的最小值为1，即最后一次对整个数组做直接插入排序
while (k > 0) {
// 里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
// 所以直接将直接插入排序中的‘1’变为‘k’就可以了。
for (int i = k; i < len; i++) {
int j = i;
int target = arr[i];
while (j >= k && target < arr[j - k]) {
arr[j] = arr[j - k];
j -= k;
}
arr[j] = target;
}
// 不同增量排序后的结果
System.out.println("增量为" + k + "排序之后：" + Arrays.toString(arr));
k /= 2;
}
}
复制代码5 归并排序
5.1 基本思想
总体概括就是从上到下递归拆分，然后从下到上逐步合并。
- 递归拆分：
先把待排序数组分为左右两个子序列，再分别将左右两个子序列拆分为四个子子序列，以此类推直到最小的子序列元素的个数为两个或者一个为止。
- 逐步合并：
将最底层的最左边的一个子序列排序，然后将从左到右第二个子序列进行排序，再将这两个排好序的子序列合并并排序，然后将最底层从左到右第三个子序列进行排序..... 合并完成之后记忆完成了对数组的排序操作（一定要注意是从下到上层级合并，可以理解为递归的层级返回）
5.2 算法步骤
-
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
-
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
-
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
-
重复步骤 3 直到某一指针达到序列尾；
-
将另一序列剩下的所有元素直接复制到合并序列尾。
5.3 动态演示
5.4 算法特性
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
5.5 代码展示
/**
* 递归拆分
* @param arr 待拆分数组
* @param left 待拆分数组最小下标
* @param right 待拆分数组最大下标
*/
public static 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); // 合并左右
}
}
/**
* 合并两个有序子序列
* @param arr 待合并数组
* @param left 待合并数组最小下标
* @param mid 待合并数组中间下标
* @param right 待合并数组最大下标
*/
public static 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循环能够初步筛选出待合并的了两个子序列中的较小数
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];
}
}
复制代码6 快速排序
6.1 基本思想
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
6.2 算法步骤
快速排序也采用了分治的策略，这里引入了‘基准数’的概念。
-
从数列中挑出一个元素，称为 “基准”（pivot）;
-
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
-
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.3 算法特性
在平均状况下，快速排序排序 n 个项目需要要 Ο(nlogn) 次比较，在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
6.4 动态演示
6.5 代码展示
/**
* 分区过程
* @param arr 待分区数组
* @param left 待分区数组最小下标
* @param right 待分区数组最大下标
*/
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int temp = qSort(arr, left, right);
quickSort(arr, left, temp - 1);
quickSort(arr, temp + 1, right);
}
}
/**
* 排序过程
* @param arr 待排序数组
* @param left 待排序数组最小下标
* @param right 待排序数组最大下标
* @return 排好序之后基准数的位置下标，方便下次的分区
*/
public static int qSort(int[] arr, int left, int right) {
int temp = arr[left]; // 定义基准数，默认为数组的第一个元素
while (left < right) { // 循环执行的条件
// 因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
// 如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
while (left < right && arr[right] > temp) {
right--;
}
// 跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
// 这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
if (left < right) {
arr[left++] = arr[right];
}
// 下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
// 因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
while (left < right && arr[left] <= temp) {
left++;
}
// 跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if (left < right) {
arr[right--] = arr[left];
}
}
// 当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
// 这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
arr[left] = temp;
return left;
}
复制代码7 堆排序
7.1 基本思想
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
-
大顶堆：每个结点的值都大于它的左右子结点的值，升序排序用大顶堆。
-
小顶堆：每个结点的值都小于它的左右子结点的值，降序排序用小顶堆。
7.2 算法步骤
-
创建一个堆 H[0……n-1]；
-
把堆首（最大值）和堆尾互换；
-
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
-
重复步骤 2，直到堆的尺寸为 1。
7.3 动态演示
7.4 代码展示
public static void heapSort(int[] arr) {
if (arr == null) {
return;
}
int len = arr.length;
// 初始化大顶堆（从最后一个非叶节点开始，从左到右，由下到上）
for (int i = len / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, len);
}
// 将顶节点和最后一个节点互换位置，再将剩下的堆进行调整
for (int j = len - 1; j > 0; j--) {
swap(arr, 0, j);
adjustHeap(arr, 0, j);
}
}
/**
* 整理树让其变成堆
* @param arr 待整理的数组
* @param i 开始的结点
* @param 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;
}
/**
* 交换数据
* @param arr
* @param num1
* @param num2
*/
public static void swap(int[] arr, int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
复制代码8 计数排序
8.1 基本思想
计数排序采用了一种全新的思路，不再是通过比较来排序，而是将待排序数组中的最大值+1作为一个临时数组的长度，然后用临时数组记录待排序数组中每个元素出现的次数。最后再遍历临时数组，因为是升序，所以从前到后遍历，将临时数组中值>0的数的下标循环取出，依次放入待排序数组中，即可完成排序。计数排序的效率很高，但是实在牺牲内存的前提下，并且有着限制，那就是待排序数组的值必须 限制在一个确定的范围。
8.2 动态演示
8.3 代码展示
public static void countSort(int[] arr) {
if (arr == null)
return;
int len = arr.length;
// 保存待排序数组中的最大值，目的是确定临时数组的长度（必须）
int maxNum = arr[0];
// 保存待排序数组中的最小值，目的是确定最终遍历临时数组时下标的初始值（非必需，只是这样可以加快速度，减少循环次数）
int minNum = arr[0];
// for循环就是为了找到待排序数组的最大值和最小值
for (int i = 1; i < len; i++) {
maxNum = maxNum > arr[i] ? maxNum : arr[i];
minNum = minNum < arr[i] ? minNum : arr[i];
}
// 创建一个临时数组
int[] temp = new int[maxNum + 1];
// for循环是为了记录待排序数组中每个元素出现的次数，并将该次数保存到临时数组中
for (int i = 0; i < len; i++) {
temp[arr[i]]++;
}
// k=0用来记录待排序数组的下标
int k = 0;
// 遍历临时数组，重新为待排序数组赋值。
for (int i = minNum; i < temp.length; i++) {
while (temp[i] > 0) {
arr[k++] = i;
temp[i]--;
}
}
}
复制代码9 桶排序
9.1 基本思想
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
-
在额外空间充足的情况下，尽量增大桶的数量
-
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
9.2 图片演示
9.3 算法特性
桶排序利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
-
在额外空间充足的情况下，尽量增大桶的数量
-
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
当输入的数据可以均匀的分配到每一个桶中的时候桶排序最快,当输入的数据被分配到了同一个桶中的时候最慢。
9.4 代码展示
public static void bucketSort(int[] arr) {
if (arr == null)
return;
int len = arr.length;
// 定义桶的个数，这里k的值要视情况而定，这里我们假设待排序数组里的数都是[0,100)之间的。
int k = 10;
// 用嵌套集合来模拟桶，外层集合表示桶，内层集合表示桶里边装的元素。
List<List<Integer>> bucket = new ArrayList<>();
//for循环初始化外层集合即初始化桶
for (int i = 0; i < k; i++) {
bucket.add(new ArrayList<>());
}
// 循环是为了将待排序数组中的元素通过映射函数分别放入不同的桶里边
for (int i = 0; i < len; i++) {
bucket.get(mapping(arr[i])).add(arr[i]);
}
// 这个循环是为了将所有的元素个数大于1的桶里边的数据进行排序。
for (int i = 0; i < k; i++) {
if (bucket.size() > 1) {
// 因为这里是用集合来模拟的桶所以用java写好的对集合排序的方法。
// 其实应该自己写一个方法来排序的。
Collections.sort(bucket.get(i));
}
}
// 将排好序的数重新放入待排序数组中
int m = 0;
for (List<Integer> list : bucket) {
if (list.size() > 0) {
for (Integer a : list) {
arr[m++] = a;
}
}
}
}
/**
* 映射函数
* @param num
* @return
*/
public static int mapping(int num) {
return num / 10;
}
复制代码10 基数排序
10.1 基本思想
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
10.2 动态演示
10.3 代码展示
public static void main(String[] args) {
int[] arr = {720, 6, 57, 88, 60, 42, 83, 73, 48, 85};
redixSort(arr, 10, 3);
System.out.println(Arrays.toString(arr));
}
public static void redixSort(int[] arr, int radix, int d) {
// 缓存数组
int[] tmp = new int[arr.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计下一个关键字
Arrays.fill(buckets, 0);
// 将data中的元素完全复制到tmp数组中
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 计算每个待排序数据的子关键字
for (int j = 0; j < arr.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子关键字对指定的数据进行排序
for (int m = arr.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
arr[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
复制代码参考资料
本帐号将持续分享后端技术干货，包括虚拟机基础，多线程编程，高性能框架，异步、缓存和消息中间件，分布式和微服务，架构学习和进阶等学习资料和文章。
近期评论