浙江省网站建设,wordpress分页怎么写,厦门有没网站建设的公司,做新闻的网站怎样赚钱第七章 排序 一、排序 1.定义#xff1a;将无序的数排好序 #xff1b; 2.稳定性#xff1a; Kᵢ和Kⱼ中#xff0c;Kᵢ优先于Kⱼ那么在排序后的记录中仍然保持Kᵢ优先#xff1b; 3.评价标准#xff1a;执行时间和所需的辅助空间#xff0c;其次是算法的稳定性#xf…第七章 排序 一、排序 1.定义将无序的数排好序 2.稳定性 Kᵢ和Kⱼ中Kᵢ优先于Kⱼ那么在排序后的记录中仍然保持Kᵢ优先 3.评价标准执行时间和所需的辅助空间其次是算法的稳定性空间复杂度是O(1)代表其算法所需的辅助空间不依赖问题规模则该排序方法为就地排序否则就是非就地排序 4.排序的分类待排序的记录数不太多时为内部排序反之为外部排序 二、插入排序 1.定义按关键字大小插入到前面已经排好序的子序列中 2.直接插入排序稳定的排序
性能分析空间复杂度是O(1)最好的情况时间复杂度为O(n)最坏的时间复杂度为O(n²)
3.折半插入排序是一种稳定的排序算法有些类似折半查找时间复杂度为O(n²)但对于数据量比较小排序表折半插入排序往往能表现出较好的性能
4.希尔排序
特点分组后n值不断减小关键字较小的记录跳跃式前移增量序列取法无除1外的公因子最后一个增量值必须为1不稳定
三、交换排序 1.定义系统的交换反序的记录的偶对直到不再有这样的偶对为止 2.冒泡排序时间复杂度T(n)O(n²)空间复杂度S(n)O(1)
3.快速排序 两指针选中的指针不动与另一个指针比较若被比较的数小于选中的指针就往选中指针的方向移动也就是不做改变否则就交换 当两指针相遇时才完成第一次排序。
性能分析时间复杂度是T(n)O(nlog₂n)最坏情况是O(n²)栈最大深度为[log2n]1空间复杂度最坏是O(n)不稳定的算法
四、选择排序 1.基本思想每次从当前待排序的记录中选取关键字最小的记录表然后与待排序的记录序列中的第一个记录进行交换直到整个记录序列有序为止。
2.简单选择排序时间复杂度是T(n)O(n²)空间复杂度是S(n)O(1)是不稳定的
3.排序
定义基于完全二叉树分大根堆和小根堆结论排序过程中若采用的是小根堆排序后得到的是非递减序列若采用的是大根堆则排序后得到的是非递增序列堆的调整和筛选根结点必须小于左右子树否则要交换直到第一次全部交换完成输出对顶元素也就是最小那个然后将堆底元素送到堆顶再进行排序交换一直反复循环直到堆只剩一个元素为止性能分析时间复杂度是T(n)O(nlog₂n)空间复杂度是S(n)O(1)堆排序是不稳定的
五、归并与基数排序 1.归并排序时间复杂度为O(mn);
排序思想2-路归并排序两两归并排序使其有序性能分析时间复杂度无论最好还是最坏都是O(nlog₂n)空间复杂度是O(n)归并排序是稳定的
2.基数排序桶排序或数字排序按待排序记录的关键字的组成成分位进行排序 性能分析时间复杂度O(d(nr))空间复杂度为O(nr)其中d为关键字位数每位有r种取值排序的趟数是d基数排序是稳定的
六、各种排序的比较 1.记忆方法:时间复杂度:快些归队(快速 归并堆排序)O(nlog₂n) 空间复杂度:快速O(log₂n)归并0(n)基数0(nr) 其他都为0(1) 稳定性:快些选一堆(快速 希尔 选择 堆排序)是不稳定的
2.其他细节:经过一次排序能够保证一个关键字到达最终位置这样的排序是交换的两类(冒泡、快速)和选择的两种(简单选择 堆)
排序算法的关键字比较次数和原始序列无关–简单选择和折半插入排序算法的排序趟数和原始序列有关–交换类的序。
