南京城乡住房建设厅网站,网站开发总出现出现404,网站制作手机网站,wordpress 用户登录ip记录稳定性#xff1a; 用一句话总结排序算法的稳定性就是#xff1a;同样的值#xff0c;在排完序之后改不改变相对次序。 举例#xff1a;arr[] {3,2,1,2,1,3}#xff0c;数组中共有1、2 、3各2个数#xff0c;排完序之后arr1[] {1,1,2,2,3,3}。稳定性是指排完序之后 用一句话总结排序算法的稳定性就是同样的值在排完序之后改不改变相对次序。 举例arr[] {3,2,1,2,1,3}数组中共有1、2 、3各2个数排完序之后arr1[] {1,1,2,2,3,3}。稳定性是指排完序之后arr[]中的第一个位置的1在arr1[]中是否还是第一个arr[]中第2个位置的1在arr1[]中是否还在第二个。 如果能保持不变证明这个算法有稳定性否则则称为没有稳定性。
这种有稳定性的排序对基础类型的数据来讲是没用的1就是1、2就是2相同数字之间任顺序调换丝毫没有影响但是如果是自定义的类就不同了。
举例 比如说Student类中有班级class和年龄age属性。 第一次先用age有小到大进行排序。排完序之后 年龄小 - 年龄大。 在紧接着用班级进行由小到大排序此时如果这个算法是有稳定性的那么排完序的结果里1班学生的内部年龄也一定是从小到大的。2班学生的内部年龄也一定是从小到大的。
再比如说。商品价格区间100 - 200先按照价格进行排序。再根据好评度进行排序。如果算法是由稳定性的那么得到的结果中第一条数据就是最物美价廉的商品。
排序算法总结 基于之前更新的所有帖子中所介绍的算法做一个总结。
时间复杂度额外空间复杂度稳定性选择排序 O ( N 2 ) O(N^2) O(N2) O ( 1 ) O(1) O(1)无冒泡排序 O ( N 2 ) O(N^2) O(N2) O ( 1 ) O(1) O(1)有插入排序 O ( N 2 ) O(N^2) O(N2) O ( 1 ) O(1) O(1)有归并排序 O ( N ∗ l o g N ) O(N * log^N) O(N∗logN) O ( N ) O(N) O(N)有随机快排 O ( N ∗ l o g N ) O(N * log^N) O(N∗logN) O ( l o g N ) O(logN) O(logN)无堆排序 O ( N ∗ l o g N ) O(N * log^N) O(N∗logN) O ( 1 ) O(1) O(1)无计数排序 O ( N ) O(N ) O(N) O ( M ) O(M) O(M)有基数排序 O ( N ) O(N ) O(N) O ( N ) O(N) O(N)有
总结 为了绝对速度选快排稳定性选归并排序占用空间少选堆排序。
