如何检测社交网络中两个人是否是朋友关系（union-find 算法）

关注

发布于: 2021 年 02 月 22 日

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore
程序员常用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目：https://github.com/silently9527/mall-coupons-server
微信公众号：贝塔学 Java

前言

相信所有的程序员刚开始接触到的算法都会是排序算法，因为排序在对数据处理和计算有这重要的地位，排序算法往往是其他算法的基础；本文我们就先从初级排序算法开始学习算法。

排序算法的模板

在开始之前我们先定义一个排序算法通用的模板，在后面的排序算法都会实现这个模板

public interface SortTemplate {
    void sort(Comparable[] array);
    default void print(Comparable[] array) {        for (Comparable a : array) {            System.out.print(a + " ");        }    }
    default boolean less(Comparable a, Comparable b) {        return a.compareTo(b) < 0;    }
    default void exch(Comparable[] array, int i, int j) {        Comparable tmp = array[i];        array[i] = array[j];        array[j] = tmp;    }    }

复制代码

Comparable: 为了让我们实现的排序算法更加的通用，可以排序任意的对象，所以我们这里使用了 Comparable 数组
sort: 不同的排序算法实现的方式不一样，子类自己去实现
less: 定义的公用方法，如果 a < b 就返回 true
exch: 定义的公用方法，交换数组中的两个对象
print: 打印出数据中的每个元素

选择排序

算法实现的思路：

首先找到数组中的最小元素，
其实将它和数组中的第一个元素进行交换，这样就排定了一个元素；
再次找出剩余元素中最小的元素与数组中的第二个元素进行交换，如此反复直到所有元素都是有序的

代码实现：

public class SelectionSort implements SortTemplate {
    @Override    public void sort(Comparable[] array) {        int length = array.length;        for (int i = 0; i < length; i++) {            int min = i;            for (int j = i + 1; j < length; j++) {                if (less(array[j], array[min])) {                    min = j;                }            }            exch(array, i, min);        }    }
}

复制代码

假如输入的数组是有序的，我们会发现选择排序运行的时候和未排序的时间一样长！

对于 N 个元素的数组，使用选择排序的时间复杂度是 O(n²)

选择排序的是数据移动最少的，交换的次数与数组的大小是线性关系，N 个元素的数组需要 N 次交换

冒泡排序

算法实现的思路：

比较相邻的两个元素，如果前一个比后一个大，那么就交换两个元素的位置
对每一组相邻的元素执行同样的操作，直到最后一个元素，操作完成之后就可以排定一个最大的元素
如此往复，直到数组中所有的元素都有序

代码实现：

public class BubbleSort implements SortTemplate {
    @Override    public void sort(Comparable[] array) {        int length = array.length - 1;        for (int i = 0; i < length; i++) {            for (int j = 0; j < length - i; j++) {                if (less(array[j + 1], array[j])) {                    exch(array, j, j + 1);                }            }        }    }
}

复制代码

对于 N 个元素的数组，使用冒泡排序的时间复杂度是 O(n²)

插入排序

想象我们在玩扑克牌时，整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似

算法实现的思路：

初始默认第一个元素就是有序的，当前索引的位置从 0 开始
先后移动当前索引的位置，当前索引位置左边的元素是有序的，从后往前开始扫码与当前索引位置元素进行比较
当确定当前索引位置上的元素在左边有序适合的位置之后，插入到该位置上
如果当确定当前索引位置上的元素大于了已排序的最后一个元素，那么当前索引位置直接往后移动
如此反复，直到所有元素有序

代码实现：

public class InsertionSort implements SortTemplate {
    @Override    public void sort(Comparable[] array) {        int length = array.length;        for (int i = 1; i < length; i++) {            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) {                exch(array, j, j - 1);            }        }    }
}

复制代码

从代码的实现我们可以看出，当遇到了当前索引的元素大于了左边有序数组的最后一个元素时，内层循环就直接结束了，所以所我们排序的数组中存在着部分有序，那么插入排序算法会很快。

考虑最糟糕的情况，如果输入数组是一个倒置的，那么插入排序的效率和选择排序一样，时间复杂度是 O(n²)

希尔排序

对于大规模的乱序数组插入排序很慢，是因为它只交换相邻的元素，元素只能一点一点的从数组中移动到正确的位置；插入排序对于部分有序的数组排序是的效率很高；

希尔排序基于这两个特点对插入排序进行了改进；

算法实现的思路

首先设置一个步长 h 用来分隔出子数组
用插入排序将 h 个子数组独立排序
减小 h 步长继续排序子数组，直到 h 步长为 1
当步长为 1 时就成了普通的插入排序，这样数组一定是有序的

希尔排序高效的原因，在排序之初，各个子数组都很短，子数组排序之后都是部分有序的，这两种情况都很适合插入排序。

代码实现：

public class ShellSort implements SortTemplate {
    @Override    public void sort(Comparable[] array) {        int gap = 1;        int length = array.length;
        while (gap < length / 3) {            gap = 3 * gap + 1;        }
        while (gap >= 1) {            for (int i = gap; i < length; i++) {                for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {                    exch(array, j, j - gap);                }            }            gap = gap / 3;        }    }
}

复制代码

最后（点关注，不迷路）

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏

文中所有源码已放入到了 github 仓库https://github.com/silently9527/JavaCore
图片来源于网络
参考书籍：算法第四版

发布于: 2021 年 02 月 22 日阅读数: 15

原文链接:【http://xie.infoq.cn/article/6c1e64345719b07623560faeb】。文章转载请联系作者。

Silently9527

关注

公众号：贝塔学JAVA 2018.05.09 加入

Simple Programmer, Make the complex simple

发布

暂无评论

创作场景

如何检测社交网络中两个人是否是朋友关系（union-find 算法）

前言

排序算法的模板

选择排序

冒泡排序

插入排序

希尔排序

最后（点关注，不迷路）

Silently9527

评论