Java面试题|【Java面试题】常见算法总结
常见算法
- 1、7种常见排序算法
-
- 1.1、冒泡排序
- 1.2、简单选择排序
- 1.3、直接插入排序
- 1.4、希尔排序
- 1.5、归并排序
- 1.6、快速排序
- 1.7、堆排序
1、7种常见排序算法 7种常见排序算法的时间复杂度、辅助空间以及稳定性对照表。
| 排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O()n^2 | O(1) | 稳定 |
| 直接插入排序 | O(n^2) | O(n) | O()n^2 | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
【Java面试题|【Java面试题】常见算法总结】时间复杂度： O(n^2)。
动态直观图：
文章图片
代码实现：
import java.util.Arrays;
public class BubbleSort {public static void main(String[] args) {int[] arr = new int[]{
3,78,34,50,89,1,45,7};
System.out.println("排序之前：" + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序之后：" + Arrays.toString(arr));
}/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){for(int i = arr.length - 1;
i >= 0;
i--){for(int j = 0;
j < i;
j++){if(arr[j] > arr[j + 1]){int tem = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tem;
}
}
}
}
}
结果：
排序之前：[3, 78, 34, 50, 89, 1, 45, 7]
排序之后：[1, 3, 7, 34, 45, 50, 78, 89]
1.2、简单选择排序 **原理：**在严蔚敏版本的《数据结构》中对选择排序的基本描述为：每一轮在n-i+1(i1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第
i个记录。假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端（也就是min1不等于arr[0]），则将最小值arr[0] = min1，接着在剩下的(n-1)个数字中找到最小值min2，如果最小值min2不等于arr[1]，那么则arr[1] = min2，依次类推，知道数组arr有序排列。时间复杂度： O(n^2)。
直观图解：
文章图片
代码实现：
import java.util.Arrays;
public class SelectSort {public static void main(String[] args) {int[] arr = new int[]{
3,78,34,50,89,1,45,7};
System.out.println("排序之前：" + Arrays.toString(arr));
selectSort(arr);
System.out.println("排序之后：" + Arrays.toString(arr));
}/**
* 简单选择排序
* @param arr
*/
static void selectSort(int[] arr){for(int i=0;
i arr[j]){index = j;
}
}if(index == i){continue;
} else {int tem = arr[index];
arr[index] = arr[i];
arr[i] = tem;
}
}
}}
结果：
排序之前：[3, 78, 34, 50, 89, 1, 45, 7]
排序之后：[1, 3, 7, 34, 45, 50, 78, 89]
1.3、直接插入排序 原理： 插入排序的基本思想就是将无序序列插入到有序序列中。例如：将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列（图中用蓝色标出），将[2,8,0,5,1]看做是一个无序序列，无序序列中2比4小，于是将2插入到4的左边，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，所以将8插入到4的右边，有序序列变成了[2,4,8]，无序序列变成了[0,5,1]。依次类推最终数组按照从小到大的排序。
时间复杂度： O(n^2)。
直观图：
文章图片
文章图片
代码实现：
import java.util.Arrays;
public class InsertSort {public static void main(String[] args) {int[] arr = new int[]{
4,2,8,0,5,1};
System.out.println("排序之前：" + Arrays.toString(arr));
insertSort(arr);
System.out.println("排序之后：" + Arrays.toString(arr));
}static void insertSort(int[] arr){for(int i=1;
i0;
j--){if(arr[j] < arr[j-1]){int tem = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tem;
}
}}
}
}
结果：
排序之前：[4, 2, 8, 0, 5, 1]
排序之后：[0, 1, 2, 4, 5, 8]
1.4、希尔排序 待续……
1.5、归并排序 待续……
1.6、快速排序 原理： 快速怕排序的基本思想是：通过一次排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实际上：
快速排序 = 冒泡 + 分治 + 递归。一趟快速排序的具体过程可描述为： 从待排序列中任意取出一个记录（通常选取第一个记录）作为基准值，然后将记录中比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序序列分成两个子序列。
一趟快速排序的具体做法为： 设置两个指针low和high分别指向待排序列的开始和结尾，记录下基准值baseval（待排序列的第一个记录），然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换，接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换，重复这两个步骤直到low=high为止。
时间复杂度： O(nlogn)。
直观图：
文章图片
文章图片
文章图片
代码实现：
import java.util.Arrays;
public class QuickSort {public static void main(String[] args) {int[] arr = new int[]{
4,2,8,0,5,1};
System.out.println("排序之前：" + Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("排序之后：" + Arrays.toString(arr));
}/**
* 快速排序
* @param arr 数组
* @param left 起始位置0
* @param right 末尾位置 (arr.length-1)
*/
static void quickSort(int arr[],int left,int right){//左右两指针相与直接返回
if(left >= right){return;
}
//为了方便起见，我们将i和j分别代表左右指针
int i = left;
int j = right;
//获取基准数(一般是以第一个数为基准数)
int baseval = arr[left];
while (i= baseval){//如果不小于，j指针就继续左移
j--;
}//从左向右找比基准数大的记录,
while (i 执行结果：
排序之前：[4, 2, 8, 0, 5, 1]
排序之后：[0, 1, 2, 4, 5, 8]
1.7、堆排序 待续……
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- PMSJ寻平面设计师之现代(Hyundai）
- 杜月笙的口才
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- Linux下面如何查看tomcat已经使用多少线程
- 皮夹克
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题