`
茶是树叶
  • 浏览: 59262 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

算法稳定性

 
阅读更多
最近在看算法,书上关于稳定性的概念一带而过,甚觉不爽,于是网上搜了个貌似靠谱的答案。答案来自stackoverfollow

问:
I m very curious, why stability is or is not important in sorting algorithms?

Any ideas?

靠谱的答:
Background: a "stable" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:

peach straw apple spork

Stable-sorting by the first letter gives us:

apple peach straw spork

In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since 'straw' appears before 'spork' in the input, it also appears before 'spork' in the output).

We could sort the list of words using this algorithm: stable sorting by column 5, then 4, then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (by the way, that algorithm is called radix sort)

Now to answer your question, suppose we have a list of first and last names. We are asked to sort "by last name, then by first". We could first stable sort by the first name, then sort by the last name. After these sorts, the list is primarily sorted by the last name. However, where last names are the same, the first names are sorted.

You can't stack unstable sorts in the same fashion
分享到:
评论

相关推荐

    误差传播与算法稳定性matlab程序

    误差传播与算法稳定性是数值计算中的重要概念,特别是在使用计算机模拟和数据分析时。这两个概念直接影响到计算结果的准确性和可信度。本篇讨论的是在MATLAB环境中实现的两种不同的算法,用于计算某个序列的递推值,...

    误差传播与算法稳定性实验报告(1).doc

    误差传播与算法稳定性实验报告 本实验报告的主要目标是研究误差传播对算法稳定性的影响。实验中,我们使用了两种算法:算法一和算法二,并对其进行了比较和分析。结果表明,算法二比算法一具有更好的稳定性和准确性...

    算法稳定性MATLAB.exe

    算法稳定性MATLAB.exe

    视频监控中人脸识别算法稳定性的改进.pdf

    视频监控中人脸识别算法稳定性的改进 人脸识别是一项极具发展潜力的生物特征识别技术,研究人脸识别技术具有十分重要的理论和应用价值。最近几年,人脸识别技术取得了前所未有的发展,人脸识别在视频监控、人机交互...

    误差传播与算法稳定性实验报告.doc

    "误差传播与算法稳定性实验报告" 本实验报告的标题是"误差传播与算法稳定性实验报告”,它的目的是研究误差传播对算法稳定性的影响。实验报告的内容可以分为七个部分:实验目标、实验内容、算法描述、实验步骤、...

    一种改进的粒子群算法稳定性证明及其应用.pdf

    一种改进的粒子群算法稳定性证明及其应用 本文提出了一种改进的粒子群算法,并对其稳定性进行了证明。粒子群算法是一种基于群体智能的随机优化算法,由于其结构简单、运算速度快且不需要领域知识,因而广泛应用于...

    分布式网络拥塞控制算法稳定性研究.pdf

    综上所述,分布式网络拥塞控制算法稳定性研究涉及了网络技术、优化理论、系统稳定性等多个领域的知识,是计算机网络研究中的一个重要方向,对于实际的网络应用具有重要的实践价值。通过不断优化和改进拥塞控制算法,...

    协同过滤推荐算法稳定性研究.docx

    协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐...

    距离保护的仿真研究及其算法稳定性分析

    距离保护的仿真研究及其算法稳定性分析 距离保护的仿真研究及其算法稳定性分析距离保护的仿真研究及其算法稳定性分析

    试验一误差传播与算法稳定性一试验内容考虑一个简单由积分定义.pdf

    该实验主要探讨了误差传播和算法稳定性的概念,通过计算由积分定义的序列来分析不同算法的精度。实验内容涉及一个简单的积分序列,其定义为 \( I_n = \int_0^1 \frac{1}{x^n} dx \),对于 \( n=1 \) 时可以直接求解...

    实验一:误差传播与算法稳定性 一:实验内容 考虑一个简单由积分定义.doc

    实验一探讨了误差传播与算法稳定性的主题,重点关注了一个由积分定义的序列的计算方法。序列的初始定义为 ,并且当 时,可以利用分步积分得到递推关系。实验中提供了两种不同的算法来计算这个序列,即算法(Ⅰ) 和...

    ZXZ显式积分算法稳定性的数值模拟研究

    ZXZ显式积分算法稳定性的数值模拟研究,张晓志,李根,在瑞雷阻尼假定下,以设定结构体系动力响应的数值模拟为主,理论分析为辅,并结合与PJ算法以及LL算法的对比分析,研究了ZXZ直接显�

    协同过滤推荐算法稳定性研究.pdf

    然而,这种算法的稳定性是一个关键问题,因为它容易受到系统攻击,如恶意打分和随机连边,这可能导致推荐结果的不准确。 协同过滤推荐算法的稳定性研究主要关注在遭遇攻击时,算法能否保持推荐的准确性和一致性。...

    matlab验证算法数值稳定性的两个函数

    在MATLAB环境中,验证算法的数值稳定性是进行科学计算时非常关键的一个步骤。数值稳定性指的是一个算法在处理小数值或接近零的数值时,其结果的精确度和可靠性。这通常涉及到浮点误差、舍入误差以及算法设计的敏感性...

    算法的数值稳定性

    在数值分析领域,"算法的数值稳定性"是一个关键概念,它涉及到计算机在处理数学运算时可能出现的精度损失问题。在本实验中,我们将探讨如何测试和理解算法在实际计算过程中的稳定性。 数值稳定性指的是一个算法在...

    java排序算法的稳定性

    排序算法的稳定性排序算法的稳定性排序算法的稳定性

Global site tag (gtag.js) - Google Analytics