数组常见算法比较

1.选择排序

基本思想：
选择排序的基本思想是将指定排序位置与其他数组元素分别对比，如果满足条件则交换元素。
算法示例：

如图，先将下标为0的数组元素分别与其他元素相比，23<45,不交换（从小到大排序），再比较23与6，交换……这样将23与其他元素比较后，下标为0的元素变成了6。再将下标为1的元素与下标为2，3，4，5的元素进行比较，经过5轮这样的比较后，就可完成排序。
算法实现：

其中，交换方法的代码可以提取为一个函数：

ps：是交换数组元素的下标，如果函数参数是元素本身，只是交换了传递给参数的值，形参交换，函数结束形参被销毁，但是实参并未发生改变，所以得交换两个元素所在的地址（即下标），这样才能使实参真正交换。

算法优化：
上面的选择排序的第n趟从待排序的数据元素中选出最小元素，要进行n-1次比较，最多可能进行了n-1次下标的交换，才能将本轮的最小值放在对应的位置。可以用两个变量分别存储每次比较的最小值元素以及下标，这样便不需要每次比较后条件满足了就交换，只需要这轮比较完后将这两个临时变量的下标与本轮的下标进行交换，确定本轮的最小值。
优化算法的实现：

2.冒泡排序

基本思想：
冒泡排序的基本思想是对比相邻的元素值，如果满足条件就交换元素值，把较小的元素值移到数组前面，大的元素值移到数组后面，这样较小的元素就像气泡一样从底部上升到顶部。
算法示例：
冒泡排序由双层循环实现，其中外层循环用于控制排序的轮数，内层循环主要用于对比数组每个临近元素的大小。

算法实现：

或者

在java.util包里有定义好的函数来对数组进行排序：Arrays.sort(arr);

3.反转排序

反转排序就是以相反的顺序把原有数组的内容重新排序。
基本思想：
把数组最后一个元素与第一个元素替换，倒数第二个元素与第二个函数替换。依次类推，把所有的元素替换。
算法实现：

4.折半查找

对于无序的数组，查找某个元素在数组中的位置：直接遍历

对于有序的数组，查找可以有更加高效的算法：折半查找。
基本思想：
假设数组是升序的，取数组的中间下标作为基准：
如果查找的元素等于中间下标对应的元素，则已经找到；
如果查找的元素大于中间下标对应的元素，说明要查找的元素在数组的右半边，此时用中间下标对应的元素代替查找范围的最小值，再在新的范围内折半查找。
如果查找的元素小于中间下标的元素，说明查找的元素在数组的左半边，此时将中间下标对应的元素代替查找范围的最大值，在新的范围内进行查找。
如果查找范围最大值的下标小于查找范围的最小值的下标，说明数组内没有要查询的元素。
很显然对于在大量数据里的查找，我们可以将待查找的数据进行排序，然后再用折半查找进行查找，会提高查找的效率。
折半查找的时间复杂度为O(logn)。
算法示例：
对于数组[4,7,23,45,67,90,100,123]，查找23所对于的下标。
数组的中间下标是(0+7)/2=3，对应的值为45，由于23<45,因此查找的范围为原数组的左半边[4,7,23,45]，第一轮查找结束；
新的查找范围中间下标为（0+3）/2=1，对应的元素为7，由于7<23，因此查找的范围是右半边[23,45]，第二论查找结束；
新的查找范围中间下标为（0+1）/2=0，对应的元素是23，23==23，找到了，结束。
算法实现：

或者：

扩展：
如果给定一个有序的数组，往数组中插入一个数，保证数组还是有序的，求插入的位置（下标）。（ps:数组长度是固定的，不能增减元素，所以只是求插入的位置。）
只需要将折半查找的代码返回值改为返回min,而不是-1。
实际上java.util包里有函数Arrays.binarySearch(arr,key)，这个函数如果key在arr里，则返回对应的下标，否则，返回（-插入点位置-1）。