1. 快排
快速排序有多种实现方式, 有递归和非递归, 之前遇到的解法多是递归的, 而且分成了两部分代码, 较难理解和使用, 这个实现较为简单, 容易理解, 所有代码包括在一个方法里. 非递归解法暂不考虑. 快排的思路是在一个数组中取一个基准, 将比基准大的放到右侧 (从小到大), 比基准小的放到左侧, 然后递归实现两部分. 中间可以简易优化的部分是在取基准的序号时可以使用随机数. 整个过程总结来说, 算法大致思路一般能够考虑到, 重要的是各种边界条件的测试. 以下代码实现和简单的测试例子.
2. 二分查找
首先数组是已经排好序的, 每次折半取值, 如果相等返回序号值, 否则返回 -1 , 表示没有找到. 其实重点考虑的是各项边界条件, 如单值数组, 折半前序大于后序 (是否考虑相等), 数组首个值查找, 数组尾值查找等情况.
- /**
- * created by igoso at 2018/1/5
- **/
- public class SortMethod {
- public static void main(String[] args) {
- int num = 12;
- final int[] arr = new int[num];
- for (int i = 0; i <num; i++) {
- arr[i] = (int) (Math.random() * 1000) + 1;
- }
- System.out.println(Arrays.toString(arr));
- //simple qsort
- simpleQsort(arr,0,arr.length -1);
- System.out.println(Arrays.toString(arr));
- int[] arr1 = {1};
- //binary search
- System.out.println(binarySearch(arr1,1,0,arr1.length -1 ));
- }
- public static void simpleQsort(int[] arr, int left, int right) {
- if (arr == null || arr.length <= 1 || left>= right) {
- return;
- }
- /**
- * or idx = new Random.nextInt(right - left + 1) + left;
- */
- int idx = (left + right) / 2;
- int i = left, j = right, pivot = arr[idx];
- while (i <j) {
- while (arr[i] < pivot) {
- ++i;
- }
- while (arr[j]> pivot) {
- --j;
- }
- if (i <j) {
- int t = arr[i];
- arr[i] = arr[j];
- arr[j] = t;
- ++i;
- --j;
- } else if (i == j) {
- ++i;
- }
- }
- // 此处有些人可能考虑 i+1, j-1, 这样会导致部分排序没有完成, 是错误的.
- simpleQsort(arr, i, right);
- simpleQsort(arr, left, j);
- }
- /**
- * simple binary search for integer array
- * @param arr
- * @param value
- * @param left
- * @param right right 初次必须是 length - 1 , 否则某些 case 下会有错误, 如 {1,2,3} --> 3
- * @return
- */
- public static int binarySearch(int[] arr, int value, int left, int right) {
- if (arr == null || left> right) {
- return -1;
- }
- int idx = (left + right) / 2;
- if (arr[idx] == value) {
- return idx;
- }
- if (arr[idx]> value) {
- idx = binarySearch(arr, value, left, idx - 1);
- // 注意此处必须是 if else , 否则会多次匹配, 导致去 index = -1 报错
- }else if (arr[idx] < value) {
- idx = binarySearch(arr, value, idx + 1, right);
- }
- return idx;
- }
- }
来源: http://www.jianshu.com/p/1bdc9d7af3f6