`
owenyang
  • 浏览: 14967 次
  • 性别: Icon_minigender_1
  • 来自: 济南
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

数据结构--排序方法

阅读更多

排序的稳定性

 ??? 当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。
???  在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的
? 注意:
 ??? 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。

排序方法的分类

1.按是否涉及数据的内、外存交换分

???  在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序
? 注意:
 ??? ① 内排序适用于记录个数不很多的小文件
???  ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。

2.按策略划分内部排序方法
???  可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。

?

插入排序:直接插入排序和希尔排序

交换排序:冒泡排序和快速排序

选择排序:直接选择排序和堆排序

归并排序:

分配排序:箱排序和基数排序

插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
???  本节介绍两种插入排序方法:直接插入排序和希尔排序。

直接插入排序基本思想

1、基本思想

???  假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。
希尔排序基本思想

? 基本思想:
 ??? 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2<d<sub>1重复上述的分组和排序,直至所取的增量dt=1(dt<d<sub>t-l<…<d<sub>2<d<sub>1),即所有记录放在同一组中进行直接插入排序为止。
???  该方法实质上是一种分组插入方法。
 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
???  应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

冒泡排序

1、排序方法

???  将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
快速排序(QuickSort)

1、算法思想
???  快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
 选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。
???  常用的选择排序方法有直接选择排序和堆排序。

直接选择排序(Straight Selection Sort)

1、直接选择排序的基本思想

???  n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
?①初始状态:无序区为R[1..n],有序区为空。
?②第1趟排序
???  在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
  ……
?③第i趟排序
  第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
???  这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
堆排序

1、 堆排序定义
???  n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
???  (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

???  若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

两路归并算法

1、算法基本思路

???  设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。
分配排序的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。

箱排序(Bin Sort)

1、箱排序的基本思想

???  箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。
【例】要将一副混洗的52张扑克牌按点数A<2<…<j<q<k排序,需设置13个"箱子",排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌。< p="">

基数排序?

???  基数排序(Radix Sort)是对箱排序的改进和推广。

1、单关键字和多关键字

???  文件中任一记录R[i]的关键字均由d个分量
????????????????????
构成。
若这d个分量中每个分量都是一个独立的关键字,则文件是多关键字的(如扑克牌有两个关键字:点数和花色);否则文件是单关键字的,
??????????????
(0≤j<d)只不过是关键字中其中的一位(如字符串、十进制整数等)。<br> ??? 多关键字中的每个关键字的取值范围一般不同。如扑克牌的花色取值只有4种,而点数则有13种。单关键字中的每位一般取值范围相同。

分享到:
评论

相关推荐

    数据结构--快速排序C++源代码

    数据结构--快速排序C++源代码,自己编写调试,代码简单易懂,不长

    数据结构- C语言 -排序.md

    数据结构- C语言 -排序.md

    数据结构---二叉排序树.doc

    数据结构---二叉排序树.doc

    数据结构-----排序

    计算机专业 上机报告 数据结构上机报告-----排序

    数据结构--排序--思维导图.pdf

    "数据结构--排序--思维导图" 数据结构中排序是指将一组无序的记录序列按照一定的规则排列成有序的序列,排序的目的是为了提高数据的存储和检索效率。排序算法的稳定性是指在排序过程中,如果待排序表中有两个元素Ri...

    数据结构---二叉排序树

    数据结构实验程序---二叉排序树的生成。该课题是用来描述二叉排序树的,给定一列整型的数据(无序),按照二叉排序树的思想将该列数据排成一个有序的序列(通过中序遍历该二叉树可以得到一个非递减有序序列)。通过...

    数据结构--课程设计(多种排序算法 有界面)

    数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面 数据结构 课程设计 多种排序算法 有界面

    22%-数据结构-c语言-排序算法(8种).ppt

    - 堆排序:使用堆这种数据结构,将待排序的序列构造成一个大顶堆(或小顶堆),然后依次将堆顶元素与末尾元素交换,再调整堆。 4. 归并排序:采用分治策略,将数组分为两半,分别排序后再合并,保证排序稳定性。 ...

    数据结构--九种排序算法 --排序001.cpp

    此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!

    数据结构-排序课件

    数据结构-排序课件,严蔚敏课本课件,比较好用

    图解数据结构--使用Java

    利用大量且丰富的图示与范例, 详解复杂的抽象理论,从最基本的数据结构概念开始 说明,再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念,引领读者抓住重 点轻松进入数据结构的学习领域

    数据结构------排序

    常见的集中排序算法 冒泡排序 快速排序 。。。。。。。。。。。。。。。。

    数据结构--排序 很细致

    数据结构中的排序是计算机科学中一个基础且重要的概念,它涉及到如何有效地组织和处理大量数据。排序算法的主要目标是将一组无序的数据元素按照特定的标准(通常是升序或降序)排列成一个有序序列。本篇文章主要介绍...

    数据结构-归并排序

    数据结构-归并排序 PPT文档

    数据结构-各种排序算法.pptx

    数据结构-各种排序算法.pptx

    数据结构课程设计---排序算法比较

    数据结构课程设计,C语言,七大排序算法比较

    数据结构--内排序

    数据结构是基于C语言的,很有用,欢迎大家下载。

    北大信息院数据结构--张铭

    7. **排序与查找**:排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等)和查找算法(如顺序查找、二分查找、哈希查找)是数据结构的重要组成部分,它们对算法性能有显著影响。 8. **动态...

    数据结构思维导图-排序.pdf

    以上是数据结构中关于排序的一些基本知识,包括排序的稳定性、比较次数、内部排序和外部排序的定义,以及直接插入排序、折半插入排序、希尔排序和冒泡排序的原理和特点。这些排序算法各有优缺点,选择哪种排序算法取...

Global site tag (gtag.js) - Google Analytics