厦门网站建设云端网络,做果蔬行业的网站,仙桃做网站的公司有哪些,安徽建设工程信息网查询平台蔡庆树转上一节#xff1a;
http://t.csdnimg.cn/fr4I4http://t.csdnimg.cn/fr4I4
6.3#xff1a;排序算法
考点1#xff1a;排序算法的基本概念
1.排序的概念
稳定与不稳定排序
2.排序方法分类
插入类排序直接插入排序希尔排序交换类排序冒泡排序快速排序选择类排序简单选…转上一节
http://t.csdnimg.cn/fr4I4http://t.csdnimg.cn/fr4I4
6.3排序算法
考点1排序算法的基本概念
1.排序的概念
稳定与不稳定排序
2.排序方法分类
插入类排序直接插入排序希尔排序交换类排序冒泡排序快速排序选择类排序简单选择排序堆排序归并排序基数排序 考点2插入类排序
1直接插入排序
直接插入排序:即当插入第i个记录时均已排好序,因此将第i个记录依次与
进行比较找到合适的位置插入。它简单明了但速度很慢。
直接插入排序是一种稳定的排序方法 时间复杂度为O()。在排序过程中仅需要一个元素的辅助
空间 空间复杂度为0(1)
适用于基本有序的情况此时时间复杂度近乎线性即O(n)。 2希尔(Shell) 排序
希尔(Shell) 排序先取一个小于n的整数d1作为第一个增量 把文件的全部记录分成个组。所
有距离为的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后取第二个增量
d2d1重复 上述的分组和排序直至所取的增量,即所有
记录放在同一组中进行直接插入排序为止。该访法实质上是一种分组插入方法。
希尔排序是一种不稳定的排序方法据统计分析其时间复杂度约为O()。在排序过程中仅需要
一个元素的辅助空间用于数组元素的交互空间复杂度为O(1)。 考点3选择类排序
1直接选择排序
直接选择排序的过程是首先在所有记录中选出排序码最小的记录把它与第1个记录交换然后
在其余的记录内选出排序码最小的记录与第2个记录交换……依此类推直到所有记录排完为止。
直接选择排序是一种不稳定的排序方法其时间复杂度约为O()。在排序过程中仅需要一个元素
的辅助空间用于数组元素的交互空间复杂度为O(1)。 2堆的概念
设有n个元素的序列{}, 当且仅当满足下述关系之一时,称之为堆。
(1) 且;父结点小于等于左右两个子结点。第一个元素最小。
(2) 且;父结点大于等于左右两个子结点。第一个元素最大。
其中(1)称为小顶堆(2) 称为大顶堆。 3.堆排序
堆排序的基本思想为先将序列建立堆然后输出堆顶元素再将剩下的序列建立堆然后再输出
堆顶元素依此类推直到所有元素均输出为止此时元素输出的序列就是一个有 序序列。
对于大量的记录来说堆排序是很有效的。
堆排序的算法步骤如下(以大顶堆为例) :
(1)初始时将顺序表R[1...n]中元素建立为一个大顶堆堆顶位于R[1],待序区为R[1...n]。
(2) 循环执行步骤3~步骤4共n-1次。
(3)假设为第i次运行则待序区为R[1...n-i1], 将堆顶元素R[1]与待序区元素R[n-i1]交换此时顶
点元素被输出新的待序区为R[1..n-1]。
(4)待序区对应的堆已经被破坏将之重新调整为大顶堆。
将顺序表R{30, 6010, 50, 4516, 15, 80, 40, 20}进行堆排序。
[初建堆] [取走堆顶元素60重建堆]
堆排序的时间复杂度为:O(nlog2n) 为什么? 堆排序的空间复杂度为O(1)。 考点4交换类排序
1冒泡排序
冒泡排序的基本思想是通过相邻元素之间的比较和交换将排序码较小的元素逐渐从底部移向顶
部。整个排序的过程元素就像水底下的气泡一样逐渐向上冒因此称为冒泡算法。
冒泡排序是一种稳定的排序方法其时间复杂度约为O()。在排序过程中仅需要一个元素的辅助
空间用于数组元素的交互空间复杂度为O(1)。 2快速排序
快速排序采用的是分治法其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子
问题通过递归地解决这些子问题然后再将这些子问题的解组合成原问题的解。
在O()时间量级上,平均性能最好。
快速排序通常包括两个步骤:
第一步在待排序的n个记录中任取一个记录 以该记录的排序码为准将所有记录都分成两组
第1组都小于该数第2组都大于该数,如图所示。
第二步采用相同的方法对左、右两组分别进行排序直到所有记录都排到相应的位置为止。 快速排序的基准元素一般是第一个元素 也可以设置中位数。
快速排序是种不稳定的排序方法平均和最优情况下时间复杂度约为0()。
快速排序的最差情况--------基 本有序
以第一个元素为基准元素此时时间复杂度为O()。
以中位数为基准元素此时时间复杂度为O()。
辅助空间
(1)空间复杂度默认为O(1)。
(2)需要辅助空间存储左侧数组和右侧数组时空间复杂度为O(n)。
(3)需要记录所有基准元时空间复杂度为O()。 考点5归并排序
归并也称为合并是将两个或两个以上的有序子表合并成一个新的有序表。 若将两个有序表台并
成一个有序表则称为二路合并。合并的过程是比较A[i]和A[j]的排序码大小若A[i]的排序码小
于等于A[j]的排序码,则将第一个有序表中的元素A[i]复制到R[k]中i和k分别加1如此循环下去
直到其中一个有序表比较和复制完然后再将另一个有序表的剩余元素复制到R中。
归并排序是一种稳定的排序方法 其时间复杂度约为O()。在排序过程中仅需要一个元素
的辅助空间用于数组元素的交互空间复杂度为O(n)。 考点6基数排序
基数排序是一种借助多关键字的排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关健
字比较的排序方法它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关
键字的类型来决定的例如关键字是十进制数则按个位、十位来分解。
基数排序是一种稳定的排序方法其时间复杂度约为O(d(nrd))。在排序过程中仅需要一个元素的
辅助空间用于数组元素的交互空间复杂度为O(rd)。 考点7排序算法对比 在选取排序方法时需要考虑的因素有待排序的记录个数n、记录本身的大小、关键字的分布情况、
对排序稳定性的要求、语言工具的条件和辅助空间的大小。依据这些因素可以得到以下几点结
论:
若待排序列的记录数目n较小可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多因而当记录本身信息量大时用简单选择排序方法较好。若待排记录按关键字基本有序宜采用直接插入排序或冒泡排序。当n很大且关键字位数较少时,采用基数排序较好。若n很大则应采用时间复杂度为O()的排序方法例如快速排序、堆排序或归并排序
(1)快速排序目前被认为是内部排序中最好的方法当待排序的关键字为随机分布时,快速排序的平
均运行时间最短。
(2)堆排序只需要一个辅助空间 并且不会出现在快速排序中可能出现的最快情况。
(3)快速排序和堆排序都是不稳定的排序方法若要求排序稳定可选择归并排序。 6.4算法策略
考点1算法策略概述
1分治法
特征把一个问题拆分成多个小规模的相同子问题一般可用递归解决。
经典问题斐波那契数列、归并排序、快速排序、矩阵乘法、二 分搜索、大整数乘法、汉诺塔。
2贪心法(一 般用于求满意解)
特征局部最优但整体不见得最优。每步有明确的、既定的策略。
经典问题背包问题(如装箱)、多机调度、 找零钱问题、最小生成树问题(普里姆算法、克鲁斯卡
尔算法)。
3.动态规划法(用于求最优解)-------. 最优子结构”和递归式
特征划分子问题使用数组存储子问题结果利用查询子问题结果构造最终问题结果。(一 般自
顶向下时间复杂度为O()自底向上时间复杂度为O()效率更高)
经典问题斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列。
4回溯法
特征系统的搜索一个问题的所有 解或任一解。
经典问题: N皇后问题、迷言、背包问题。
(回溯法对解空间做深度优先探索分支限界法对解空间做广度优先探索) 考点2分治法
对于一个规模为n的问题若该问题可以容易地解决比如说规模n较小则直接解决否则将其分
解为k个规模较小的子问题这些子问题互相独立且与原问题形式相同递归地解这些子问题然
后将各子问题的解合并得到原问题的解。
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的
分解
解决
合并
1分治法递归技术
递归就是在运行的过程中调用自己。 2分治法(二分查找)
function Binary_Search(L,a,b,x){if(ab) return(-1);else{m(ab)/2;if([xL[m])return(m);else if(xL[m])retun(Binary_Search(L,m1,b,x));elseretun(Binary_Search(L,a.m-1,x)),}
}
考点3贪心算法
总是做出在当前来说是最好的选择而并不从整体上加以考虑,它所做的每步选择只是当前步骤的
局部最优选择,但从整体来说不一定是最优的选择。由于不必为了寻找最优解而穷尽所有可能解
因此其耗费时间少一般可以快速得到满意的解但可能得不到最优解。【贪心法解决部分背包问
题可得最优解】 考点4动态规划法
在求解问题中对于每步决策 列出各种可能的局部解再依据某种判定条件,舍弃那些肯定不能
得到最优解的局部解每一步都经过筛选以每一步都是最优解来保证全局是最优解。 (问题中如
果出现“最优子结构”这类描述并且结果用递归式表示一般为动态规划法) 考点5回溯法
回溯法是一种选优搜索法按选优条件向前搜索以达到目标。但当搜索到某一步时发现原先选
择并不优或达不到目标就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。
