1 / 10
文档名称:

数据结构排序算法.docx

格式:docx   页数:10页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构排序算法.docx

上传人:799474576 2015/5/29 文件大小:0 KB

下载得到文件列表

数据结构排序算法.docx

文档介绍

文档介绍:常见排序算法总结
1. 基本概念
排序:是将一组数据元素按某种特定要求(升或降序)排列成有规律序列的过程。
排序可以分为内部排序和外部排序两种:
1). 若整个排序过程不需要访问外存便能完成,则称此类排序为内部排序。
2). 若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,需要借助外存来完成,则称此类排序为外部排序。//不涉及内外存交换
就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),则称为就地排序。
稳定性:假设在待排序的元素中,存在两个或两个以上的元素具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。
2. 常见内部排序
交换排序
交换排序的基本思想是两两比较待排序记录的关键字,若发生与排序要求相逆,则交换之,反复进行,直到数据有序。
交换排序的主要方法有:冒泡排序和快速排序。
1). 冒泡排序
a. 算法思想
已知一组无序数据元素P[n],需将按其关键字升序排列。
第一趟对n个元素冒泡得到一个关键字最大的元素P[n-1],第二趟冒泡对n-1个元素得到一个关键字最大的元素P[n-2],依次类推,直到数据有序。
b. 算法实现
void buble(int arr[], int n)
{
bool flag;//用于判断是否发生了交换
int i;
int temp;//临时变量
//反复多轮,从小到大排序。
do {
//一轮排序
flag = false;
//反复比较所有相邻的元素,循环比较n-1次。
for(i = 1; i < n; i++) {
//如果顺序不当,就交换他们。
if(arr[i] < arr[i - 1]) {
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
//记录本轮已发生交换
flag = true;
}
}
n--;
}while(flag);//知道本轮没有发生交换,循环退出。
}
注:
冒泡排序算法是稳定的,时间复杂度是O(n^2)。
冒泡排序算法适合只有少量乱序的数据。
2). 快速排序
a. 算法思想
已知一组无序数据元素P[n],需将按其关键字升序排列。
首先任取一个元素P[x](通常选取首元素)作为基准,多次比较P[x]与其它元素并交换。
直到当P[x]可以排在序列的第k位,并且使P[0]~P[k]中的每一个元素小于P[x],P[k+1]~P[n-1]中的每一个元素不小于P[x]时,交换P[x]和P[k]。
再分别对P[0]~P[k-1]和P[k+1]~P[n-1]两组数据元素重复上述过程,直到数据有序。
b. 算法实现
//交换函数
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//快速排序
void qsort(int arr[], int n)
{
int temp;
int *L, *R;

最近更新

摄影棚装修合同书3篇 51页

1981年国内研究生入学试题选载(Ⅱ) 2页

1515—75″布机投梭力配置的初探 2页

10吨工频炉熔炼潜力与经济性的探讨 2页

东风日产PPAP表格 22页

质量审核中不合格项的判定 19页

高速铁路CPⅢ测量标志在建筑变形监测中的应用.. 3页

社会资本在社会创新中的作用-全面剖析 26页

非物质文化遗产的传承开发研究——以丝绸之路.. 3页

闭式循环水系统在空气压缩机的应用 3页

铁路固定资产管理的探讨与探究 3页

详解营销渠道管理与渠道设计 68页

7个方面直观幼儿园的幼小衔接是否成熟可行 2页

透水层水中承台沉井围堰施工技术 4页

大数据应用中的内存优化方法-全面剖析 32页

路桥工程施工中的软土地基处理技术探究 3页

超分子聚乙醇类“固-固相变材料”的研究 3页

财政专项资金预算绩效管理初探 3页

试论作者队伍建设的重要性及途径、方法 3页

记者在新闻采访中的作用及沟通技巧的有效应用.. 3页

西门子技术在棒材轧机改造中的应用 3页

行政事业单位固定资产内部控制问题研究 3页

蔗渣纤维素分离纯化预处理工艺条件优化 3页

苏浙沪三省(市)二氧化碳排放现状与影响因素分.. 3页

2025年度个人住房装修贷款协议 7页

2025年商砼站绿色建材应用合作合同 10页

膜类材料标签产品加工溢胶原因分析 3页

聚丙烯纤维机制砂水泥砂浆早期抗裂性能试验研.. 3页

罗定电厂#2汽轮机#1轴瓦温度高的原因分析 3页

综采工作面液压支架回撤技术应用 3页