第10章排序 排序的基本概念 主插入排序 要」选择排序 识交换排序归并排序 点基数排序 性能比较
第10章 排序 排序的基本概念 插入排序 选择排序 交换排序归并排序 基数排序 性能比较 主 要 知 识 点
101排序的基本概念 排序是对数据元素序列建立某种有序排列的过程是把一个数据 元素序列整理成按关键字递增(或递减)排列的过程。 关键字是要排序的数据元素集合中的一个城,排序是以关键字 为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同,是能够 惟一区分各个不同数据元素的关键字;不满足主关键字定义的关 键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序 外部排序是因数量太大,把数据元素分批导入内存,排好序后 再分批导出到磁盘和磁带外存介质上的排序方法
10.1 排序的基本概念 排序是对数据元素序列建立某种有序排列的过程,是把一个数据 元素序列整理成按关键字递增（或递减）排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字 为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同，是能够 惟一区分各个不同数据元素的关键字;不满足主关键字定义的关 键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序。 外部排序是因数量太大，把数据元素分批导入内存，排好序后 再分批导出到磁盘和磁带外存介质上的排序方法
比较排序算法优劣的标准: (1)时间复杂度它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度:算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关鍵字值相等,但排序后A、B 的先后次序保持不变,则称这种排序算法是稳定的
比较排序算法优劣的标准: (1)时间复杂度:它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度 :算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B 的 先后次序保持不变，则称这种排序算法是稳定的
10.2插入排序 插入排序的基本思想是:每步将一个待排序的数据元素,按 其关键码大小,插入到前面已经排好序的一组数据元素的适当 位置上,直到数据元素全部插入为止。 常用的插入排序有直接插入排序和希尔排序两种 1直接插入排序 其基本思想是: 顺序地把待排序的数据元素按其关键字值的大小插入到 已排序数据元素子集合的适当位置
10.2插入排序 插入排序的基本思想是：每步将一个待排序的数据元素，按 其关键码大小，插入到前面已经排好序的一组数据元素的适当 位置上，直到数据元素全部插入为止。 1.直接插入排序 常用的插入排序有直接插入排序和希尔排序两种。 其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到 已排序数据元素子集合的适当位置
算法如下: void InsertSort DataType all, int n) /用直接插入法对a0-a{m-排序 int l, Data Type temp; for(i=0;i<n-1;i++) t temp=a i+1 J=1 while(j>-1 & temp key aljkey t aj+1=aljl a[j+1]=temp;
算法如下： void InsertSort (DataType a[], int n) //用直接插入法对a[0]--a[n-1]排序 { int i, j; DataType temp; for(i=0; i<n-1;i++) { temp = a[i+1]; j = i; while(j > -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } }