Java基础算法：堆排，快排，二分查找
1. 堆排
满二叉树：所有叶结点都有同样的深度，每个内部结点都有两个儿子
完全二叉树：若二叉树的高度为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]
2. 快排
寻找中间值角标，右侧先开始查找比中间值小的，然后左侧寻找比中间值大的，然后交换，直到中间值左侧都比中间值小，右侧都比中间值大
代码
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));
}
private static void quickSort(int[] nums, int low, int high) {
// 角标未越界
if (low < high) {
int index = findPartIndex(nums, low, high);
quickSort(nums, low, index - 1);
quickSort(nums, index + 1, high);
}
}
/**
* 找到一个枢轴值，这个临界值左边的数都比这个枢轴值小，右边都比这个枢轴值大
*
* @param nums 数组
* @param left 最左侧索引
* @param right 最右侧索引
* @return 枢轴值的角标
*/
private static int findPartIndex(int[] nums, int low, int high) {
// 临时角标
int i = low;
int j = high;
// 临时值，对比值
int temp = nums[low];
while (i < j) {
// 先从右侧开始比较，若当前最右侧的值大于等于枢轴值，角标减 1
while (i < j && nums[j] >= temp) {
j--;
}
// 左侧开始比较，若当前最左侧的值小于等于枢轴值，角标加 1
while (i < j && nums[i] <= temp) {
i++;
}
// 到了这一步，就说明右侧找到了一个比枢轴值小
// 而左侧找到了一个比枢轴值大的值
if (i < j) {
// 进行交换,将大的值放在右边，小的值放在左面
int n = nums[j];
nums[j] = nums[i];
nums[i] = n;
}
}
// 出了while循环，说明 i == j ，因为 i 在++ ， j 在--
// 将 j 位置上的值赋予最左侧
// 其中 j 就是临界角标
nums[low] = nums[j];
// 将之前的基准值，赋予枢轴值角标位置
nums[j] = temp;
return j;
}
}
3. 二分查找
二分查找作用于一个有序的序列，有两种思路：循环和递归
代码:
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
4. 最后
网上看到别人面试问到这些，再次复习学习下
有错误请指出
共勉 : ）
