Java基礎(chǔ)算法：堆排盯孙，快排，二分查找
1. 堆排
滿二叉樹：所有葉結(jié)點(diǎn)都有同樣的深度捻勉，每個(gè)內(nèi)部結(jié)點(diǎn)都有兩個(gè)兒子
完全二叉樹：若二叉樹的高度為h镀梭，除第h層外刀森，其他各層(1 ~ h -1)的結(jié)點(diǎn)數(shù)都達(dá)到了最大個(gè)數(shù)踱启，第h層從右向左連續(xù)若干結(jié)點(diǎn)；也就是說一個(gè)結(jié)點(diǎn)有右結(jié)點(diǎn)研底，也一定有左結(jié)點(diǎn)
滿二叉樹是一種特殊的完全二叉樹埠偿，滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹
代碼：
public class HeapSort {
public static void main(String[] args) {
int[] nums = {5, 1, 6, 3, 7, 2, 9, 4, 0, 8};
//進(jìn)行排序
heapSort(nums);
System.out.println("排序后: " + Arrays.toString(nums));
}
/**
* 進(jìn)行排序
*/
private static void heapSort(int[] nums) {
//創(chuàng)建最大堆
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);
}
}
/**
* 從小到達(dá)排序榜晦，建立最大堆
* 創(chuàng)建的時(shí)間復(fù)雜度為 O(N)
* 由于葉結(jié)點(diǎn)沒有子結(jié)點(diǎn)冠蒋，直接從最后一個(gè)非葉結(jié)點(diǎn)的結(jié)點(diǎn)開始
*/
private static void create(int[] nums) {
int len = nums.length;
//最后一個(gè)非葉結(jié)點(diǎn)是第 n/2 個(gè)結(jié)點(diǎn)
for (int i = len / 2; i > -1; i--) {
siftDown(nums, i, len);
}
}
/**
* 數(shù)組角標(biāo)從0開始，左兒子結(jié)點(diǎn)為 2 * i + 1乾胶；右兒子結(jié)點(diǎn)為 2 * i + 2抖剿；
*排序的時(shí)間復(fù)雜度為 O(NlogN)
* @param nums 數(shù)組
* @param index 向下調(diào)整的父結(jié)點(diǎn)編號(hào)
* @param last 數(shù)組的最后角標(biāo)
*/
private static void siftDown(int[] nums, int index, int last) {
//左兒子結(jié)點(diǎn)
int left = index * 2 + 1;
//右兒子結(jié)點(diǎn)
int right = left + 1;
//將父結(jié)點(diǎn)賦予臨時(shí)結(jié)點(diǎn)
int temp = index;
//左兒子結(jié)點(diǎn)沒有越界并且父結(jié)點(diǎn)上的值小于左兒子結(jié)點(diǎn)的值
if (left < last && nums[left] > nums[index]) {
//將左兒子結(jié)點(diǎn)賦予臨時(shí)結(jié)點(diǎn)
temp = left;
}
//右兒子結(jié)點(diǎn)沒有越界并且父結(jié)點(diǎn)上的值小于右兒子結(jié)點(diǎn)的值
if (right < last && nums[right] > nums[temp]) {
//將右兒子結(jié)點(diǎn)賦予臨時(shí)結(jié)點(diǎn)
temp = right;
}
//父結(jié)點(diǎn)和臨時(shí)結(jié)點(diǎn)不相同朽寞，證明兒子結(jié)點(diǎn)有比父結(jié)點(diǎn)大的情況
if (index != temp) {
//交換結(jié)點(diǎn)的值
swap(nums, index, temp);
//再次進(jìn)行篩選
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;
}
}
結(jié)果：
最大堆: [9, 8, 6, 4, 7, 2, 5, 3, 0, 1]
排序后: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2. 快排
尋找中間值角標(biāo)，右側(cè)先開始查找比中間值小的斩郎，然后左側(cè)尋找比中間值大的脑融，然后交換，直到中間值左側(cè)都比中間值小缩宜，右側(cè)都比中間值大
代碼
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) {
// 角標(biāo)未越界
if (low < high) {
int index = findPartIndex(nums, low, high);
quickSort(nums, low, index - 1);
quickSort(nums, index + 1, high);
}
}
/**
* 找到一個(gè)樞軸值肘迎，這個(gè)臨界值左邊的數(shù)都比這個(gè)樞軸值小，右邊都比這個(gè)樞軸值大
*
* @param nums 數(shù)組
* @param left 最左側(cè)索引
* @param right 最右側(cè)索引
* @return 樞軸值的角標(biāo)
*/
private static int findPartIndex(int[] nums, int low, int high) {
// 臨時(shí)角標(biāo)
int i = low;
int j = high;
// 臨時(shí)值锻煌，對比值
int temp = nums[low];
while (i < j) {
// 先從右側(cè)開始比較妓布，若當(dāng)前最右側(cè)的值大于等于樞軸值，角標(biāo)減 1
while (i < j && nums[j] >= temp) {
j--;
}
// 左側(cè)開始比較宋梧，若當(dāng)前最左側(cè)的值小于等于樞軸值匣沼，角標(biāo)加 1
while (i < j && nums[i] <= temp) {
i++;
}
// 到了這一步，就說明右側(cè)找到了一個(gè)比樞軸值小
// 而左側(cè)找到了一個(gè)比樞軸值大的值
if (i < j) {
// 進(jìn)行交換,將大的值放在右邊捂龄，小的值放在左面
int n = nums[j];
nums[j] = nums[i];
nums[i] = n;
}
}
// 出了while循環(huán)肛著，說明 i == j ，因?yàn)?i 在++ 跺讯， j 在--
// 將 j 位置上的值賦予最左側(cè)
// 其中 j 就是臨界角標(biāo)
nums[low] = nums[j];
// 將之前的基準(zhǔn)值枢贿，賦予樞軸值角標(biāo)位置
nums[j] = temp;
return j;
}
}
3. 二分查找
二分查找作用于一個(gè)有序的序列，有兩種思路：循環(huán)和遞歸
代碼:
public class BinarySearch {
public static void main(String[] args) {
int[] nums = {11, 13, 23, 24, 34, 46, 67, 89, 98};
int key = 23;
//循環(huán)
int v = binarySearch(nums, key);
System.out.println("循環(huán):" + 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);
}
/**
* 利用循環(huán)
* 從Java api中復(fù)制出來的
*/
private static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
//早起JDk使用的(low + high) / 2刀脏，但會(huì)有有臨界值bug
//當(dāng)數(shù)組的大小足夠大時(shí)局荚，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);
}
}
}
結(jié)果:
循環(huán):2
遞歸:2
Java api:2
4. 最后
網(wǎng)上看到別人面試問到這些，再次復(fù)習(xí)學(xué)習(xí)下
有錯(cuò)誤請指出
共勉 : ）
