什么是排序算法的稳定性?
稳定: 如果 a = b, a原本在b的前面, 排序之后, a仍然在b的前面, 那么这个排序算法就是稳定的。反之, 就是不稳定的排序算法。
稳定的排序算法有:
思想:选取中间的数为基准值, 然后将比它小的放在左边, 比它大的放在右边, 然后将左右两边的数组进行同样的操作, 使用递归的思想。
注意三点:
1.要判断递归的边界条件, 当数组的长度 <= 1 时, 跳出递归;
2.最后进行数组合并时, 需要将基准值也合并进去;
3.splice是对原数组进行操作, 返回的是要删除的数组;
冒泡排序的原理:
比方说有五个数字54321, 要按从小到大排列;
首先比较前两个, 就是5和4, 如果第一个小于第二个, 不做操作, 如果第一个大于第二个, 那么交换二者的位置, 即变成45321, 然后比较第二个和第三个,交换位置, 变成43521, 然后第三个和第四个, 第四个和第五个, 这样一次循环下来, 变成43215;
所以, 一层循环的效果就是挑出最大的一个数字5, 冒泡到最后面。接着相似方法挑出第二大, 第三大的数字等。那么一层循环就不够用, 必须再嵌套一层。
像这个例子, 五个数字, 起码要进行四轮循环才行。 至于为什么要this.length - i, 是因为第一次比较五个数字, 第二个只要比较前四个就行了,第五个肯定是最大的了。
改进后的冒泡排序:
改进的思路: 将每趟排序中最后一次进行交换的位置pos记录下来, 下次排序只要扫描到pos即可。
最直观的排序算法
依次找出第一大、 第二大、 第三大...依次放在数组中
欢迎关注。