标签：right day01 交换 mid 冒泡 有序 left

二分查找

手写代码

注意事项

索引溢出

如果right是最大整数值，而left又赋值为mid+1，则会溢出变成负数，不过这种情况毕竟是少数

解决方案

mid=left+(right-left)/2;

自己推

(left+right)>>>1;

无符号右移可以将1拉回来

选择题

查找次数确定

看mid指针指过多少个数

上限

log2n=log10n/log10 2

小数向上取整

注意事项

结论适用条件为jdk中的Arrays.binarySerch的实现方式

排序

冒泡排序

改进

• 最多比较n-1轮，如果i的初值为n-1（即此时全都无序），每轮最多比较i-1次
• 如果比较过程中，没有任何交换，说明已经完全有序，可直接退出循环
• 可以记录最后一次交换的索引，根据其确定下一轮的比较次数，即比较元素中位于左边的，j和j+1那么下一轮就是j

选择排序

改进

• 记录最小元素的索引，最后交换到目标位置，不要每次发现比之小的都交换

插入排序

算法思想

将无序区的元素逐渐插入有序区，逐渐扩大有序区至全部

改进

插入时，从后往前比，满足条件交换，不满足条件原地插入，原理在于有序。

冒泡VS选择

• 时间复杂度均为O(N^2)
• 一般选择快于冒泡，交换次数少
• 有序度高的情况下，优化后的冒泡快于选择，这导致了冒泡的一个适用场景
• 冒泡稳定，不会交换相同元素的次序，因为比较过程中前后相同不交换
• 选择不稳定，可能会交换相同元素的次序，因为等于也会交换的缘故?

标签：right,day01,交换,mid,冒泡,有序,left
From： https://www.cnblogs.com/zhouj-learn/p/16778253.html