算法笔试面试
十大排序算法:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序、希尔排序、计数排序,基数排序,桶排序。
ps:重点在理解原理,写代码的时候要由里往外写。
冒泡排序:
思想:两个相邻的元素比较并交换。
public static void bubbleSort(int[] arr) {
if(arr.length == 0){
return;
}
// 一共进行元素-1次排序
for (int i = 0; i < arr.length -1; i++) {
// 只需要对没有排序的进行排序
for (int j = 0; j < arr.length - 1 - i; j++) {
//将前一个比后一个大的两元素进行交换
if (arr[j+1] < arr[j]) {
// int tmp = arr[j+1];
// arr[j+1] = arr[j];
// arr[j] = tmp;
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
public static void main(String[] args) {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
选择排序
思想:每次从剩余元素中找最大(最小)元素进行交换。
public static void selectSort(int[] arr) {
if(arr.length == 0){
return;
}
// 升序
// 用于记录最小元素的下标位置
for (int j = 0; j < arr.length; j++) {
int index = j;
for (int i = index; i < arr.length -1; i++) {
if(arr[index] > arr[i+1]){
index = i+1;
}
}
// 找到了最小元素的位置之后,进行元素的交换
int tmp = arr[j];
arr[j] = arr[index];
arr[index] = tmp;
System.out.println(Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
插入排序
对于基本有序的数组来说最好用。
思想:就好像是打麻将或者是玩扑克牌。只不过略微有点区别。
public static void insertSort(int[] arr) {
if(arr.length == 0){
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i ; j >0; j--) {
if(arr[j ] < arr[j - 1]){
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
System.out.println(Arrays.toString(arr));
}
}
public static void main(String[] args) {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
爬楼梯
方法一:递归解法
public static int climbStairs(int n) {
if(n == 0){return 0;}
if(n == 1){return 1;}
if(n == 2){return 2;}
return climbStairs(n-1) + climbStairs(n-2);
}
public static void main(String[] args) {
System.out.println(climbStairs(3));
}
以上的解法存在重复计算的问题,我们可以使用hashmap集合来保存我们已经计算过的结果。
private static HashMap<Integer,Integer> map = new HashMap();
public static int climbStairs2(int n) {
if(n == 0){return 0;}
if(n == 1){return 1;}
if(n == 2){return 2;}
if(null != map.get(new Integer(n))){
return map.get(new Integer(n));
}
int reslut = climbStairs(n-1) + climbStairs(n-2);
map.put(new Integer(n),reslut);
return reslut;
}
标签:面试题,return,int,笔试,arr,算法,static,排序,public
From: https://www.cnblogs.com/dongyaotou/p/18440458