数据结构上机基本习题.ppt

该【数据结构上机基本习题 】是由【相惜】上传分享，文档一共【44】页，该文档可以免费在线阅读，需要了解更多关于【数据结构上机基本习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。单元实验二排序算法精选课件排序的分类内部排序外部排序插入排序〔直插排序、二分插入排序、希尔排序〕交换排序〔冒泡排序、快速排序〕选择排序〔简单项选择择排序、树型排序、堆排序〕归并排序〔二路归并排序、多路归并排序〕分配排序〔多关键字排序、基数排序〕多路平衡归并排序置换-选择排序最正确归并树排序精选课件直接插入排序直接插入排序(StraightInsertionSorting)的根本思想是:n个待排序的元素由一个有序表和一个无序表组成,开始时有序表中只包含一个元素。排序过程中,每次从无序表中取出第一个元素,将其插入到有序表中的适当位置,使有序表的长度不断加长,完成排序过程。有序序列R[1..i-1]R[i]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1..n]精选课件冒泡排序冒泡排序(BubbleSorting)的根本思想是:将相邻位置的关键字进行比较,假设为逆序那么交换之。无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录,将关键字最大的记录交换到n-i+1的位置上第i趟起泡排序假设在一趟排序过程中没有进行过交换记录的操作,那么整个排序过程终止。精选课件简单项选择择排序简单项选择择排序的根本思想是:第一趟在n个记录中选取最小记录作为有序序列的第一个记录,第二趟在n-1个记录中选取最小记录作为有序序列的第二个记录,第i趟在n-i+1个记录中选取最小的记录作为有序序列多中的第i个记录。有序序列R[1..i-1]无序序列R[i..n]第i趟简单项选择择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]〔或更多〕整数〔或浮点数〕,保存在文件〔〕中,然后将文件中的所有整数〔或浮点数〕读入一个数组A。〔1〕用冒泡法对数组A排序;〔2〕用简单项选择择排序方法对数组A排序;〔3〕用直接插入排序法对数组A排序;将上述排序算法分别用函数实现,输出每种排序过程中元素的比较次数、交换〔或移动〕次数,以及排序过程所消耗的时间〔以s或ms为单位〕;〔或更多〕整数读入数组A,用快速排序算法对数组A中的元素排序,输出排序结果、排序过程中元素的比较和交换〔移动〕次数、排序算法消耗的时间;,,读取其中的所有学生信息:〔1〕按学号排序输出学生信息;〔2〕按姓名排序输出学生信息;〔3〕按三门课程的平均分从高到低排序输出学生信息〔除了学生根本信息外,还要输出每个学生的平均成绩〕,最后再加一行输出信息:每门课程的平均成绩。精选课件快速排序快速排序(QuickSorting)是迄今为止所有内排序算法中速度最快的一种。其根本思想是:取待排序序列中的某个元素作为基准〔也成为枢轴元素,一般取第一个元素〕,通过一趟排序,将待排序列划分为左右两个子序列,左子序列元素的关键字均小于或等于基准元素的关键字,右子序列的关键字那么大于或等于基准元素的关键字,然后分别对两个子序列继续进行排序,直至整个序列有序。无序的记录序列无序的左子序列无序的右子序列枢轴一次划分分别进行快速排序精选课件386597132749551234567849049pivotij快速排序中的一趟划分386597132749551234567804949pivotija[j]与pivot比较,a[j]小那么a[j]→a[i]精选课件386597132749551234567804949pivotij快速排序中的一趟划分i386597132749551234567804949pivotja[i]与pivot比较,a[i]大那么a[i]→a[j];否那么i增1精选课件