查找算法

---

二分查找

非常经典的查找算法，常用在已排序数组的查找上。 不过需要注意的还有几点：

注意代码鲁棒性：函数头判断low和high的合法性求mid时，用 mid = low + (high - low) / 2 防止溢出扩展：若含有重复数字，则可以返回第一次或最后一次出现的位置

代码示例：

public class BinarySearch { public static int binarySearch(int [] array, int des) throws Exception { if(array == null || array.length == 0) throw new Exception("Null Array!"); int low = 0, high = array.length - 1; int mid = 0; while(high >= low) { mid = low + (high - low) / 2; if(array[mid] == des) { return mid; } else if(array[mid] > des) { high = mid - 1; } else { low = mid + 1; } } throw new Exception("No such des."); } }

---

排序算法

经典的排序算法有：

插入排序选择排序冒泡排序希尔排序(Shellsort)归并排序快速排序堆排序

下面一一简单温习一遍：

---

插入排序

public class InsertionSort { public static void insertionSort(int [] array) { if(array == null || array.length == 0) return ; int j; for(int i = 1; i < array.length; i++) { int tmp = array[i]; for(j = i; j > 0 && array[j - 1] > tmp; j--) { array[j] = array[j - 1]; } array[j] = tmp; } } }

---

选择排序

public class SelectSort { public static void selectSort(int [] array) { for(int i = 0; i < array.length - 1; i++) { int k = i; for(int j = k; j < array.length; j++) { if(array[j] < array[k]) { k = j; } } if(k != i) { int tmp = array[k]; array[k] = array[i]; array[i] = tmp; } } } }

---

冒泡排序

public class BubbleSort { public static void bubbleSort(int [] array) { for(int i = 0; i < array.length - 1; i++) { for(int j = 0; j < array.length - 1 - i; j++) { if(array[j] > array[j + 1]) { int tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; } } } } }

---

希尔排序

希尔排序可以理解为: 对每隔gap长度的子数组进行插入排序操作，一道最后进行gap=1，即普通的插入排序操作。

public class ShellSort { public static void shellSort(int [] array) { int j; for(int gap = array.length / 2; gap > 0; gap /= 2) { for(int i = gap; i < array.length; i++) { int tmp = array[i]; for(j = i; j >= gap && array[j - gap] > tmp; j -= gap) { array[j] = array[j - gap]; } array[j] = tmp; } } } }

---

归并排序

归并排序应用了经典的分治策略(divide and conquer)，算法细节不再赘述，不过要注意的是，在算法进行过程中，只需要一个与待排序数组同样大小的空间做缓冲区即可，所以在排序驱动代码中创建一个tmp数组，然后在子函数传参的时候把tmp与array同时传递即可。

public class MergeSort { public static void mergeSort(int[] array) throws Exception { if(array == null || array.length == 0) { throw new Exception("Null array!"); } int[] tmp = new int[array.length]; mergeSort(array, tmp, 0, array.length - 1); } public static void mergeSort(int[] array, int[] tmp, int left, int right) { int center = (left + right) / 2; if(left < right) { mergeSort(array, tmp, left, center); mergeSort(array, tmp, center + 1, right); merge(array, tmp, left, center + 1, right); } } public static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) { int leftEnd = rightPos - 1; int tmpPos = leftPos; int length = rightEnd - leftPos + 1; while(leftPos <= leftEnd && rightPos <= rightEnd) { if(array[leftPos] > array[rightPos]) { tmp[tmpPos++] = array[rightPos++]; } else { tmp[tmpPos++] = array[leftPos++]; } } while(leftPos <= leftEnd) { tmp[tmpPos++] = array[leftPos++]; } while(rightPos <= rightEnd) { tmp[tmpPos++] = array[rightPos++]; } for(int i = 0; i < length; i++, rightEnd--) { array[rightEnd] = tmp[rightEnd]; } } }

---

快速排序