第5节 算法的数值稳定性

排序算法稳定性实现技巧概述排序算法是计算机科学中常用的算法之一，用于将一组元素按照特定的规则进行排列。

在排序算法中，稳定性是一个重要的概念，它指的是排序后相等元素之间的相对位置是否保持不变。

本文将概述排序算法的稳定性实现技巧。

一、稳定性的意义及应用稳定性在排序算法中非常关键，特别是在多关键字排序或对象排序的场景中。

对于多关键字排序，如果排序算法是稳定的，那么第一关键字相同时，第二关键字不会打乱原本的顺序，这对于保持数据的有效性非常重要。

在对象排序中，保持原始顺序能够确保对象之间的关联性，在某些应用中具有重要意义。

二、常见的排序算法及其稳定性1. 冒泡排序（Bubble Sort）冒泡排序是一种简单直观的排序算法，通过相邻元素的比较和交换来达到排序的目的。

冒泡排序是一种稳定的排序算法，因为对于相等的元素，它们不会改变原始的相对位置。

2. 插入排序（Insertion Sort）插入排序将元素逐个插入到已排序序列中的合适位置。

插入排序也是一种稳定的排序算法，因为在插入过程中，不会改变相等元素的相对顺序。

3. 归并排序（Merge Sort）归并排序采用分治策略，将待排序序列不断拆分为更小的子序列，然后再将子序列排序合并。

归并排序是一种稳定的排序算法，因为在合并子序列的过程中，相等元素的相对顺序不会改变。

4. 堆排序（Heap Sort）堆排序利用堆数据结构来实现排序操作。

堆排序是一种不稳定的排序算法，因为堆的构建过程可能会改变相等元素的相对位置。

5. 快速排序（Quick Sort）快速排序通过选取一个基准元素，将序列分割成两部分，然后对两部分分别进行排序。

快速排序是一种不稳定的排序算法，因为在分割过程中，可能会改变相等元素的相对顺序。

三、实现稳定性的技巧1. 稳定的基于比较的排序算法在基于比较的排序算法中，为了实现稳定性，当比较两个元素相等时，不进行交换操作，而是保持它们在原始序列中的相对顺序。

2. 索引排序索引排序是一种利用辅助数组或链表来记录元素位置的方法。

第1章复习与思考题习题0，依据定义|X*X|/X*|X*-X|=X***X X：按定义求解E(lnX)=|lnX-LnX*|=ln(X/X*)=ln(1-)X|lnX ln*|/lnX*ln(1)/lnX*ln(1)/lnX*按泰勒展开求解，2(x*)=(x*)(x x*)"()(x x*)f f f1(lnX*)|lnX lnX*|lnX*(X X*)**r(lnX*)|lnX lnX*|/ln */ln *X X X X问题是解法1错了吗？ 很小时，ln(1-)=，求n X 的相对误差*0.02*X X ： 按照定义：{(10.02)X*}*(1.02)n n X (X )(X X*)/X* 1.021(10.02)1n n n n n多项式展开，有100.02n n i i：按照泰勒展开11(X X*)*(X X*)nX*(0.02X*)0.02X*)(XX*)/X*0.02*/*0.02n n n n n nn nn nnX nX X n问题是解法1错了吗？10.02n n i i 收敛于（0.02/(1-0.02)= 0.002004008016032064128256释？应该没有错，按照泰勒展开，相当于将误差限放大了。

3、下列各数都是经过四舍五入得到的近似数，即误差限不超过最后一位的半个单位，试指出它们是几位有效数字* 1.1021x ，0.031x ，385.6，56.430，7 1.0。

解：有4位有效数字；X2有1位有效数字；X3有3位有效数字；X4有1位有效数字**24x x ，*1x x 其中***123x x x ，，，公式（2.3）：1(A*)|()*|(X )n k k kfX 解：******124124()()()()0.510x x x x x x ************1232311321234313()()()()0.031385.60.510 1.1021385.60.510 1.10210.0310.510(0.59768212.48488 1.708255)100.214790815x x x x x x x x x x x x******2*2442244323335(/)1/()/()()1/56.4300.5100.031/(56.430)0.510(10.031/56.430)/56.4300.510=(0.99945064681906787169945064681907)0.5/56.430100.885610x x x x x x x5、计算求体积要使相对误差限为1%，问度量半径R 所允许的相对误差是多少？解：球的体积公式3V R23(V)3R (R)/R 3(R)/R 0.01r有(R)0.01/3R (R)(R)/1/300r R6、设Y0=28，按递推公式11783100n nY Y ，1,2,3.....n 计算到Y100，若取27.982（解：n n n (Y )(Y Y )，所以(Y )0n 。

数值计算方法思考题数值计算方法思考题第一章预篇1．什么是数值分析？它与数学科学和计算机的关系如何？ 2．何谓算法？如何判断数值算法的优劣？3．列出科学计算中误差的三个来源，并说出截断误差与舍入误差的区别。

4．什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？5．什么是算法的稳定性？如何判断算法稳定？为什么不稳定算法不能使用？ 6．判断如下命题是否正确：一个问题的病态性如何，与求解它的算法有关系。

无论问题是否病态，好的算法都会得到好的近似解。

解对数据的微小变化高度敏感是病态的。

高精度运算可以改善问题的病态性。

用一个稳定的算法计算良态问题一定会得到好的近似值。

用一个收敛的迭代法计算良态问题一定会得到好的近似值。

两个相近数相减必然会使有效数字损失。

计算机上将1000个数量级不同的数相加，不管次序如何结果都是一样的。

7．考虑二次代数方程的求解问题ax2 + bx + c = 0.下面的公式是熟知的bb24acx.2a与之等价地有x?对于2c?b?b?4ac2.a = 1,b = -100 000 000 ,c = 1应当如何选择算法？8．指数函数有著名的级数展开x2x3e?1?x2!3!x 如果对x 9．考虑数列xi, i = 1,…, n, 它的统计平均值定义为x?1n?xi xi?1 它的标准差2?1n2(xi?x)? n?1i?1??1 数学上它等价于1n222xinx n1i11 作为标准差的两种算法，你如何评价它们的得与失？第二章非线性方程求根1．判断如下命题是否正确：(a) 非线性方程的解通常不是唯一的；(b) Newton法的收敛阶高于割线法；(c) 任何方法的收敛阶都不可能高于Newton法； (d)Newton法总是比割线法更节省计算时间；(e) 如果函数的导数难于计算，则应当考虑选择割线法；(f) Newton法是有可能不收敛；(g) 考虑简单迭代法xk+1 = g(xk)，其中x* = g(x*)。

关于常见排序算法的稳定性分析和结论（转载）收藏|2007-10-16 09:25这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当然如果你笔试之前已经记住了数据结构书上哪些是稳定的，哪些不是稳定的，做起来应该可以轻松搞定。

本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

其次，说一下稳定性的好处。

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。

基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。

另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。

回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。

比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

数据结构排序算法稳定性总结——写给⾃⼰看⼀、排序分类（1）插⼊类：直接插⼊排序、折半插⼊排序、希尔排序（2）交换类：冒泡排序、快速排序（3）选择类：简单选择排序、堆排序（属于树形选择排序）（4）归并类：2-路归并排序（5）分配类：基数排序⼆、排序稳定性及其原因（1）稳定排序：直接插⼊排序、折半插⼊排序、冒泡排序、2-路归并排序、基数排序直接插⼊排序：每次将⼀个待排序的记录，按其关键字的⼤⼩插⼊到已经排好序的⼀组记录的适当位置上。

在数组内部前半部为排好序的记录，后半部是未排好序的。

⽐较时从前半部的后向前⽐较，所以不会改变相等记录的相对位置。

折半插⼊排序：将直接插⼊排序关键字⽐较时的查找利⽤“折半查找”来实现，本质并没有改变还是⼀种稳定排序。

冒泡排序：通过两两⽐较相邻记录的关键字，如果发⽣逆序，则进⾏交换。

也不会改变相等记录的相对位置。

2-路归并排序：将两个有序表合并成⼀个有序表。

每次划分的两个⼦序列前后相邻。

合并时每次⽐较两个有序⼦序列当前较⼩的⼀个关键字，将其放⼊排好序的序列尾部。

因为两⼦序列相邻，合并时也没有改变相等记录的相对位置，所以也是稳定的。

基数排序：对待排序序列进⾏若⼲趟“分配”和“收集”来实现排序。

分配时相等记录被分配在⼀块，没有改变相对位置，是⼀种稳定排序。

（2）不稳定排序：希尔排序、快速排序、堆排序希尔排序：采⽤分组插⼊的⽅法，将待排序列分割成⼏组，从⽽减少直接插⼊排序的数据量，对每组分别进⾏直接插⼊排序，然后增加数据量，重新分组。

经过⼏次分组排序之后，对全体记录进⾏⼀次直接插⼊排序。

但是希尔对记录的分组，不是简单的“逐段分割”，⽽是将相隔每个“增量”的记录分成⼀组（假如：有1~10⼗个数，以2为增量则分为13579、246810两组）。

这种跳跃式的移动导致该排序⽅法是不稳定的。

快速排序：改进的冒泡排序。

冒泡只⽐较相邻的两个记录，每次交换只能消除⼀个逆序。

快排就是通过交换两个不相邻的记录，达到⼀次消除多个逆序。

数据结构——排序——8种常⽤排序算法稳定性分析⾸先，排序算法的稳定性⼤家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

在简单形式化⼀下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

其次，说⼀下稳定性的好处。

排序算法如果是稳定的，那么从⼀个键上排序，然后再从另⼀个键上排序，第⼀个键排序的结果可以为第⼆个键排序所⽤。

基数排序就是这样，先按低位排序，逐次按⾼位排序，低位相同的元素其顺序再⾼位也相同时是不会改变的。

另外，如果排序算法稳定，对基于⽐较的排序算法⽽⾔，元素交换的次数可能会少⼀些(个⼈感觉，没有证实)。

回到主题，现在分析⼀下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序冒泡排序就是把⼩的元素往前调或者把⼤的元素往后调。

⽐较是相邻的两个元素⽐较，交换也发⽣在这两个元素之间。

所以，如果两个元素相等，我想你是不会再⽆聊地把他们俩交换⼀下的；如果两个相等的元素没有相邻，那么即使通过前⾯的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是⼀种稳定排序算法。

(2)选择排序选择排序是给每个位置选择当前元素最⼩的，⽐如给第⼀个位置选择最⼩的，在剩余元素⾥⾯给第⼆个元素选择第⼆⼩的，依次类推，直到第n-1个元素，第n个元素不⽤选择了，因为只剩下它⼀个最⼤的元素了。

那么，在⼀趟选择，如果当前元素⽐⼀个元素⼩，⽽该⼩的元素⼜出现在⼀个和当前元素相等的元素后⾯，那么交换后稳定性就被破坏了。

⽐较拗⼝，举个例⼦，序列5 8 5 2 9，我们知道第⼀遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是⼀个稳定的排序算法。

(3)插⼊排序插⼊排序是在⼀个已经有序的⼩序列的基础上，⼀次插⼊⼀个元素。

当然，刚开始这个有序的⼩序列只有1个元素，就是第⼀个元素。

应用数学领域内算法稳定性和收敛性评估在应用数学领域中，算法的稳定性和收敛性评估是十分重要的研究领域。

在许多实际问题中，我们需要设计和实施数值算法来解决复杂的数学问题。

然而，算法的稳定性和收敛性是决定算法可靠性和有效性的关键因素。

稳定性评估涉及到算法在输入数据微小变化时输出结果的变化情况。

一个稳定的算法是指对于微小的输入干扰，其输出结果只有微小的变化。

反之，一个不稳定的算法对于微小的输入变化可能会导致输出结果的巨大变化。

因此，算法的稳定性评估是确保数值计算结果可靠性的重要环节。

为了评估算法的稳定性，我们可以采用不同的数学工具和技术，如条件数和误差分析。

条件数是一种度量矩阵或线性方程组对输入数据的敏感性的指标。

较小的条件数意味着算法对输入数据的变化更加稳定。

而误差分析则涉及到对数值计算过程中产生的舍入误差进行分析，以便评估算法的稳定性。

另一个重要的评估指标是算法的收敛性。

收敛性是指算法在逐渐逼近目标解时的性能表现。

一个良好的数值算法应该能够在有限的迭代次数内达到所需的精度。

因此，评估算法的收敛性是确保算法能够高效解决数值问题的关键因素。

在评估算法的收敛性时，我们需要考虑迭代序列逼近目标解的速度和稳定性。

一种常见的评估方法是利用收敛速度的收敛阶作为指标。

收敛阶定义了迭代序列逼近目标解的速度。

较高的收敛阶意味着算法能够更快地收敛到目标解。

同时，我们也可以考虑迭代过程中的局部收敛性和全局收敛性。

局部收敛性是指算法在初始近似值附近能够快速收敛到目标解的能力，而全局收敛性则是指算法对于任意初始近似值都能够收敛到目标解的能力。

评估算法的稳定性和收敛性需要使用数学理论和方法进行分析。

以求解线性方程组的迭代算法为例，我们可以采用矩阵理论、数值分析和最优化方法等工具来评估算法的性能。

这些方法可以帮助我们理解算法背后的数学原理，并提供相应的评估指标和技术。

同时，实际应用中的问题可能十分复杂，可能涉及到非线性方程组、优化问题、微分方程等。

数值微分方程的稳定性分析数值微分方程是求解微分方程数值解的一种方法，它在很多科学和工程领域具有重要的应用价值。

然而，数值微分方程的求解过程中存在着一些稳定性问题，对于保证数值解的准确性和可靠性具有重要意义。

稳定性是指在数值计算过程中，解的误差是否会放大或者衰减。

如果数值方法对于微小的扰动非常敏感，解的误差会不断放大，从而导致数值解的不可信。

而如果数值方法对于微小的扰动具有稳定性，解的误差可以被控制在一定的范围内，数值解就是可靠的。

为了进行数值微分方程的稳定性分析，一般采用线性稳定性和非线性稳定性两种方法。

下面我将分别介绍这两种方法。

1. 线性稳定性分析线性稳定性分析是通过对数值微分方程进行离散化，然后分析离散化误差的增长情况来判断数值方法的稳定性。

常用的线性稳定性分析方法有稳定性函数法和相容性条件法。

稳定性函数法是通过构造稳定性函数来分析离散化误差的增长情况。

稳定性函数是一个关于步长和离散化参数的函数，当稳定性函数的模小于等于1时，数值方法是稳定的。

相容性条件法则是通过对方程进行泰勒展开，得到离散化误差的表达式，然后对离散化误差进行分析得到稳定性条件。

2. 非线性稳定性分析非线性稳定性分析是在线性稳定性分析的基础上，进一步考虑微分方程的非线性特性对稳定性的影响。

非线性稳定性分析通常使用Lyapunov函数方法和能量方法来进行。

Lyapunov函数方法通过构造Lyapunov函数，根据Lyapunov函数的增减性判断数值方法的稳定性。

当Lyapunov函数单调递减时，数值方法是稳定的。

能量方法则是通过考虑系统的能量守恒来进行稳定性分析，通常通过构造系统的总能量以及能量的变化率来进行分析。

总结起来，数值微分方程的稳定性分析对于保证数值解的准确性和可靠性至关重要。

通过线性稳定性分析和非线性稳定性分析，可以判断数值方法的稳定性，并选择合适的数值方法来求解微分方程。

在实际应用中，还需要结合数值方法的精度、效率等方面进行综合考虑，以获得满足实际需求的数值解。

专业 序号 姓名 日期实验1 算法的数值稳定性实验【实验目的】1．掌握用MATLAB 语言的编程训练，初步体验算法的软件实现；2．通过对稳定算法和不稳定算法的结果分析、比较，深入理解算法的数值稳定性及其重要性。

【实验内容】1．计算积分 ()dx a x x I n⎰+=10)(n (n=0,1,2......，10) 其中a 为参数，分别对a=0.05及a=15按下列两种方案计算，列出其结果，并对其可靠性，说明原因。

2．方案一 用递推公式 n aI I n 11n +-=- (n=1,2,......,10) 递推初值可由积分直接得)1(0aa In I += 3. 方案二 用递推公式 )1(11-n nI a I n +-= (n=N,N -1,......,1) 根据估计式 ()()()11111+<<++n a I n a n 当1n a +≥n 或()()n1111≤<++n I n a 当1n n a 0+<≤ 取递推初值为 ()()()()11212])1(1111[21N +++=++++≈N a a a N a N a I 当1a +≥N N 或 ()()]1111[21NN a I N +++= 当1a 0+<≤N N 计算中取N=13开始【程序如下】: % myexp1_1.m --- 算法的数值稳定性实验% 见 P11 实验课题(一)%function yyjjglobal n aN = 20; % 计算 N 个值a =0.05;%或者a=15% %--------------------------------------------% % [方案I] 用递推公式%I(k) = - a*I(k-1) + 1/k%I0 =log((a+1)/a); % 初值I = zeros(N,1); % 创建 N x 1 矩阵(即列向量),元素全为零I(1) =-a*I0+1;for k = 2:NI(k) =-a*I(k-1)+1/k;end% %--------------------------------------------% % [方案II] 用递推公式%I(k-1) = ( - I(k) + 1/k ) / a%II = zeros(N,1);if a >= N/(N+1)II(N)=(2*a+1)/(2*a*(a+1)*(N+1));elseII(N) =(1/(a+1)/(N+1)+1/N)/2;endfor k = N:-1:2II(k-1) =(-II(k)+1/k)/a;end% %--------------------------------------------% % 调用 matlab 高精度数值积分命令 quadl 计算以便比较III = zeros(N,1);for k = 1:Nn = k;III(k) = quadl(@f,0,1);end% %--------------------------------------------% % 显示计算结果clcfprintf('\n 方案I结果方案II结果精确值') for k = 1:N,fprintf('\nI(%2.0f) %17.7f %17.7f %17.7f',k,I(k),II(k),III(k))end% %--------------------------------------------function y = f(x) % 定义函数global n a % 参量 n 为全局变量y =x.^n./(a+x); % ★注意:这里一定要 '点' 运算return% %--------------------------------------------【运行结果如下】：当a=0.05方案I结果方案II结果精确值I( 1) 0.8477739 -919648916620722180000.0000000 0.8477739 I( 2) 0.4576113 45982445831036109000.0000000 0.4576113 I( 3) 0.3104528 -2299122291551805700.0000000 0.3104528 I( 4) 0.2344774 114956114577590290.0000000 0.2344776 I( 5) 0.1882761 -5747805728879515.0000000 0.1882761I( 6) 0.1572529 287390286443975.9400000 0.1572529I( 7) 0.1349945 -14369514322198.6540000 0.1349945I( 8) 0.1182503 718475716110.0577400 0.1182503I( 9) 0.1051986 -35923785805.3917770 0.1051986I(10) 0.0947401 1796189290.3695889 0.0947401I(11) 0.0861721 -89809464.4275704 0.0861724I(12) 0.0790247 4490473.3047119 0.0790247I(13) 0.0729718 -224523.5883125 0.0729718I(14) 0.0677800 11226.2508442 0.0677800I(15) 0.0632777 -561.2458755 0.0632777I(16) 0.0593361 28.1247938 0.0593361I(17) 0.0558567 -1.3474162 0.0558567I(18) 0.0527627 0.1229264 0.0527627I(19) 0.0499934 0.0464853 0.0499934I(20) 0.0475003 0.0476757 0.0475003当a=15方案I结果方案II结果精确值I( 1) 0.0319222 0.0319222 0.0319222I( 2) 0.0211673 0.0211673 0.0211673I( 3) 0.0158245 0.0158245 0.0158245I( 4) 0.0126326 0.0126326 0.0126326I( 5) 0.0105112 0.0105112 0.0105112I( 6) 0.0089993 0.0089993 0.0089993I( 7) 0.0078674 0.0078674 0.0078674I( 8) 0.0069883 0.0069883 0.0069883I( 9) 0.0062862 0.0062859 0.0062859I(10) 0.0057064 0.0057117 0.0057117I(11) 0.0053136 0.0052336 0.0052337I(12) 0.0036289 0.0048293 0.0048296I(13) 0.0224896 0.0044830 0.0044838I(14) -0.2659159 0.0041831 0.0041831I(15) 4.0554050 0.0039207 0.0039207I(16) -60.7685756 0.0036893 0.0036893I(17) 911.5874579 0.0034837 0.0034837I(18) -13673.7563129 0.0033002 0.0032998I(19) 205106.3973248 0.0031283 0.0031344I(20) -3076595.9098724 0.0030754 0.0029847>>【结果分析】：1、综上所述，当a=0.05的时候，方案二算法的结果从I(20)开始计算，刚开始的时候与精确解相差不大，但是随着计算的进行，误差变得越来越大，最终与原来的精确解相差十分巨大，而方案一算法的数值结果始终与精确解相差不大，是稳定的算法。

《数值分析》教学大纲课程编码：1511104802课程名称：数值分析学时/学分：32/2先修课程：《数学分析》、《高等代数》适用专业：数学与应用数学开课教研室：应用数学教研室一、课程性质与任务1．课程性质：本课程是数学与应用数学专业的专业选修课。

本课程开设在第7学期。

2．课程任务：通过本课程的学习，使学生理解有关数值计算的基本概念和理论，了解数值计算的基本思想，掌握常见基本数值计算方法和基本理论，使学生具备一定的科学计算、分析问题和解决问题的能力，为后继课程的学习打下坚实的数学基础。

二、课程教学基本要求掌握插值、函数逼近、数值积分、非线性方程、线性方程组的解等常见数值计算方法和相关理论，为后继课程学习奠定基础。

主要教学环节以课堂讲授为主。

成绩考核形式：期终成绩（闭卷考查）（70%）＋平时成绩（平时测验、作业、课堂提问、课堂讨论等）（30％）。

成绩评定采用百分制，60分为及格。

三、课程教学内容第一章 数值分析与科学计算引论1.教学基本要求通过本章的学习使学生了解数值分析的研究对象、主要方法及误差的分类，掌握有效数字位数的确定以及设计算法过程中应注意的一些事项。

2.要求学生掌握的基本概念、理论、原理通过本章学习，使学生掌握误差、相对误差、有效数字的概念，掌握避免误差危害的常见方法。

3.教学重点和难点教学重点是误差与有效数字的概念及计算，避免有效数字损失的方法。

教学难点是有效数字概念的理解，算法的稳定性分析。

4.教学内容第一节 数值分析的对象、作用与特点1．数学科学与数值分析2．计算数学与科学计算3．计算方法与计算机第二节 数值计算的误差1．误差来源与分类2．误差与有效数字3．数值运算的误差估计第三节 误差定性分析与避免误差危害 1．算法的数值稳定性2．病态问题与条件数3．避免误差危害第二章 插值法1.教学基本要求掌握常见插值方法；了解常见插值方法的联系及区别，并能熟练地进行运算。

2.要求学生掌握的基本概念、理论、原理掌握Lagrange插值多项式的构造与误差的估计；掌握Newton插值多项式的构造；掌握两种典型的Hermite插值多项式的构造； 掌握分段低次插值多项式的构造及特点；了解三次样条插值多项式的构造及特点。

⼏种排序算法的稳定性归纳
排序算法的稳定性定义：
⼀个数组中⼏个相同的关键字经过排序以后相对位置仍然不变，那么称改排序算法的是稳定的。

举个例⼦，在⼀个数组中，紫⾊的10排在红⾊的10前⾯，经过排序算法之后，紫⾊的10位置仍然排序红⾊的10之前，那么这个算法就是稳定的。

下⾯是⼏种排序算法的总结：
1.冒泡排序：
稳定
2.选择排序：
2.1.若为交换数值式的排序算法，则为不稳定
2.2.若为插⼊式的排序算法(多应⽤于链表当中)，则稳定
3.插⼊排序：
稳定
4.快速排序：
不稳定
5.希尔排序：
不稳定
6.归并排序：
稳定
7.堆排序：
不稳定
8.基数排序：
稳定。

前面有讲到了9种排序算法:1.简单选择排序2.堆排序(1和2是属于选择排序)3.直接插入排序4.希尔排序(3和4属于插入排序,有时把改进后的直接插入排序叫做二分插入)5.冒泡排序6.快速排序 (5和6属于交换排序.交换排序顾名思义是不停的交换数据位置.但实际上选择排序也在不停的交换元素,但次数较少,只有找到最大值才一次交换.侧重点还是在通过遍历或堆来选择出最值.而冒泡排序就是通过不停交换相邻元素得出最大值,快速排序也在不停交换元素使序列一步步接近有序.侧重在交换)7.基数排序8.桶排序(7和8属于分配排序)9.归并排序面对这以多排序算法你可能郁闷着要自己排序时用哪种算法好呢? 每种算法适用哪些场景?为了对比上面各种不同算法,可以从如下几个方面来考虑.1.排序算法的稳定性2.排序算法时间复杂度3.排序算法空间复杂度4.各种算法适用的最佳场景.排序算法稳定性所谓稳定性是指待排序的序列中有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2.稳定也可以理解为一切皆在掌握中,元素的位置处在你在控制中.而不稳定算法有时就有点碰运气,随机的成分.当两元素相等时它们的位置在排序后可能仍然相同.但也可能不同.是未可知的.另外要注意的是:算法思想的本身是独立于编程语言的,所以你写代码去实现算法的时候很多细节可以做不同的处理.采用不稳定算法不管你具体实现时怎么写代码,最终相同元素位置总是不确定的(可能位置没变也可能变了).而稳定排序算法是你在具体实现时如果细节方面处理的好就会是稳定的,但有些细节没处理得到的结果仍然是不稳定的.比如冒泡排序,直接插入排序,归并排序虽然是稳定排序算法,但如果你实现时细节没处理好得出的结果也是不稳定的.稳定性的用处我们平时自己在使用排序算法时用的测试数据就是简单的一些数值本身.没有任何关联信息.这在实际应用中一般没太多用处.实际应该中肯定是排序的数值关联到了其他信息,比如数据库中一个表的主键排序,主键是有关联到其他信息.另外比如对英语字母排序,英语字母的数值关联到了字母这个有意义的信息.可能大部分时候我们不用考虑算法的稳定性.两个元素相等位置是前是后不重要.但有些时候稳定性确实有用处.它体现了程序的健壮性.比如你网站上针对最热门的文章或啥音乐电影之类的进行排名.由于这里排名不会像我们成绩排名会有并列第几名之说.所以出现了元素相等时也会有先后之分.如果添加进新的元素之后又要重新排名了.之前并列名次的最好是依然保持先后顺序才比较好.哪些算法是稳定的呢稳定性算法:基数排序 , 直接插入排序, 冒泡排序, 归并排序不稳定性算法: 桶排序, 二分插入排序,希尔排序, 快速排序, 简单选择排序,堆排序种算法稳定性详解(1)基数排序(稳定)与桶排序(不稳定)这两种算法都是属于分配排序算法.(利用元素值本身的信息直接映射到一个辅助序列中变成有序的.而不是通过与其他元素比较确定顺序位置)基数排序因为在是把低位按顺序映射到一个临时序列中去,是依次序映射,没有涉及到数据位置的变动.然后再按高位顺序映射.所以相同元素也是按次序映射过去.所以是稳定的如果数据元素没有重复的则采用简单桶排序,此时没有重复元素,所以自然不存在稳不稳定这一说.如果有重复元素得用改进的桶排序.此时辅助的临时数组只是通过索引来识别待排序元素的键值.丢失了其他信息(这是所有采用辅助的临时序列的算法中唯一一个会丢失信息的算法).假如待排序元素是一个map类型,按它的键值来排序.其他算法采用辅助序列时是把map类型做为元素去考虑的.而只有改进的桶排序不会把map类型当元素,只是利用到了键值信息. 这样一来就无法区分键值相同的信息,因此自然是不稳定的算法了啊.(2)归并排序(稳定)归并排序使得了递归的思想,把序列递归的分割成小序列,然后合并排好序的子序列.当有序列的左右两子序列合并的时候一般是先遍历左序列,所在左右序列如果有相等元素,则处在左边的仍然在前,这就稳定了.但是如果你非得先遍历右边序列则算法变成不稳定的了.虽然这样排出来的序也是对的,但变成了不稳定的,所以是不太好的实现.3)简单选择排序(不稳定)与堆排序(不稳定)这两种算法都属于选择排序.(从待排序的元素中挑选出最大或最小值.下面的例子以最小值为例)简单选择排序由于选出最小值后需要交换位置,位置一变就会变得不稳定.例如8 3 8 1.当从左往右遍历找最小值时,找到了1,这就需要把8跟1交换.这样两个相等元素8的位置就变了.堆排序的话,也会存在跟上面一样的交换最大值的位置会导致不稳定.例如有大堆8 8 6 5 2.先选出第一个最大值8,放最末尾.此时就不稳定了.因为第二个8就跑它前面去了.(4)冒泡排序(稳定)与快速排序(不稳定)这两种算法都属于交换排序.冒泡是通过不停的遍历,以升序为例,如果相邻元素中左边的大于右边的则交换.碰到相等的时就不交换保持原位.所以是稳定的.当然如果你非得吃饱了撑着了,在碰到相等的时也交换下,那肯定变成不稳定的算法了.快速排序是不稳定的.举例8 5 6 6 .以8为基准,第一趟交换后最后一个6跑到第一位,8到最后.第二趟交换.这个6跑到5的位置.变成有序的了.两个6位置变了,所以是不稳定的. (5)直接插入(稳定),二分插入排序(不稳定)与希尔排序(不稳定)直接插入时是先在已排序好的的子序列中找到合适的位置再插入.假设左边是已排序的,右边是没排序的.通过从后向前遍历已排序序列,然后插入,此时相等元素依然可以保持原有位置.但是如果你从前向后遍历已排序序列就会是不稳定排序了.二分插入排序是不稳定的,因为通过二分查找时得到的位置不稳定.例如3 4 4 5 4.但把最后一个4插入时肯定会跑到第二个4前面去了.所以是不稳定的.通过上面的分析我们可以得出这样一个经验之谈.1.只要不涉及到两个元素之间位置的交换就肯定是稳定的排序算法.比如归并排序,基数排序.(桶排序不稳定是个特例,因为它丢失了附带信息,不然的话可以弄成稳定排序的)2.在涉及到不同位置元素交换的算法中除了冒泡和直接插入排序是稳定的,其他都是不稳定的.你可以这样想,之所以出现相同元素位置变了就是其中一个交换位置时从另一个头顶跳过去了,而冒泡算法是相邻位置互换,跳不过去的,碰到相等元素的时候就停住不交换了.而直接插入排序是往已排好序的序列中插入.所以你通过由后往前遍历碰到相等的时就停住,这样也能保持稳定.但记住一定得从后往前遍历,不然也会不稳定.(所以说直接插入是半稳吧,而冒泡是非常的稳啊,除非你闲得蛋痛非得把两相等的元素两两交换)时间复杂度O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)一般时间复杂度到了2^n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2^n).平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.空间复杂度冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n 的临时数组.基数排序的空间复杂是O(n),桶排序的空间复杂度不确定最快的排序算法是桶排序所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.1.待排序的元素不能是负数,小数.2.空间复杂度不确定,要看待排序元素中最大值是多少.所需要的辅助数组大小即为最大元素的值.。