排序算法(转)


1、排序概念

排序又称分类,是数据处理中经常用到的一种运算。

简单地说,排序就是将一个记录(元素)的序列排列成一个有序序列的过程。每个记录由两部分组成:关键字、其他信息。为了实现排序,记录的关键字必须是可以进行比较大小的类型。

给定一个含有n个记录的序列(R0,R1,R2,…,Rn-1),K是 R的关键字。所谓排序,就是要寻找(0,1,2,…,n-1)一种排列(p(0),p(1),p(2),…,p(n-1)),使得记录序列按照

(Kp(0),Kp(1),Kp(2),…,Kp(n-1))非递减(或非递增)排列。此时原序列将排列为:(Rp(0),Rp(1),Rp(2),…,Rp(n-1))。

2、排序算法分类

(1)根据排序时所占的存储器的不同,可以将排序分为内排序(整个排序过程完全在内存中进行)和外排序(排序需要借助外部存储设备才能完成)。

(2)根据排序时元素的操作可以分为:插入类排序、交换类排序、选择类排序、归并排序、分配类排序。

3、排序算法的稳定性

若在原序列中有Ri领先于Rj(即i<j,Ri排在Rj之前),其关键字分别为:Ki、Kj且Ki=Kj。经过排序之后,在得到的有序序列中,若仍然有Ri领先于Rj,则所用的排序算法是稳定的,反之,算法是不稳定的。

证明一种排序算法是稳定的,需要从算法的每一个步骤去分析证明,证明一种排序算法是不稳定的,只需要给出一个反例即可。

4、排序算法常用的两种操作

(1)比较关键字大小。

(2)移动待排序序列中元素的位置(根据待排序序列元素的存储方式不同,可以避免对元素的移动)。

5、待排序序列存储方式

(1)顺序存储,待排序元素存放在一段地址连续的存储单元中,排序过程中需要进行移动元素的操作。

(2)链式存储,待排序元素之间的相邻关系是通过指针来实现的,在排序过程中只需要修改指针,而不要移动待排序序列中的元素。

(3)顺序存储与地址相结合,待排序序列的元素存放在一段地址连续的存储单元中,同时另设一个指示各个元素的位置的地址向量,在排序过程中不移动元素本身,而是修改地址向量中的地址,排序结束后,再根据地址向量中的值来调整待排序序列中元素的位置。这种排序方式通常也称为地址排序

6、序列元素结构体

在这里主要讨论顺序存储方式中各排序算法的C语言实现。定义如下结构体:

typedefine int KeyType;

typrdefine struct {

KeyType     key;

OtherType   other_data;

}ElementType;

为了方便简洁,序列元素的关键字数据类型设为整型(int)。


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
01-18 16:22
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议