直击!阿里百度常用算法面试内容都在这了，网友:再也不怕算法了
算法作为编程常用到的软技能，是面试和编程中常用的一项技能，本文将会分享常用算法的代码实战，例如：二分查找法、快速排序、桶排序、冒泡排序、堆排序、快速排序等算法！
冒泡排序
public class BubbleSort {
public static void bubbleSort(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
for (int j = 0; j < arrayLength - 1 - i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
}
}
System.out.println(java.util.Arrays.toString(data));
}
}
//优化1
public static void bubbleSort1(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLength - 1 - i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
flag = true;
}
}
System.out.println(java.util.Arrays.toString(data));
if (!flag)
break;
}
}
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
桶排序
public class BucketSort {
public static void bucketSort(int[] data, int min, int max) {
System.out.println("开始排序");
int arrayLength = data.length;
int[] temp = new int[arrayLength];
int[] buckets = new int[max - min];
for (int i = 0; i < arrayLength; i++) {
buckets[data[i] - min]++;
}
System.out.println(Arrays.toString(buckets));
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
System.out.println(Arrays.toString(buckets));
System.arraycopy(data, 0, temp, 0, arrayLength);
for (int k = arrayLength - 1; k >= 0; k--) {
data[--buckets[temp[k] - min]] = temp[k];
}
}
public static void main(String[] args) {
int[] data = { 9, 5, -1, 8, 5, 7, 3, -3, 1, 3 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bucketSort(data, -3, 10);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
堆排序
public class HeapSort {
public static void heapSort(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
buildMaxdHeap(data, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(data, 0, arrayLength - 1 - i);
System.out.println(java.util.Arrays.toString(data));
}
}
// 对data数组从0到lastIndex建大顶堆
private static void buildMaxdHeap(int[] data, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存当前正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex +1
// 代表k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 如果右子节点的值较大
if (data[biggerIndex] - data[biggerIndex + 1] < 0) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大子节点的值
if (data[k] - data[biggerIndex] < 0) {
// 交换它们
swap(data, k, biggerIndex);
// 将biggerIndex赋给k，开始while循环的下一次循环
// 重新保证k节点的值大于其左、右节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
// 交换data数组中i、j两个索引处的元素
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
heapSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
直接插入排序
public class InsertSort {
public static void insertSort(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {
int temp = data[i];
if (data[i] - data[i - 1] < 0) {
int j = i - 1;
for (; j >= 0 && data[j] - temp > 0; j--) {
data[j + 1] = data[j];
}
data[j + 1] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
insertSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
二分查找法
public class Locating {
public static void main(String[] args) {
// 线性查找：
String[] array1 = new String[] { "姐姐", "妹妹", "哥哥", "弟弟", "爸爸", "妈妈" };
String dest1 = "哥哥";
boolean isFlag1 = true;// 设立标识
for (int i = 0; i < array1.length; i++) {
if (dest1.equals(array1[i])) {// equals();内容比较
System.out.println(array1[i] + "查找成功,位置为：" + i);
isFlag1 = false;// 更新标识
break;
}
}
if (isFlag1) {
System.out.println("抱歉，未找到");
}
// 二分法查找：前提为所查找的数组必须有序
int[] array2 = new int[] { -98, -45, -2, 0, 12, 34, 56, 78, 89, 90, 100 };
int dest2 = 34;
int head = 0;// 初始的首索引
int end = array2.length - 1;// 初始的末索引
boolean isFlag2 = true;// 设立标识
while (head <= end) {
int middle = (head + end) / 2;
if (dest2 == array2[middle]) {
System.out.println(dest2 + "查找成功,位置为：" + middle);
isFlag2 = false;// 更新标识
break;
} else if (array2[middle] > dest2) {// 如果中间值大于所查找的值，从左边开始找
end = middle - 1;// end等于middle前一个索引，故-1
} else if (array2[middle] < dest2) {// 如果中间值小于所查找的值，从右边开始找
head = middle + 1;// head等于middle后一个索引，故+1
}
}
if (isFlag2) {
System.out.println("抱歉，未找到");
}
}
}
基数排序
public class MultiKeyRadixSort {
public static void radixSort(int[] data, int radix, int d) {
System.out.println("开始排序：");
int arrayLength = data.length;
int[] temp = new int[arrayLength];
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计第二个关键字
Arrays.fill(buckets, 0);
// 当data数组的元素复制到temp数组中进行缓存
System.arraycopy(data, 0, temp, 0, arrayLength);
for (int j = 0; j < arrayLength; j++) {
int subKey = (temp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
for (int m = arrayLength - 1; m >= 0; m--) {
int subKey = (temp[m] / rate) % radix;
data[--buckets[subKey]] = temp[m];
}
System.out.println("对" + rate + "位上子关键字排序："
+ java.util.Arrays.toString(data));
rate *= radix;
}
}
public static void main(String[] args) {
int[] data = { 1100, 192, 221, 12, 13 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
radixSort(data, 10, 4);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
快速排序
public class QuickSort {
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(int[] data, int start, int end) {
if (start < end) {
int base = data[start];
int low = start;
int high = end + 1;
while (true) {
while (low < end && data[++low] - base <= 0)
;
while (high > start && data[--high] - base >= 0)
;
if (low < high) {
swap(data, low, high);
} else {
break;
}
}
swap(data, start, high);
subSort(data, start, high - 1);//递归调用
subSort(data, high + 1, end);
}
}
public static void quickSort(int[] data){
subSort(data,0,data.length-1);
}
public static void main(String[] args) {
int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
直接选择排序
public class SelectSort2 {
public static void selectSort(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arrayLength; j++) {
if (data[minIndex] - data[j] > 0) {
minIndex = j;
}
}
if(minIndex != i){
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
selectSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
以上算法均为常用算法，小伙伴们如果能够掌握这些算法，面试中算法这个环节基本已经满分通过了，本文希望可以为还在为算法头疼的小伙伴们一些帮助，看完点个关注，后续更新文章才会得到及时通知哦！
