文档章节

排序算法

Ocean_K
 Ocean_K
发布于 2018/08/02 11:48
字数 1206
阅读 6
收藏 0

     定义

     1. 排序

排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一类数据元素的任意序列,重新排列成一个关键字有序的序列

     2. 排序算法

在计算机科学与数学中,一个排序算法(Sorting algorithm)是一种能将一串数据依照特定排序方式进行排列的一种算法

     3. 排序方式

最常用到的排序方式是:

  • 数值顺序
  • 字典顺序

基本上,排序算法的输出必须遵守下列两个原则:

  • 输出结果为递增序列
  • 输出结果是原输入的一种排列、或是重组

虽然排序算法是一个简单的问题,但是从计算机科学发展以来,在此问题上已经有大量的研究。举例而言,冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题,有用的新算法仍在不断的被发明。(例子:图书馆排序在2004年被发表)

     分类

排序算法有很多很多,一般有4类分类方法:

  1. 依据排序方式

  2. 依据内存使用量(空间复杂度)

  3. 依据稳定性

  4. 依据计算的时间复杂度

     1. 按”排序方式”分类

  1. 交换排序 

    • 冒泡排序bubble
    • 快速排序quick
    • 鸡尾酒、奇偶、侏儒、臭皮匠、Bogo等
  2. 选择排序 

    • 选择排序
    • 堆排序
    • 平滑、笛卡尔树、锦标赛、圈排序等
  3. 插入排序 

    • 插入排序
    • 希尔排序
    • 伸展、二叉查找树、图书馆、耐心
  4. 归并排序 

    • 归并排序
    • 梯级归并、震荡归并等
  5. 分布排序

  6. 并发排序

  7. 混合排序

     2. 按”内存使用量”分类

  1. 内部排序

    内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列

    内排序是排序的基础,内排序效率用比较次数来衡量

    按所用策略不同,内排序又可分为:

    1. 交换排序 
      其中的快速排序,是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

    2. 选择排序

    3. 插入排序

    4. 归并排序

    5. 基数排序等

  2. 外部排序

    指在排序期间全部对象太多,不能同时存放在内存中,必须根据排序过程的要求,不断在内,外存间移动的排序

    在数据量大的情况下,只能分块排序,但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

     3. 依据”稳定性”分类

稳定性定义:

一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

稳定的

名字 English Name 时间复杂度
冒泡排序 bubble sort O(n^2)
插入排序 insertion sort O(n^2)

不稳定的

名字 English Name 时间复杂度
快速排序 quick sort O(nlog n)
选择排序 selection sort O(n^2)
希尔排序 shell sort O(nlog n)
堆排序 heap sort O(nlog n)

此外还有: 鸡尾酒排序 

     4. 依据计算的”时间复杂度”

一般而言,好的性能是O(nlogn),坏的性能是O(n^2),理想性能是O(n)

而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)

简要比较

名称 数据对象 稳定性 时间复杂度
平均 – 最坏
额外空间复杂度 描述
冒泡排序 数组 O(n2) O(1) 从无序区通过交换找出最大元素放到有序区前端
选择排序 数组、链表 数组×、链表√ O(n2) O(1) 从无序区找一个最小的元素跟在有序区的后面。
对数组:比较的多,换的少
插入排序 数组、链表 O(n2) O(1) 把无序区的第一个元素插入到有序区的合适位置。
对数组:比较的少,换的多
堆排序 数组 × O(n long n) O(1) 从堆顶把根卸出来放在有序区之前,再恢复堆
快速排序 数组 × O(n log n)–O(n2) O(log n) 小数,枢纽元,大数

© 著作权归作者所有

Ocean_K
粉丝 19
博文 104
码字总数 40133
作品 0
昌平
程序员
私信 提问
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
排序(上):冒泡排序、插入排序和选择排序

如何分析一个排序算法? 分析一个排序算法的三要素:排序算法的执行效率、排序算法的内存消耗以及排序算法的稳定性。 排序算法的执行效率 对于排序算法执行效率的分析,一般是从以下三个方面...

hardyyao
2018/11/04
0
0
排序算法——冒泡排序VS插入排序

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_26545305/article/details/87988991 一、概述 最经典、最常用的排序算法有:冒泡排序、插入排序、选择排序...

LemmonTreelss
03/04
0
0
Rxjs实践-各种排序算法排序过程的可视化展示

这几天学习下《算法》的排序章节,具体见对排序的总结,想着做点东西,能将各种排序算法的排序过程使用Rxjs通过可视化的方式展示出来,正好练系一下Rxjs的使用 本文不会太多介绍Rxjs的基本概念...

xiyuyizhi
2017/10/27
0
0
经典排序之 冒泡排序

Author: bakari Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为冒泡排序。 冒泡排序是最古老的排序,我们最早...

chambai
2012/08/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

硬件配置

https://akkadia.org/drepper/futex.pdf sudo lshw -businfo[sudo] lambda 的密码: Bus info Device Class Description======================================......

MtrS
57分钟前
2
0
springmvc的return “success”源码解读

qqqq

architect刘源源
今天
4
0
Java程序员五面阿里分享 逆袭成功 太不容易了!

前言 拿到阿里实习offer,经历了5次面试,其中4轮技术面,1轮HR面试。在这里分享一下自己的面试经验和学习心得。希望能够帮助更多的小伙伴。 我本科毕业于中南大学信管专业,真正开始学习Jav...

别打我会飞
昨天
4
0
Android Camera模块解析之视频录制

《Android Camera架构》 《Android Camera进程间通信类总结》 《Android Camera模块解析之拍照》 《Android Camera模块解析之视频录制》 《Android Camera原理之CameraDeviceCallbacks回调模...

天王盖地虎626
昨天
2
0
手把手教你使用issue作为博客评论系统

自从上周在阮一峰的 每周分享第 60 期 看到了可以将 GitHub 的 issue 当作评论系统,插入第三方网页的 JS 库——utterances。我就对此“魂牵梦绕”。个人博客使用的是VuePress。 TLDR (不多废...

jump--jump
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部