软件技术基础第03章(2)排序

《软件技术基础第03章(2)排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、软件技术基础第03章(2)排序本文由真知浊见贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。教学目标了解有关排序的–基本概念基本概念–排序的典型算法排序的典型算法–二叉排序树二叉排序树第1页排序(Sorting)排序(Sorting)将一个无序序列整理成按值非递减（或非递增）将一个无序序列整理成按值非递减（或非递增）顺序排列的有序序列。顺序排列的有序序列。排序可以在不同的存储结构上实现。排序可以在不同的存储结构上实现。–基本排序是在顺序存储的线性表中实现的；基本排序是在顺序存储的线性表中实现的；基

2、本排序是在顺序存储的线性表中实现的–二叉排序树利用二叉树的链式存储结构实现无序表二叉排序树利用二叉树的链式存储结构实现无序表的有序化。的有序化。三种基本排序方法：三种基本排序方法：交换排序?插入排序?选择排序（如（如（如冒泡排序和快速排序）；冒泡排序和快速排序）；简单插入排序和希尔排序）；简单插入排序和希尔排序）；简单选择排序和堆排序）；简单选择排序和堆排序）；第2页排序算法的数据结构顺序存储结构（C语言描述）：顺序存储结构（语言描述）：#defineNnstructrecord{intkey；/*关键字项*/otherterm；int

3、otherterm；/*其它项*/}；RECORD；typedefstructrecordRECORD；file[N+1]；RECORDfile[N+1]；第3页二、典型排序算法冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序第4页交换排序交换排序的基本思想：交换排序的基本思想：两两比较待排序记录的关键值，若发生逆两两比较待排序记录的关键值，序则交换之，直至所有记录都排好序。序则交换之，直至所有记录都排好序。交换排序的两种形式冒泡排序快速排序第5页冒泡排序冒泡排序（sort）冒泡排序（Bubblesort）是基于交换排序的一种算法

4、。它是依次两两比较待排序元素；算法。它是依次两两比较待排序元素；若为逆递增或递减）则进行交换，序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡冒泡”。从左至右比较一遍称为一趟冒泡。每趟冒泡都将待排序列中的最大关键字交换到最后（都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。最前）位置。直到全部元素有序为止。∩∩∩…∩ana1a2a3…an-1an最大值第6页冒泡排序算法举例设有数列{65,97,76,13,27,49,设有数列{65,97,76,13,27,49,58}97}65，76，1

5、3，27，49，58}第1趟{65，76，13，27，49，58}，{97}第2趟第3趟第4趟第5趟第6趟{65，13，27，49，58}，{76，97}65，13，27，49，58}76，97}{13，27，49，58}，{65，76，97}13，27，49，58}65，76，97}{13，27，49}，{58，65，76，97}13，27，49}58，65，76，97}{13，27}，{49，58，65，76，97}13，27}49，58，65，76，97}比较次数6543227，49，58，65，76，97}1{13}，{27，4

6、9，58，65，76，97}13}总计：总计：21次第7页冒泡排序算法bubble(int*item,intcount)a,b，{inta,b，t;for(a=1aitem[b])/*若逆序若逆序,if(item[b-1]>item[b])/*若逆序,则交换*/t=item[b{t=item[b-1];/*它们的位

7、置*/item[b-]=item[b];item[b-1]=item[b];item[b]=t;item[b]=t;}}第8页冒泡排序算法主程序#defineN7#include"stdio.h"main(){ints[]={65,97,76,13,27,49,58},i;bubble(s,N);/*调用选择排序函数*/is:printf("Thesortedstringis:");for(k=0;k

8、出，从第4趟冒泡起，序列已有结果是空跑了3若两次冒泡处理过程中，序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡