Sorts


Sorts

本文主要介绍几种常见的排序算法,以及 Bloom 过滤器。

排序

在正式介绍排序之前,先说下排序中的几个名词:

  • 稳定 : 我们常说,这个排序算法是稳定的,那个是不稳定的,这里的稳定,是指,两个相同大小的元素 a,b ,在排序前后,他们的相对位置未发生变化。我们假设 ai = bj , 其中 i < j, 在排序后,变成了 am , bn ,此时仍有 m < n ,则我们说该排序算法是稳定的。
  • 内排序:所有的排序过程,都是在内存中完成
  • 外排序:排序过程需要通过磁盘和内存一起完成

冒泡排序

Bubble Sort 。顾名思义,就是通过一遍遍的比较,逐步将未排序元素集合中的最大值,移动到集合的最末尾。整个排序过程,就如同小鱼吐泡泡一样,一个一个往上飘。

double for , 第一层 for 用来记录已经排序的元素个数,第二层 for 用来做未排序元素集合中,两两相邻元素的比较

O(n2), 代码实现:

private static void bubbleSort() {
    var confusion = new int[]{6, 9, 3, 7, 3, 8, 1, 2};
    for (int i = 0; i < confusion.length - 1; i++) {
        for (int j = 0; j < confusion.length - 1 - i; ++j) {
            if (confusion[j] > confusion[j + 1]) {
                var tmp = confusion[j];
                confusion[j] = confusion[j + 1];
                confusion[j + 1] = tmp;
                // 两个数的交换, 还可以这样写
                // confusion[j] ^= confusion[j + 1];
                // confusion[j + 1] ^= confusion[j];
                // confusion[j] ^= confusion[j + 1];
            }
        }
    }
    System.out.println("Bubble Sort:" + Arrays.toString(confusion));
}

选择排序

依次遍历,每次选出未排序集合中最小或者最大的元素,放到已排序集合中。

double for , 第一层 for 用来记录已排序的元素个数,第二层 for 用来挑选未排序集合中最小或最大元素,和已排序集合中的最末尾位置比较,如果小/大, 则交换。即不断找出未排序集合中最小(最大值)。

O(n2) , 代码实现:

private static void selectionSort(final int[] ary) {
    int length = ary.length;
    for (int i = 0; i < length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < length ; j++) {
            if (ary[j] < ary[min]) {
                min = j;
            }
        }
        if (ary[i] > ary[min]) {
            swap(ary, i, min);
        }
    }
    System.out.println("Selection Sort:" + Arrays.toString(ary));
}

插入排序

依次遍历, 每次选择一个未排序集合中的数, 往前插入到已排序集合中的合适位置。

与选择排序相似,不同的是, 选择排序,是选择最小的数往前插, 这样可以保证已排序的元素集合,在整个集合里,是正确有序的。而插入排序是选择一个数,往前插入到合适位置,已排序集合在整个集合里,是相对有序的。

double for , 第一层 for 用来记录已排序元素个数,第二层 for 用来挑选后一个元素,并插入到已排序元素集合的合适位置。

O(n2) ,代码实现:

private static void insertionSort2(final int[] ary) {
    int pre; // 记录前一个数据
    for (int i = 1; i < ary.length; i++) {
        var tmp = ary[i];
        for (pre = i - 1; pre > 0 && (tmp < ary[pre - 1]); pre--) {
            // 整体后移一位
            ary[pre] = ary[pre - 1];
        }
        ary[pre] = tmp;
    }
    System.out.println(Arrays.toString(ary));
}

归并排序

O(NlogN) 。

通过对左右两边不断分治、毕竟,直到有序(此时左右各只有一个元素),然后进行合并。

归并的核心思想是先分后合。

private static void doMergeSort(int[] ary, int[] tmp, int left, int right) {
    if (left < right) {
        var center = (left + right) / 2;
        doMergeSort(ary, tmp, left, center);
        doMergeSort(ary, tmp, center + 1, right);
        doMerge(ary, tmp, left, center + 1, right);
    }
}

private static void doMerge(int[] ary, int[] tgt, int leftPos, int rightPos, int rightEnd) {
    var leftEnd = rightPos - 1;
    var tmpPos = leftPos;
    var numE = rightEnd - leftPos + 1;

    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (ary[leftPos] <= ary[rightPos]) {
            tgt[tmpPos++] = ary[leftPos++];
        } else {
            tgt[tmpPos++] = ary[rightPos++];
        }
    }
    while (leftPos <= leftEnd) {
        tgt[tmpPos++] = ary[leftPos++];
    }
    while (rightPos <= rightEnd) {
        tgt[tmpPos++] = ary[rightPos++];
    }
    // 回填, 因为上面合并后的数据都在 tgt 中
    for (var i = 0; i < numE; i++, rightEnd--) {
        ary[rightEnd] = tgt[rightEnd];
    }
}

快速排序

快速排序在实际项目中是用的比较多的, java 中 Arrays.sort 方法里,使用的就是经过优化的变种快速排序。

在排序元素较少的情况下,快速排序的表现不如插入排序, java 在排序的时候,会首先判断元素的个数,当元素少于 INSERTION_SORT_THRESHOLD (47) 时, 会使用插入排序,至于为何是这个数字,我也不知道了。。。

如果在 QUICKSORT_THRESHOLD (286) 内,则使用快速排序,超过这个长度,会首先判断待排序集合是否是部分有序,是则使用快速排序,否则使用归并排序。

可见,真正在项目中,即使是排序,也有太多的讲究。

回到快速排序。快速排序的核心思想是分治。通过不断的替换基准( pivot ),来切割集合,使左边元素小于基准,右边元素大于基准,最终达到整体有序。

一种实现思路是,选择一个基准。基准选择有很多学问,java 中的快排,采用五基数 + 三路快排实现的,一般可以尝试使用中值作为基准,即获取集合首尾以及中间值,取居中的数值作为基准。

然后分别从左右往中间递进,左边 idx = i 遇到 > pivot 停下,右边 idx = j 遇到 < pivot 停下,交换两个数的位置,直到 i >= j 停下。

一遍下来后,i 左边元素都小于 pivot , i 右边元素都大于 pivot 。

交换 ary[i] 和 pivot 的位置。

分别对 [0, i-1] 和 [i+1, array.length] 递归上述步骤,直到 left >= right 。

以下是具体实现:

private static void doQuickSort(final int[] ary, int left, int right) {
    var low = left;
    var high = right;
    if (low >= high) {
        return;
    }

    var pivot = ary[right];

    while (low < high) {
        while (ary[low] <= pivot && low < high) {
            low++;
        }

        while (ary[high] >= pivot && low < high) {
            high--;
        }
        if (low < high) {
            swap(ary, low, high);
        }
    }
    // swap
    ary[right] = ary[low];
    ary[low] = pivot;

    doQuickSort(ary, left, low - 1);
    doQuickSort(ary, low + 1, right);
}

Bloom Filter

布隆过滤器,常用来做一些大数据量的非精确性的过滤处理。如海量黑名单检查,垃圾邮件过滤等。

布隆过滤器的本质,是利用 hash ,将一个 key ,通过一组(设为 n) hash func ,映射到 n 个 bit 位。

bloom filter 初始化时,会开辟一块内存空间,将其中的 bit 位置为 0 ,我们插入元素时, 会通过一组 hash 函数,计算得到 n 个 bit 地址,将其置为 1。

查询时,通过一组 hash 计算 key ,查看各个 bit 位是否为 1, 如果都为 1, 则表示存在,否则不存在。

我们直到,hash 存在 hash 碰撞,这表示,即使查出某个 key 的 bit 位都为 1, 我们也不能说该 key 一定存在,因为可能某个 bit 位,是因为 hash 碰撞,被另一个 key 设为了 1。

当然,这个概率是很小的。

也只有在我们能接收这样的误判时,我们才能够使用 bloom filter。

Bloom Filter

代码部分是 guava 的 bloom filter 实现:

static class PersonFunnel implements Funnel<Person> {
    @Override
    public void funnel(Person from, PrimitiveSink into) {
        into.putString(from.getName(), Charset.defaultCharset()).putInt(from.getAge());
    }
}

private static void bloomFilter() {
    // 大约插入的元素个数 10, 以及误判率 0.01 (根据给定数据,计算需要开辟的空间大小)
    var bloomFilter = BloomFilter.create(new PersonFunnel(), 10, 0.01);
    var exist1 = bloomFilter.mightContain(new Person(18, "dylan"));
    bloomFilter.put(new Person(18, "dylan"));
    var exist2 = bloomFilter.mightContain(new Person(18, "dylan"));
    System.out.println("first:" + exist1 + ", then: " + exist2); // false  true
}

Reference

基础排序算法–动画演示


文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
java class loading java class loading
Java 的加载机制这里我先要说下类和对象。 java 中,可以将一组特征放到一个 class 里面,我们称之为类,是一个抽象概念。 而对象则是这个类的具象。 比如清华大学之于大学。 那我们说 java 的加载机制,事实上说的是类的加载机制
2020-04-29
下一篇 
Tree Algorithm Tree Algorithm
我们知道, java 8 之后, HashMap 的底层结构做了优化。原来所有 hash 碰撞的元素,都是存储在链表中,现在当链表长度大于 8 时,就会转变成红黑树。那么什么是红黑树呢? 本篇文章将从最基础的树讲起,一步步带你揭开红黑树的面纱。
2020-04-23
  目录