《排序算法系列0》排序概述

时间：2020-04-11 15:36:39 阅读：87 评论：0 收藏：0 [点我收藏+]

排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用。因此，我们很有必要对所有常见的排序算法进行归纳。

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

内排序有可以分为以下几类：

　　(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。

　　(2)、选择排序：直接选择排序、堆排序。

　　(3)、交换排序：冒泡排序、快速排序。

　　(4)、归并排序

　　(5)、基数排序

表格版:

排序方法	时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
直接插入排序	$O (n^{2})$	$O (n^{2})$	$O (n)$	$O (1)$	稳定	简单
希尔排序	$O (n l o g_{2} n)$	$O (n^{2})$	$O (n)$	$O (1)$	不稳定	较复杂
直接选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	不稳定	简单
堆排序	$O (n l o g_{2} n)$	$O (n l o g_{2} n)$	$O (n l o g_{2} n)$	$O (1)$	不稳定	较复杂
冒泡排序	$O (n^{2})$	$O (n^{2})$	$O (n)$	$O (1)$	稳定	简单
快速排序	$O (n l o g_{2} n)$	$O (n^{2})$	$O (n l o g_{2} n)$	$O (n l o g_{2} n)$	不稳定	较复杂
归并排序	$O (n l o g_{2} n)$	$O (n l o g_{2} n)$	$O (n l o g_{2} n)$	$O (n)$	稳定	较复杂
基数排序	$O (d (n + r))$	$O (d (n + r))$	$O (d (n + r))$	$O (n + r)$	稳定	较复杂

图片版:

《排序算法系列0》排序概述

原文：https://www.cnblogs.com/wangxiucai/p/12679667.html

踩

(0)

评论一句话评论（0）

分享档案

更多>