Java基础算法：堆排，快排，二分查找
满二叉树：所有叶结点都有同样的深度，每个内部结点都有两个儿子
完全二叉树：若二叉树的高度为h，除第h层外，其他各层(1 ~ h -1)的结点数都达到了最大个数，第h层从右向左连续若干结点；也就是说一个结点有右结点，也一定有左结点
满二叉树是一种特殊的完全二叉树，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
代码：
public class HeapSort { public static void main(String[] args) { int[] nums = {5, 1, 6, 3, 7, 2, 9, 4, 0, 8}; //进行排序 heapSort(nums); System.out.println("排序后: " + Arrays.toString(nums)); } /** * 进行排序 */ private static void heapSort(int[] nums) { //创建最大堆 create(nums); //打印出最大堆 System.out.println("最大堆: " + Arrays.toString(nums)); for (int i = nums.length - 1; i > 0; i--) { swap(nums, 0, i); siftDown(nums, 0, i); } } /** * 从小到达排序，建立最大堆 * 创建的时间复杂度为 O(N) * 由于叶结点没有子结点，直接从最后一个非叶结点的结点开始 */ private static void create(int[] nums) { int len = nums.length; //最后一个非叶结点是第 n/2 个结点 for (int i = len / 2; i > -1; i--) { siftDown(nums, i, len); } } /** * 数组角标从0开始，左儿子结点为 2 * i + 1；右儿子结点为 2 * i + 2； *排序的时间复杂度为 O(NlogN) * @param nums 数组 * @param index 向下调整的父结点编号 * @param last 数组的最后角标 */ private static void siftDown(int[] nums, int index, int last) { //左儿子结点 int left = index * 2 + 1; //右儿子结点 int right = left + 1; //将父结点赋予临时结点 int temp = index; //左儿子结点没有越界并且父结点上的值小于左儿子结点的值 if (left < last && nums[left] > nums[index]) { //将左儿子结点赋予临时结点 temp = left; } //右儿子结点没有越界并且父结点上的值小于右儿子结点的值 if (right < last && nums[right] > nums[temp]) { //将右儿子结点赋予临时结点 temp = right; } //父结点和临时结点不相同，证明儿子结点有比父结点大的情况 if (index != temp) { //交换结点的值 swap(nums, index, temp); //再次进行筛选 siftDown(nums, temp, last); } } /** * 交换值 */ private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }结果：
最大堆: [9, 8, 6, 4, 7, 2, 5, 3, 0, 1] 排序后: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]寻找中间值角标，右侧先开始查找比中间值小的，然后左侧寻找比中间值大的，然后交换，直到中间值左侧都比中间值小，右侧都比中间值大
代码
public class QuickSort { public static void main(String[] args) { int[] nums = {5, 1, 6, 3, 7, 2, 9, 4, 0, 8}; quickSort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } /** * 快排 * * @param nums 目标排序数组 * @param left 目标数组开始角标 * @param right 目标数组最后的角标 */ private static void quickSort(int[] nums, int left, int right) { //角标未越界 if (left < right) { //临时角标 int i = left, j = right; //临时值 int temp = nums[i]; //当i < j ，一旦i == j，退出循环 while (i < j) { //先从右侧开始比较，若当前最右侧的值大于等于临时值，角标减1 while (i < j && nums[j] >= temp) { j--; } //左侧开始比较，若当前最左侧的值小于等于临时值，角标加1 while (i < j && nums[i] <= temp) { i++; } //到了这一步，就说明右侧找到了一个比临时值小，而左侧找到了一个比临时大的值 if (i < j) { //进行交换,将大的值放在右边，小的值放在左面 swap(nums, i, j); } } //出了while循环，说明i == j ，因为i在++ ， j在-- //将j位置上的值赋予最左侧 nums[left] = nums[j]; //此时的临时值，还是最左侧的值，将最左侧的值赋予j位置 //此时j左侧都比j位置上的值小，而j右侧都比j位置上的值大，也就是中间值 nums[j] = temp; //再对left到中间值角标的数组进行排序 quickSort(nums, left, i - 1); //再对中间值角标到right的数组进行排序 quickSort(nums, i + 1, right); } } /** * 交换值 */ private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }二分查找作用于一个有序的序列，有两种思路：循环和递归
代码:
public class BinarySearch { public static void main(String[] args) { int[] nums = {11, 13, 23, 24, 34, 46, 67, 89, 98}; int key = 23; //循环 int v = binarySearch(nums, key); System.out.println("循环:" + v); //递归 int i = binarySearch(nums, 0, nums.length, key); System.out.println("递归:" + i); //Java api int index = Arrays.binarySearch(nums, key); System.out.println("Java api:" + index); } /** * 利用循环 * 从Java api中复制出来的 */ private static int binarySearch(int[] a, int key) { int low = 0; int high = a.length - 1; while (low <= high) { //早起JDk使用的(low + high) / 2，但会有有临界值bug //当数组的大小足够大时，low + high有可能超出int范围 //可以使用 low + (high - low)/2 int mid = (low + high) >>> 1;//速度更快 int midVal = a[mid]; if (midVal < key) { low = mid + 1; } else if (midVal > key) { high = mid - 1; } else { return mid; //找到key } } return -1; // 没有找到key } /** * 利用递归 */ private static int binarySearch(int[] a, int fromIndex, int toIndex, int key) { rangeCheck(a.length, fromIndex, toIndex); int mid = (fromIndex + toIndex) >>> 1; int midVal = a[mid]; if (midVal < key) { return binarySearch(a, mid + 1, toIndex, key); } else if (midVal > key) { return binarySearch(a, fromIndex, mid - 1, key); } else if (midVal == key) { return mid; } return -1; } /** * 检查是否越界 */ private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException( "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > arrayLength) { throw new ArrayIndexOutOfBoundsException(toIndex); } } }结果:
循环:2 递归:2 Java api:2