04月01, 2018

O(n^2)级排序算法

本文总结了几种经典的O(n^2)级别的排序算法思想优化过程及适用场景。

SelectionSort-选择排序

alt

思想:

Selection-Sort是一种直观的简单排序算法。通过分别遍历元素与后继所有元素的比较,找出最小的元素位置并与之交换位置。以此类推直到遍历完整个数组从而完成排序。 alt

  • arr[i]arr[n]之间所有元素遍历,找到最小元素与之交换(swap)。

alt

  • arr[i+1]arr[n]之间所有元素遍历,找到最小元素与之交换(swap)。

alt

  • 直至遍历完数组,最终完成排序。
代码实现:
/**
* @title 选择排序 O(n^2)
* @description
* @author check321
* @date 2018/4/5 23:26
*/
@Component
public class SelectionSort extends BaseSortable implements Sortable {

    @Override
    @Profiler
    public void sort(Comparable[] arrs) {
         // 待排序元素
        for (int i = 0; i < arrs.length; i++) {
            int minIndex = i;
            // 遍历所有后继元素
            for (int j = i + 1; j < arrs.length; j++) {
                if (arrs[j].compareTo(arrs[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            commonUtils.swap(arrs,i,minIndex);
        }

    }
}
测试:
 Integer[] randomArrs = commonUtils.generateRandomArrs(10000, 1,10000);
  • 容量10000元素范围[1-10000]的随机数组的排序测试。

[main] 2018-04-05 23:31:36:648 - ---- Before Sorting ---- : [9650, 1028, 7359, 5133, 4820, 8251, 9415 ...] [main] 2018-04-05 23:31:37:274 - ---- Profiling Result ---- : Spend [610ms] on [net.check321.algorithms.sorting.basic.SelectionSort] [main] 2018-04-05 23:31:37:274 - ---- Sorting Result ---- : [1, 1, 2, 4, 4, 4, 5, 5, 6, 7, 9, 11, 11, 12, 16...] [main] 2018-04-05 23:31:37:283 - ---- Verify Result ---- : [true]

概述:

Selection-Sort算法的优势在于其实现思想便于理解,但是该算法需要从头至尾进行n^2次比较找出最小元素,缺少灵活性。在容量10000元素范围[1-10000]的随机数组测试中用时约为600ms

Insertion-Sort 插入排序

alt

思想:

Insertion-Sort算法的思想类似整理扑克牌顺序的过程——拿出待整理的牌然后将它插入至合适的位置。排序从数组第二个元素(arr[1])做为待排序元素开始,依次与前驱的元素比较,直至找到小于该元素的前驱元素或到达数组头部(arr[0])并将这个位置做为目标位置与待排序元素swap。遍历重复该过程至数组最后一个元素完成排序。 alt

  • arr[1]开始与arr[1-1]比较。

alt

  • 如果arr[i] < arr[i-1] || 到达数组头部便进行swap(),否则向前遍历。

alt

  • 遍历整个数组重复比较和swap()操作,最终完成排序。
代码实现:
/**
 * @author check321
 * @title 插入排序
 * @description
 * @date 2018/4/5 11:14
 */
@Component
public class InsertionSort extends BaseSortable implements Sortable {

    @Override
    @Profiler
    public void sort(Comparable[] arrs) {

        // 插入排序向前比较,故从第二元素开始
        for (int i = 1; i < arrs.length; i++) {
            // 内层循环,与前驱元素比较替换
            for (int j = i; j > 0 && arrs[j].compareTo(arrs[j -1]) < 0; j--) {
                commonUtils.swap(arrs, j, j-1);
            }
        }
    }
}

优化:该种实现在算法内层循环时发现待排序元素比前驱元素小时就进行swap()的方式在前驱元素比待排序元素小的占比大的情况下会频繁的swap()操作,一个swap()至少伴随着3次赋值操作,造成性能的浪费。所以将此操作优化,用操作index的方式替代swap()提示效率。

    // 内层循环优化
     for (int i = 1; i < arrs.length; i++) {
        // 记录待排序元素
        Comparable e = arrs[i];
        // 待插入index
        int j = i;
        for (; j > 0 && e.compareTo(arrs[j-1]) < 0; j--) {
            // 满足swap条件时,前驱元素移动至待排序元素位置
            arrs[j] = arrs[j-1];
        }
        // 最终j为待排序元素正确位置
        arrs[j] = e;
    }
测试:
 Integer[] randomArrs = commonUtils.generateRandomArrs(10000, 1,10000);
  • 容量10000元素范围[1-10000]的随机数组的排序测试。

    [main] 2018-04-06 00:42:43:407 ----- Before Sorting ---- : [8111, 5962, 2762, 2879, 571, 9284, ...] [main] 2018-04-06 00:42:43:737 - ---- Profiling Result ---- : Spend [324ms] on [net.check321.algorithms.sorting.basic.InsertionSort] [main] 2018-04-06 00:42:43:737 - ---- Sorting Result ---- : [2, 2, 3, 3, 4, 5, 7, 8, 8...] [main] 2018-04-06 00:42:43:747 - ---- Verify Result ---- : [true]

概述

Insertion-Sort算法虽然同为O(n^2)级别的算法,但是比起同级别的Selection-Sort在内层循环的逻辑控制上更加灵活(不满足条件时即可提前结束内层循环),所以在最理想状态也就是一个完全有序的数组下该算法复杂度会升级为O(n)(而相同情况下Selection-Sort还是要完成内外层两次循环,复杂度仍然为O(n^2))也正因为此特性Insertion-Sort特别适合处理近乎有序的序列排序。

对比测试:
Integer[] randomArrs = commonUtils.generateNearlyOrderedArrs(10000, 10);
  • 容量10000元素范围[1-10000]近乎有序数组的排序测试(随机交换10次元素位置)。

    [main] 2018-04-06 01:01:02:937 - ====================== Method Start ======================== [main] 2018-04-06 01:01:02:937 - ---- Before Sorting ---- : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9...] [main] 2018-04-06 01:01:03:591 - ---- Profiling Result ---- : Spend [637ms] on [net.check321.algorithms.sorting.basic.SelectionSort] main] 2018-04-06 01:01:03:591 - ---- Sorting Result ---- : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9...] [main] 2018-04-06 01:01:03:598 - ---- Verify Result ---- : [true] [main] 2018-04-06 01:01:03:598 - ====================== Method Start ======================== [main] 2018-04-06 01:01:03:598 - ---- Before Sorting ---- : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9...] [main] 2018-04-06 01:01:03:612 - ---- Profiling Result ---- : Spend [7ms] on [net.check321.algorithms.sorting.basic.InsertionSort] [main] 2018-04-06 01:01:03:612 - ---- Sorting Result ---- : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9...] [main] 2018-04-06 01:01:03:617 - ---- Verify Result ---- : [true]

从测试中看出,在近乎有序的数组排序中,Selection-Sort任然用时600+msInsertion-Sort仅为7ms

总结:

O(n^2)级别的排序算法做为基础算法,为我们提供了很好的算法思想基础,甚至在特定场景下达到很高的执行效率。所以时间复杂度只是在一个层面上反应算法的性能特征。充分了解算法的思想是灵活使用的算法的基础,如在近乎按时间顺序输出的日志系统中使用Insertion-Sort算法排序将会获得意想不到的效果。


alt

本文链接:https://check321.net/post/algorithms_basic_sort.html

-- EOF --

Comments

请在后台配置评论类型和相关的值。