数据结构-从概念到C++实现（第4版）课件 7-1排序概述

7-1排序概述v第七章排序技术排序的定义女李爽0005女齐梅0004女刘楠0003男张亮0002男王刚0001性别姓名职工号5635573548年龄1982.92003.71979.92003.71990.4工作时间排序是对线性结构的一种操作排序：给定一组记录的集合{r1,r2,…,rn}，其相应的关键码分别为{k1,k2,…,kn}，将这些记录排列为{rs1,rs2,…,rsn}的序列，使得相应的关键码满足ks1≤ks2≤…≤ksn（或ks1≥ks2≥…≥ksn）。数据元素、结点、顶点升序（非降序）降序（非升序）排序的数据模型是什么？排序码：排序的依据，简单起见，也称关键码。（1）进行升序排序不失一般性，做如下约定：（3）采用顺序存储（即数组）（2）记录只有排序码一个数据项排序的定义女李爽0005女齐梅0004女刘楠0003男张亮0002男王刚0001性别姓名职工号5635573548年龄1982.92003.71979.92003.71990.4工作时间排序是对线性结构的一种操作排序的数据模型是什么？排序码：排序的依据，简单起见，也称关键码。正序、逆序正序：待排序序列中的记录已按关键码排好序。1234512345逆序（反序）：待排序序列中记录的顺序与排好序的顺序相反。5432112345深刻理解趟的含义能够更好地掌握排序方法的思想和过程趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。算法的稳定性排序算法的稳定性：假定在待排序的记录序列中存在多个具有相同关键码的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法稳定，否则称为不稳定。学号姓名高数英语语文0001王军85880002李明64920003汤晓影8586………687278……学号姓名高数英语语文0001王军64880002李明85920003汤晓影8586………687278……排序算法的稳定性只是算法的一种属性，且由具体算法决定排序的分类根据排序过程中所有记录是否全部放在内存中，排序方法分为：（1）内排序：在排序的整个过程中，待排序的所有记录全部放在内存中（2）外排序：待排序的记录个数较多，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果根据排序方法是否建立在关键码比较的基础上，排序方法分为：（1）基于比较：主要通过关键码之间的比较和记录的移动实现（2）不基于比较：根据待排序数据的特点所采取的其他方法①插入排序；②交换排序；③选择排序；④归并排序直接插入排序希尔排序起泡排序快速排序简单选择排序堆排序二路归并递归算法二路归并非递归算法排序算法的性能如何衡量排序算法的性能呢？（1）时间性能：排序算法在各种情况（最好、最坏、平均）下的时间复杂度。例如，基于比较的内排序在排序过程中的基本操作：①比较：关键码之间的比较；②移动：记录从一个位置移动到另一个位置。（2）空间性能：排序过程中占用的辅助存储空间。辅助存储空间是除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。排序类的定义classSort{public:

Sort(intr[],intn);

~Sort();

voidInsertSort();

voidShellSort();

voidBubbleSort();

voidQuickSort(intfirst,intlast);

voidSelectSort();

voidHeapSort();

voidMergeSortRecursion();voidMergeSort(intfirst,intlast);

voidPrint();private:

intPartition(intfirst,intlast);

voidSift(intk,intlast);

voidMerge(intfirst1,intlast1,intlast2);

voidMergePass(inth);

int*data;

intlength;};Sort::Sort(intr[],intn){

data=newint[n];

for(inti=0;i<n;i++)

data[i]=r[i];

length=n;}Sort::~Sort(){

delete[]data;}voidSort::Print(){

for(inti=0;i<length;i++)

{

cout<<data[i]<<"\t";

}

cout<<endl;}排序类的定义classSort{public:

Sort(intr[],intn);

~Sort();

voidInsertSort();

voidShellSort();

voidBubbleSort();

voidQuickSort(intfirst,intlast);

voidSelectSort();

voidHeapSort();

voidMergeSortRecursion();voidMergeSort(intfirst,intlast);

voidPrint();private:

intPartition(intfirst,intlast);

voidSift(intk,intlast);

voidMerge(intfirst1,intlast1,intlast2);

voidMergePass(inth);