排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

它们的平均复杂度均为O(n^2),实现也比较简单。

1、直接插入排序对于规模很小的元素序列(n<=25)非常有效。它的时间复杂度与待排序元素序列的初始排列有关。在最好情况下,直接插入排序只需要n-1次比较就可以完成,而且不需要交换操作。在平均情况下和最差情况下,直接插入排序的比较和交换操作都是O(n^2).

2、冒泡排序在最好的情况下只需要一趟排序过程就可以完成,此时只需要n-1次比较操作,不需要交换操作。

3、简单选择排序的关键字比较次数与待排序元素序列的初始排序无关,其比较次数总是O(n^2),但元素移动次数则与待排序元素序列初始排列有关,最好情况下数据不需要移动,最坏情况下元素移动次数不超过3(n-1)次。

从空间复杂度来看,这三种基本的排序方法除了一个辅助元素外,都不需要额外的空间,从稳定性来看,直接插入排序和冒泡排序是稳定的,但简单选择排序不是。

二、对于中等规模的元素序列(n<=1000),希尔排序是一种很好的选择。

在希尔排序中,开始增量较大,分量较多,每个组内的记录数较少,因而记录的比较和移动次数较少,且移动距离较远;到后来步长越小(最后一步为1),分组越少,每个组内的记录数也越多,但同时记录次数也越来越接近有序,因而记录的比较和移动次数也都比较少。从理论上和实验上都已证明,在希尔排序中,记录的总的比较次数和总的移动次数比直接插入排序时少的多,特别是当n越大时效果越明显。而且希尔排序代码简单,基本不需要什么额外内存,但希尔排序是一种不稳定的排序算法。

三、对于元素个数n很大的情况,可以采用快排、堆排序、归并排序或基数排序,其中快速排序和堆排序都是不稳定的,而归并排序和基数排序是稳定的排序算法。

1、快速排序是最通用的高效的内排序算法,特别是它的划分思想经常在很多算法设计题中出现。平均情况下它的时间复杂度为O(nlog2N),一般情况下所需要的额外空间也是O(log2N)。但是快速排序在有些情况下也可能退化(例如元素序列已经有序时),时间复杂度会增加到O(n^2),空间复杂度也会增加到O(n)。但是我们可以通过“三者取中”法来避免最坏情况的发生。

2、堆排序也是一种高效的内排序算法,它的时间复杂度是O(nlog2N),而且没有什么最坏情况会导致堆排序的运行明显变慢,而且堆排序基本不需要额外的空间。但堆排序不太可能提供比快速排序更好的平均性能。

3、归并排序是一个重要的高效排序算法,它的一种重要特性是性能与输入元素序列无关,时间复杂度总是O(nlog2N),归并排序的主要缺点是需要O(n)的额外存储空间。

基数排序是一种相对特殊的排序算法,这类算法不仅是对元素序列关键字进行比较,更重要的是它们对关键字的不同部分进行处理和比较。虽然基数排序具有线性增长的时间复杂度,但是由于在常规编程环境中基数排序的线性时间开销实际上不比快速排序的时间开销小并且由于基数排序基于的关键字抽取算法受到操作系统和排序元素的影响,其适应性远不如普通的进行比较和交换操作的排序方法。因此在实际工作中,常规的高效排序算法如快速排序的应用要比基数排序广泛得多。基数排序需要的额外存储空间包括和待排序元素规模相同的存储空间以及与基数数目相等的一系列桶(一般用队列实现)。

四、混合使用

我们还可以把不同的排序算法混合使用,这也是得到普遍应用的一种算法改进方法,例如可以将直接插入排序集成到归并算法中。这种混合算法能够充分发挥不同算法各自的优势,从而在整体上得到更好的性能。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

视觉直观感受 7 种常用排序算法

2005
来自专栏目标检测和深度学习

排序算法算法对比

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3476
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

3225
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

632
来自专栏云霄雨霁

排序算法总结

1320
来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

3555
来自专栏杨建荣的学习笔记

重温快速排序(r4笔记第73天)

说起排序,总是会想起大名鼎鼎的快速排序,等自己再次翻开快速排序时,感觉是很陌生的,从这个对比也能看出自己确实是已经忘记了曾经重要的日子。 快速排序使用了分治思想...

3627
来自专栏java一日一条

面试中的 10 大排序算法总结

查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只...

1993
来自专栏desperate633

LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

732
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

4058

扫码关注云+社区

领取腾讯云代金券