9小结

南山隐士 2022年07月31日 47 0

本章通过具体实例介绍了排序的基本概念,给出了针对记录序列排序的定义。讨论了插入排序、交换排序、选择排序、归并排序等的基本原理、实现步骤和相关算法,并给出了各种算法的时间复杂度。

主要知识点归纳如下:

1.对记录序列排序是指按记录的某个关键字排序,记录序列按主关键字排序结果是唯一的。

2.按某关键字对记录序列排序,若其中关键字相等的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的,否则是不稳定的。

3.插入排序的直接插入排序和折半插入排序时间复杂度为O(n2),直接插入排序是顺序查找插入位置,而折半插入排序是通过折半查找插入位置。它们都是稳定的排序。

4.交换排序的冒泡法排序,通过不断比较相邻元素和交换操作实现排序。n个元素排序需要进行n-1趟冒泡,第j趟冒泡要比较n-j次。冒泡法排需时间复杂度为O(n2),是稳定的排序。快速排序每进行一次排序,使分割元素排序到位,并把序列分成大于、小于分割元素的子序列。通过递归继续对子序列实行快速排序。快速排序时间复杂度为O(nlog2n),是不稳定的排序。

5.选择排序的直接选择排序是逐次从n个元素、n-1个元素,···,中查找最小元素所在的位置,然后把他们逐一排列到位。它的时间复杂度为O(n2), 是稳定排序。堆排序利用堆结构的性质进行排序。堆能与一棵具有特殊性质的完全二叉树对应。排序的关键是筛选和建堆,它的时间复杂度是O(nlog2n),是不稳定的排序。

6.归并排序的基础是两个有序序列的归并。基于它设计出一趟归并的算法,利用一趟归并算法对一个待排序的序列逐次施行(1,1)归并,(2,2)归并,(4,4)归并。最终完成排序,它的时间复杂度为O(nlog2n),是稳定的排序。

Last Updated: 2022/07/31 23:28:15
mysql 设置root远程登录 9.5 归并排序