PHP数据结构(十七) ——内部排序综述

PHP数据结构(十七)——内部排序综述

(原创内容,转载请注明来源,谢谢)

一、稳定性

假设Ki=Kj(1<=i,j<=n,i!=j),且排在序列前的序列中Ri领先于Rj(即i>j)。

1)若在排序后的序列中,Ri必然仍领先于Rj,则称所用的排序方法是稳定的。

2)如果Ri可能出现在Rj之后的情况,则称所用的排序方法是不稳定的。

用一句话描述,就是原数组中两个相同的数字,一个在前一个在后,经过某种排序后(无论重新使用该方法排序多少次),仍一个在前一个在后,则称为稳定。

二、排序方式

区分方式:待排序记录数量不同,使的排序过程中涉及的存储器不同。

1)内部排序

待排序记录数量较少,存放于计算机随机存储器中进行排序。

2)外部排序

待排序记录数量较多,内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问。

三、内部排序分类

大致分为五类:插入排序、交换排序、选择排序、并归排序、计数排序。其中,时间复杂度可以分为三种:

1)简单排序方法,时间复杂度O(n2)

2)先进排序方法,时间复杂度O(nlogn)

3)基数排序方法,是将复杂度O(d*n)

四、排序过程

排序过程通常进行两个操作:

1)比较两个关键字的大小。

2)将记录从一个位置移动至另一个位置。

待排序记录有下列三种存储方式:

1)待排序的一组记录存放在地址连续的一组存储单元上,类似于线性表的顺序存储结构,序列中相邻的两个记录存储位置也相邻,排序需要借助移动记录。

2)(链)表排序:待排序的一组记录存放在静态链表中,记录的次序由指针指示,实现排序不需要移动记录,只需要修改指针即可。

3)地址排序:待排序记录本身存储在一组地址连续的存储单元内,另设一个指示各记录存储位置的地址向量,在排序过程中不移动记录本身,而是移动地址向量中记录的这些地址,拍些虚侯按照地址向量的值调整记录的存储位置。

五、各种内部排序方法比较

如下表所示:

排序方法

平均时间

最坏情况

辅助存储

简单排序

O(n2)

O(n2)

O(1)

快速排序

O(nlogn)

O(n2)

O(logn)

堆排序

O(nlogn)

O(nlogn)

O(1)

并归排序

O(nlogn)

O(nlogn)

O(n)

基数排序

O(d(n+rd))

O(d(n+rd))

O(rd)

1)平均性能而言,快速排序最佳,但最坏情况下不如堆排序和并归排序。堆排序和并归排序比较,n较大时并归排序所需时间较堆排序少,但所需的辅助存储量多。

2)简单排序包括除希尔排序之外的所有插入排序,冒泡排序,简单选择排序。当序列中的记录基本有序或n值较小时,用直接插入排序最佳,因此其可以和快速排序、并归排序结合在一起用。

3)基数排序时间复杂度也可以写成O(d*n),适用于n值很大而关键字较小的序列。如果关键字也很大,序列中大多数记录最高为关键字均不同,则也可以先按最高位关键字不同将序列分成若干小的子序列,再用直接插入进行排序。

4)稳定性比较

基数排序、简单排序都是稳定的,快速排序、堆排序、希尔排序不稳定。

一般而言,排序如果是通过比较相邻的关键字,则排序方法是稳定的,否则是不稳定的。稳定的排序,无论使用多少次,结果都是稳定的;不稳定的排序,经过多次使用后,总会出现不稳定的情况。

5)经过推论,借助于比较进行排序的算法,最坏情况下能达到最好的时间复杂度是O(nlogn)。

——written by linhxx 2017.07.16

相关阅读:

PHP数据结构(十六) ——B树

PHP数据结构(十五) ——哈希表​

PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-16

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java3y

八大基础排序总结

前言 大概花了一周的时间把八大基础排序过了一遍,这篇博文主要是用来回顾一下八大基础排序的要点和一些总结~ 回顾: 冒泡排序就这么简单 选择排序就这么简单 插入排...

3805
来自专栏技术换美食换不换

块状链表

的复杂度,而如果将整个块状链表维护成有序的,它甚至可以实现平衡树的一些操作[1],毕竟平衡树也可以看作是一种维护序列的方法。 又因为块状链表只在每个分块记录一...

682
来自专栏真皮专栏

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

622
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

442
来自专栏数据结构与算法

#106. 二逼平衡树(附带详细代码注释)

内存限制:512 MiB时间限制:4000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

3697
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版7.7节 set对象

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

731
来自专栏aCloudDeveloper

LeetCode:152_Maximum Product Subarray | 最大乘积连续子数组 | Medium

题目:Maximum Product Subarray Find the contiguous subarray within an array (contai...

1899
来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

622
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

VB.NET中图像处理的一些技巧以及其和C#图像处理的差距。

 早期的时候我使用的开发工具是VB6,VB6做图像处理的速度在我的软件Imageshop中有所体现,还是算可以的。目前,我已经改用C#来研究图像算法,C#中有...

1765
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

673

扫码关注云+社区