算法分析(2)经典排序算法对比

概述

上一篇文章分析了一下基本的排序算法以及Java的实现,不过没有比较深入的去分析,因为对于O(n^2)的算法实现比较简单,但是对于O(nLogn)的算法本身有些复杂,所以就分为两篇文章来写。评价算法的标准有很多,时间复杂度,空间复杂度以及稳定性等等。下面从两个方面来对经典排序算法进行总结一下:

正文

时间复杂度

时间复杂度分类

经典排序算法的时间复杂度大致可以分为以上两种,下面来通过一个表格来看一下:

对比 O(n^2) O(nLogn) 快的倍数
n = 10 100 100 3
n=100 10000 664 15
n=1000 10^6 9966 100
n=10000 10^8 132877 753
n=100000 10^10 1660964 6020

当数据量比较小的时候,O(nLogn)的优势并不明显,当数据量越来越大的时候,优势才更加明显

先写一个测试的通用的工具类SortUtils

public class SortUtils {
// 生成有n个范围在[rangeL, rangeR]的数组
static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
    assert rangeL <= rangeR;
    Integer[] arr = new Integer[n];
    for (int i = 0; i < n; i++)
  arr[i] = (int) (Math.random() * (rangeR - rangeL + 1) + rangeL);
    return arr;
}

// 生成一个有序数组, 之后随机交换swapTimes对
static Integer[] generateOrderedArray(int n, int swapTimes) {
    Integer[] arr = new Integer[n];
    for (int i = 0; i < n; i++)
        arr[i] = i;
    for (int i = 0; i < swapTimes; i++) {
        int a = (int) (Math.random() * n);
        int b = (int) (Math.random() * n);
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
    return arr;
}
}

通过反射测试排序算法:

 // 通过反射获取调用相应的方法
static void testSort(String sortClassName, Comparable[] arr) {
    // 通过Java的反射机制,通过排序的类名,运行排序函数
    try {
        // 通过sortClassName获得排序函数的Class对象
        Class sortClass = Class.forName(sortClassName);
        // 通过排序函数的Class对象获得排序方法
        Method sortMethod = sortClass.getMethod("sort", new Class[]{Comparable[].class});
        // 排序参数只有一个,是可比较数组arr
        Object[] params = new Object[]{arr};
        long startTime = System.currentTimeMillis();
        // 调用排序函数
        sortMethod.invoke(null, params);
        long endTime = System.currentTimeMillis();
        System.out.println(sortClass.getSimpleName() + " : " + (endTime - startTime) + "ms");
    } catch (Exception e) {
        e.printStackTrace();
    }
}

O(n^2)排序算法

编写测试方法

    Integer[] arr1 = SortUtils.generateRandomArray(N, 0, 20000);
    Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
    Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
    Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
    SortUtils.testSlow("com.wustor.slow.SelectionSort", arr1);
    SortUtils.testSlow("com.wustor.slow.InsertionSort", arr2);
    SortUtils.testSlow("com.wustor.slow.BubbleSort", arr3);
    SortUtils.testSlow("com.wustor.ShellSort", arr4);
测试随机数据

500条数据:

SelectionSort : 7ms
InsertionSort : 14ms
BubbleSort : 14ms
ShellSort : 0ms

1000条数据:

SelectionSort : 18ms
InsertionSort : 16ms
BubbleSort : 24ms
ShellSort : 1ms

5000条数据:

SelectionSort : 75ms
InsertionSort : 164ms
BubbleSort : 195ms
ShellSort : 9ms

20000条数据:

SelectionSort : 1265ms
InsertionSort : 1361ms
BubbleSort : 2999ms
ShellSort : 22ms

总结一下

随机数据 500条 1000条 5000条 20000条
SelectionSort 7ms 18ms 75ms 1265ms
InsertionSort 14ms 16ms 164ms 1361ms
BubbleSort 14ms 24ms 195ms 2999ms
ShellSort 0ms 1ms 9ms 22ms
测试有序数据

500条数据:

SelectionSort : 11ms
InsertionSort : 2ms
BubbleSort : 1ms
ShellSort : 3ms

1000条数据:

SelectionSort : 6ms
InsertionSort : 10ms
BubbleSort : 10ms
ShellSort : 1ms

5000条数据:

SelectionSort : 98ms
InsertionSort : 8ms
BubbleSort : 82ms
ShellSort : 3ms

20000条数据:

SelectionSort : 624ms
InsertionSort : 28ms
BubbleSort : 991ms
ShellSort : 20ms

总结一下

有序数据 500条 1000条 5000条 20000条
SelectionSort 11ms 6ms 98ms 624ms
InsertionSort 2ms 10ms 8ms 28ms
BubbleSort 1ms 24ms 82ms 991ms
ShellSort 3ms 1ms 3ms 20ms

通过对比可以发现,不管是测试有序还是无序的数据,希尔排序都是效率最高的。

O(nlogn)排序算法

编写测试方法

     public static void main(String[] args) {
        int T = 1000000;
        int N = 20000;
        // 比较 HeapSort、Shell Sort 和 Merge Sort 和 三种 Quick Sort 的性能效率
         Integer[] arr1 = SortUtils.generateRandomArray(T, 0, N);
       // Integer[] arr1 = SortUtils.generateOrderedArray(T, N);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
        Integer[] arr3 = Arrays.copyOf(arr1, arr1.length);
        Integer[] arr4 = Arrays.copyOf(arr1, arr1.length);
        long time1 = SortUtils.testFast("com.wustor.ShellSort", arr1);
        long time2 = SortUtils.testFast("com.wustor.fast.HeapSort", arr2);
        long time3 = SortUtils.testFast("com.wustor.fast.MergeSort", arr3);
        long time4 = SortUtils.testFast("com.wustor.fast.QuickSort", arr4);
        System.out.println("Sorting " + N + " elements " + T + " times. Calculate theRun Time.");
        System.out.println("Shell Sort       Run Time: " + time1 + " ms");
        System.out.println("Heap  Sort       Run Time: " + time2 + " ms");
        System.out.println("Merge Sort       Run Time: " + time3 + " ms");
        System.out.println("Quick Sort       Run Time: " + time4 + " ms");

    }
测试随机数据

因为只有数据量涉及到几十万甚至上百万的时候,才能体体现出O(nlogn)的优势
10000条数据:

Shell Sort       Run Time: 0 ms
Heap  Sort       Run Time: 0 ms
Merge Sort       Run Time: 93 ms
Quick Sort       Run Time: 0 ms

20000条数据:

Shell Sort       Run Time: 16 ms
Heap  Sort       Run Time: 15 ms
Merge Sort       Run Time: 0 ms
Quick Sort       Run Time: 0 ms

100000条数据:

Shell Sort       Run Time: 75 ms
Heap  Sort       Run Time: 44 ms
Merge Sort       Run Time: 110 ms
Quick Sort       Run Time: 62 ms

1000000条数据:

Shell Sort       Run Time: 1062 ms
Heap  Sort       Run Time: 734 ms
Merge Sort       Run Time: 281 ms
Quick Sort       Run Time: 282 ms

测试随机数据

随机数据 10000条 20000条 100000条 1000000条
Shell Sort 0ms 16ms 75ms 1062ms
Heap Sort 0ms 15ms 44ms 734ms
Merge Sort 93ms 0ms 110ms 281ms
Quick Sort 0ms 0ms 62ms 282ms
测试有序数据

10000条数据:

Shell Sort       Run Time: 0 ms
Heap  Sort       Run Time: 0 ms
Merge Sort       Run Time: 16 ms
Quick Sort       Run Time: 0 ms

20000条数据:

Shell Sort       Run Time: 16 ms
Heap  Sort       Run Time: 0 ms
Merge Sort       Run Time: 15 ms
Quick Sort       Run Time: 16 ms

100000条数据:

Shell Sort       Run Time: 77 ms
Heap  Sort       Run Time: 52 ms
Merge Sort       Run Time: 62 ms
Quick Sort       Run Time: 31 ms

1000000条数据:

Shell Sort       Run Time: 1086 ms
Heap  Sort       Run Time: 606 ms
Merge Sort       Run Time: 302 ms
Quick Sort       Run Time: 257 ms

测试有序数据

有序数据 10000条 20000条 100000条 1000000条
Shell Sort 0ms 16ms 77ms 1086ms
Heap Sort 0ms 0ms 52ms 606ms
Merge Sort 16ms 15ms 62ms 302ms
Quick Sort 0ms 16ms 31ms 282ms

对比分析,发现快排不管是对于有序的还是无序的数组,排序效率都比较高。

稳定性

定义:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。
根据这个定义来分析一下经典排序算法:

  • 简单选择排序:由于需要交换元素的位置,所以有可能会破坏原来的顺序,比如说7571,第一次交换之后,两个7之间的顺序就调换了。不稳定
  • 堆排序:在数据结构分析之二叉树中分析过二叉堆的数据结构,在堆排序之前需要将数组是生成一个二差堆,如果给定的二叉堆是数组是37556,那么进行生成二叉堆的时候层次遍历是35756,两个5相对顺序不变,但是取出最小值的时候,底部的元素进行上滤操作,后面的5会置顶,相对顺序被破坏。不稳定
  • 直接插入排序:只有当后面的元素大于前面的元素的时候才会进行交换,所以不会破坏相同元素的顺序。稳定
  • 希尔排序:分组的插入排序,虽然插入排序都是稳定的,但是每列之间的元素在排序之间会相互移动,这样就有可能导致相同元素之间的位置发生变化。不稳定
  • 冒泡排序:第一个比第二个大,才进行交换,所以元素相同的元素之间不会进行交换,相对位置也就不会发生变化。稳定
  • 快速排序:在分组的时候很容易把两个元素相同的位置进行交换,对于6225,分组的时候22之间的顺序会被打乱。不稳定
  • 归并排序:分组进行递归,递归到最后,每一个数组都是有序的,合并的时候,也是从左到右的,相同的元素不会进行交换,所以可以保证稳定性。稳定

下面用图片总结一下


算法稳定性分类

对比

算法 最大时间 平均时间 最小时间 辅助空间 稳定性
插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
冒泡排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
希尔排序 O(n^(3/2)) O(n^(3/2)) O(n^(3/2)) O(1) 不稳定
快速排序 O(n^2) O(nlogn) O(nlogn) O(logn) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

排序方法的选择

数据较小

有序
可采用直接插入排序。因为插入排序效率此时效率最高。
无序
采用直接插入排序或者直接选择排序

数据较大

快速排序在完全有序的情况下,会退化到O(n^2)级别,效率较低
有序
则应采用时间复杂度为 O(nLogn)的排序方法:堆排序或归并排序
无序
则应采用时间复杂度为 O(nLogn)的排序方法:快速排序、堆排序或归并排序

以上选择是在对排序算法稳定性没有要求的情况下进行选择的,如果需要排序稳定,则需要剔除不稳定的算法,在排序稳定的算法里面进行选择即可。

源码下载

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,164评论 0 52
  • 排序算法说明 (1)排序的定义:对一序列对象根据某个关键字进行排序; 输入:n个数:a1,a2,a3,…,an输出...
    BULL_DEBUG阅读 763评论 0 3
  • 慧鱼阅读 1,036评论 2 5
  • 今天看了电影《我的少女时代》,刚好这段时间有空而且电影终于免费了,可以重复观看。对这部电影的记忆还挺深,挂在心里有...
    晓来樱桃阅读 200评论 0 0
  • 今年三月,我来到这座小城 十多天了,雨一直下 春雨肯定窥视了这座小城的许多秘密 比你多得多吧 虽然你细数过每条小巷...
    如言阅读 114评论 0 0