boss直聘|算法 | Java 常见排序算法(纯代码)

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