排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序外部排序

内部排序是数据记录在内存中进行排序。

外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

常见的内部排序算法有:插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。

十大排序算法时间复杂度:

1571058315-4e87395f327c9c8.png

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

关于原地排序

原地排序算法:冒泡排序、插入排序、选择排序、快速排序

不是原地排序算法:归并排序、计数排序、桶排序、基数排序

如何选择合适排序算法:

  1. 如果对小规模数据进行排序,可以选择时间复杂度为O(n2)算法。

  2. 如果对大规模数据进行排序,可以选择时间复杂度为O(nlogn)算法更加高效。



总结:为了兼顾任意规模数据的排序,一般都是首选时间复杂度为O(nlogn)的排序算法来实现排序函数

为什么一般生成环境比较少使用归并排序?

  1. 归并排序不是原地排序算法,所以如果要排序200mb的数据,出了数据本身占用的内存之外,排序算法还需额外占用200mb的内存空间,所以空间耗费需要翻倍。

参考:

https://www.cxyxiaowu.com/2090.html

https://time.geekbang.org/column/article/42359

本文地址: http://chenxm.cc/article/984.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: python 排序算法——线性排序之基数排序(Radix sort)
下一篇: 阿里云 宝塔 mongodb允许外部访问
发表评论
  1. 缝纫机
    缝纫机  @回复

    太高深了,完全看不懂