数据结构 如何判断算法是否稳定

Question

如题所述

Answer 1

主要是看同样的输入或者执行过程结果是否一致.
大学里一般常接触的就是排序算法.
例如输入一串数字排序(原位子用①标号显示)
①5 ②2 ③9 ④3 ⑤7 ⑥3
1'排序后执行结果错误.
2'如果第一次排完结果是②④⑥①⑤③,第二次执行完结果为②⑥④①⑤③
虽然输出一样,但是这种算法就属于不稳定算法
3'如果是从前向后移动的算法,相同的数如果原前端的数在后(例如大数后移冒泡.最后结果④在⑥前面),就属于不稳定算法.

Answer 2

如果是复杂度，就多次测试的样本方差大小，如果小，则算法复杂度稳定
如果是排序，就看排序前后相同大小的元素相对位置有无变化，如果没有，则稳定，稳定的排序算法有冒泡排序，归并排序和插入排序，其他的常用排序比如快排基本都不是稳定排序

Answer 3

第一个用基本简单语言，第一个多拿数据测试，看结果怎样