本文主要介绍数组的选择排序、冒泡排序两种简单排序算法,以及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 源代码的二分查找法是这样的: