boss直聘|算法 | Java 常见排序算法（纯代码）

目录

汇总

序号	排序算法	平均时间	最好情况	最差情况	稳定度	额外空间	备注	相对时间
1	冒泡算法	O(n 2 )	O(n)	O(n 2 )	稳定	O(1)	n 越小越好	182 ms
2	选择算法	O(n 2 )	O(n 2 )	O(n 2 )	不稳定	O(1)	n 越小越好	53 ms
3	插入算法	O(n 2 )	O(n)	O(n 2 )	稳定	O(1)	大部分排序好时好	16 ms

4	快速算法	O(nlog 2 n)	O(nlog 2 n)	O(n 2 )	不稳定	O(nlog 2 n)	n 大时好	719 ms
5	归并算法	O(nlog 2 n)	O(nlog 2 n)	O(nlog 2 n)	稳定	O(n)	n 大时好	550 ms
6	希尔算法	O(nlog 2 n)	O(n)	O(n 2 )	不稳定	O(1)		197 ms/4 ms
7	堆排序	O(nlog 2 n)	O(nlog 2 n)	O(nlog 2 n)	不稳定	O(1)	n 大时好	3 ms

8	计数排序	O(n+k)	O(n+k)	O(n+k)	稳定	O(n+k)	k 是桶的数量	2 ms
9	桶排序	O(n+k)	O(n)	O(n 2 )	稳定	O(n+k)		11 ms
10	【boss直聘\|算法 \| Java 常见排序算法（纯代码）】基数排序	O(n*k)	O(n*k)	O(n*k)	稳定	O(n+k)		4 ms

11	优先队列				不稳定	O(n)		9 ms
12	Java API					O(1)		4 ms

1. 冒泡排序每轮循环确定最值；
public void bubbleSort(int[
nums){ int temp; boolean isSort = false; //优化，发现排序好就退出
for (int i = 0; i < nums.length-1; i++) { for (int j = 0; j < nums.length-1-i; j++) { //每次排序后能确定较大值
if(nums[j
> nums[j+1
){
isSort = true;
temp = nums[j
;
nums[j
= nums[j+1
;
nums[j+1