文档章节

排序

BK灬
 BK灬
发布于 2016/07/28 10:37
字数 535
阅读 35
收藏 1
排序大的分类可以分为两种:内排序和外排序.在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序.下面讲的排序都是属于内排序.

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

(1)、插入排序:直接插入排序、二分法插入排序、希尔排序.

(2)、选择排序:简单选择排序、堆排序.

(3)、交换排序:冒泡排序、快速排序.

(4)、归并排序

(5)、基数排序

总结:

一、稳定性:

    稳定:冒泡排序、插入排序、归并排序和基数排序

  不稳定:选择排序、快速排序、希尔排序、堆排序

二、平均时间复杂度

  O(n^2):直接插入排序,简单选择排序,冒泡排序.

  在数据规模较小时(9W),内直接插入排序,简单选择排序差不多.当数据较大时,冒泡排序算法的时间代价最高.性能为O(n^2)的算法基本上是相邻元素进行比较,基本上都是稳定的.

  O(nlogn):快速排序,归并排序,希尔排序,堆排序.

  其中,快排是最好的, 其次是归并和希尔,堆排序在数据量很大时效果明显.

三、排序算法的选择

  1.数据规模较小

    (1)待排序列基本序的情况下,可以选择直接插入排序

    (2)对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡

  2.数据规模不是很大

  (1)完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出log(N)的额外空间.

  (2)序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序

  3.数据规模很大

   (1)对稳定性有求,则可考虑归并排序。

   (2)对稳定性没要求,宜用堆排序

  4.序列初始基本有序(正序),宜用直接插入,冒泡

 

本文转载自:http://www.cnblogs.com/liuling/p/2013-7-24-01.html

上一篇: 直接插入排序
下一篇: 冒泡排序
BK灬

BK灬

粉丝 46
博文 345
码字总数 142921
作品 0
朝阳
后端工程师
私信 提问

暂无文章

Java 文件类操作API与IO编程基础知识

阅读目录: https://www.w3cschool.cn/java/java-io-file.html Java 文件 Java 文件 Java 文件操作 Java 输入流 Java 输入流 Java 文件输入流 Java 缓冲输入流 Java 推回输入流 Java 数据输入...

boonya
22分钟前
2
0
SDKMAN推荐一个好

是在大多数基于Unix的系统上管理多个软件开发工具包的并行版本的工具。它提供了一个方便的命令行界面(CLI)和API来安装,切换,删除和列出sdk相关信息。以下是一些特性: By Developers, fo...

hotsmile
46分钟前
8
0
什么是 HDFS

是什么? HDFS 是基于 Java 的分布式文件系统,允许您在 Hadoop 集群中的多个节点上存储大量数据。 起源: 单机容量往往无法存储大量数据,需要跨机器存储。统一管理分布在集群上的文件系统称...

Garphy
49分钟前
5
0
一起来学Java8(四)——复合Lambda

在一起来学Java8(二)——Lambda表达式中我们学习了Lambda表达式的基本用法,现在来了解下复合Lambda。 Lambda表达式的的书写离不开函数式接口,复合Lambda的意思是在使用Lambda表达式实现函...

猿敲月下码
今天
10
0
debian10使用putty配置交换机console口

前言:Linux的推广普及,需要配合解决实际应用方能有成效! 最近强迫自己用linux进行实际工作,过程很痛苦,还好通过网络一一解决,感谢各位无私网友博客的帮助! 系统:debian10 桌面:xfc...

W_Lu
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部