模板网站建设哪家专业,网上全网推广,网站建设总结和体会,太原网站建设招聘一、排序的基本概念
1-1、稳定性
稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后#xff0c;次序不变#xff0c;则是稳定的。 1-2、归位
每一趟排序能确定一个元素的最终位置。 1-3、内部排序
排序记录全部存放在内存中进行排序的过程。 1-4、外部…一、排序的基本概念
1-1、稳定性
稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后次序不变则是稳定的。 1-2、归位
每一趟排序能确定一个元素的最终位置。 1-3、内部排序
排序记录全部存放在内存中进行排序的过程。 1-4、外部排序
待排序记录的数量很大以至于内存不能容纳全部记录在排序过程中尚需对外存进行访问的排序过程。 1-5、排序小结要背 比较最好时间复杂度会发现当待排序的序列基本有序的话适合采用 直接插入排序希尔排序冒泡排序 二、直接插入排序 稳定的 不归位 三、希尔排序
直接插入排序的改进。 基本思想现将整个待排记录序列分割成若干子序列然后分别进行直接插入排序待整个序列中的记录基本有序的时候再对全体记录进行一次直接插入排序。 示例 不稳定 不归位 四、真题1
真题1 真题2 真题3 真题4 五、简单选择排序
算法思想从待排数组中找到最小值再将最小值与已排好序的数组后一位进行交换。 归位 不稳定 六、堆排序简单了解
示例 此时根元素80是最大的元素将根元素80和队列最后一个元素10交换并将80脱离当前序列归位此时新的二叉树不满足大顶堆的规则则继续调整。 每次调整完得到的根节点都是当前序列的最大元素 归位 不稳定 七、真题2
真题1 真题2 八、冒泡排序
基本思想相邻两个元素俩俩交换。 稳定 归位 九、快速排序
快速排序首先选择了一个基准值然后分别选择两个指针在数组中一个找大一个找小然后进行交换。
通过一趟排序将待排序的记录以基准值为分界分为独立的两个部分称为前半区和后半区前半区均小于基准值后半区均大于基准值。
然后再分别对这两个部分在进行快速排序从而使得整个序列有序。 分治分而治之。 归位 不稳定 纠错空间时间复杂度是O(log2n) 十、真题2
真题1 真题2 真题3 真题4 十一、归并排序 示例 设计方法分治法 不归并 稳定 11-1、真题
真题1 真题2 真题3 真题4 真题5 真题6 十二、排序小结
12-1、简单排序
1、直接插入排序稳定
2、冒泡排序稳定
3、简单选择排序不稳定 时间复杂度都是O(n^2) 空间复杂度O(1) 12-2、希尔排序不稳定 时间复杂度O(n^1.3) 空间复杂度O(1) 12-3、快速排序不稳定
分治思想 时间复杂度O(nlog2n)——性能最好 空间时间复杂度O(log2n) 但是当待排序列基本有序的时候是最坏的情况时间复杂度退化为O(n^2) 12-4、堆排序不稳定 时间复杂度O(nlog2n) 空间时间复杂度O(1) 12-5、归并排序稳定
俩俩归并n/2向上取整
整个归并排序需要进行log2n趟向上取整 空间复杂度O(n) 时间复杂度O(nlogn) 12-6、小结-稳定的排序
直接插入排序冒泡排序归并排序 12-7、真题
真题1 真题2 真题3 直接插入排序局部有序 冒泡每一趟排序都将最大的泡泡在最后的位置。
