数组的简单排序和查找

　　本文主要介绍数组的选择排序、冒泡排序两种简单排序算法，以及indexOf和有序数组的二分查找法。

1. 选择排序

　　我们的需求是使用选择排序给 int[] a = { 5, 42, 1, -2, 100 } 数组排序。主要的思路就是[0]号元素逐一和后面的元素比较，如果大则置换位置；之后使用[1]、[2] ......号元素和后面的元素比较，这样就可以实现元素的升序排序。算法大致就是这样的：

 1 public static void selectionSort(int[] array){
 2     int tmp = 0;
 3     for (int i = 0; i < array.length - 1; i++) {
 4         for (int j = i + 1; j < array.length; j++) {
 5             if (array[i] > array[j]) {
 6                 tmp = array[i];
 7                 array[i] = array[j];
 8                 array[j] = tmp;
 9             }
10         }
11     }
12 }

　　Java 中的选择排序是这样的：

2. 冒泡排序

　　我们再使用冒泡排序给 int[] a = {5, 42, 1, -2, 100} 数组排序，思路就是对数组的元素进行“两两比较”，较大的置换到后面的位置上去。算法大致就是这样的：

 1 public static void bubbleSort(int[] array) {
 2     int tmp = 0;
 3     for (int i = 0; i < array.length - 1; i++) {
 4         for (int j = 0; j < array.length - i - 1; j++) {    
 5             if (array[j] > array[j + 1]) {
 6                 tmp = array[j];
 7                 array[j] = array[j + 1];
 8                 array[j + 1] = tmp;
 9             }
10         }
11     }
12 }
13 
14 public static void main(String[] args) {
15     int[] array = {5, 42, 1, -2, 100};
16     bubbleSort(array);
17     System.out.println(printArray(array));
18 }
19 
20 输出：
21 
22 [ -2, 1, 5, 42, 100 ]

　　Java 中的冒泡排序是这样的：

3. indexOf查找元素

　　一个普通的查找方法，即传入待查找元素，返回该元素的下标位置，如果未找到返回 -1

 1 public static int indexOf(int[] arr, int element) {
 2         
 3         // 如果数组为 null 或数组长度为 0，返回 -1
 4         if (arr == null || arr.length == 0)
 5             return -1;
 6 
 7         for (int i = 0; i < arr.length; i++) {
 8             if (arr[i] == element) // 如果元素找到，直接返回 index
 9                 return i;
10         }
11         return -1; // 如果没有，返回 -1
12 }

4. 有序数组的二分查找法

　　我们可能都玩过“猜数字”游戏，就是一个人随机想一个1~100的数字，另外一个人猜这个数字，前一个人只能提示猜的大了或是小了，使用的最常见的方式就是从最小值、最大值的中间猜，以此类推最终猜出这个数字。

　　二分查找法和上面的游戏类似，它最重要的要求就是数组有序。

　　首先比较1 / 2位置的元素和待查找元素：

　　如果待查找元素大，再比较3 / 4位置的元素 ......

　　如果待查找元素小，再比较1 / 4位置的元素 ......

　　......

　　如果使用上面的方式找到了元素，则返回位置；

　　如果没有找到元素，一种方式是返回-1，另外一种是返回可以插入位置的下标-(min+1)

　　代码如下：

 1 public static int binarySearch(int[] arr, int element){
 2         int min = 0;
 3         int max = arr.length - 1;
 4         int mid = 0;
 5 
 6         while (max >= min) {
 7             mid = (min + max) >> 1;
 8 
 9             if (arr[mid] > element)
10                 max = mid - 1;
11             else if (arr[mid] < element)
12                 min = mid + 1;
13             else 
14                 return mid;
15         }
16         return -(min+1); // 如果未找到，返回 -( 插入下标 + 1 )
17 }
18 
19 public static void main(String[] args) {
20 
21     int[] a = new int[]{ 2, 56, 100, 201, 340 };
22 
23     int index = binarySearch(a, 100);
24     System.out.println(index);
25 
26     index = binarySearch(a, 78);
27     System.out.println(index);
28 }
29 
30 输出：
31 
32 2
33 -3

　　如果返回非负数，表示元素存在，且 返回值 = 元素下标

　　如果返回负数，表示元素不存在，且 插入位置点 = -( 返回值 + 1 )

　　100 元素是数组的第三个元素，下标为 2。78 元素不存在，插入位置点为 2

　　JDK 源代码的二分查找法是这样的：