【算法刷题小模版|八大排序的思想及其代码】
文章图片
插入排序
1.直接插入排序
- 时间复杂度：最好O(n) 、最坏O(n2) 、平均O(n2)
- 稳定
文章图片
文章图片
public class Main{
public static void main(String[] args) {
int[] nums={4,5,8,7,9,6,3,2,1};
int len=nums.length;
int num=-1;
for (int i = 1;
i =0&&num 2.希尔排序
文章图片
交换排序 1. 冒泡排序
- 时间复杂度：最好O(n2)、最坏O(n2)、平均O(n2)
- 稳定
文章图片
public class Main{
public static void main(String[] args) {
int[] nums={4,5,8,7,9,6,3,2,1};
int len=nums.length;
for (int i = 0;
i < len - 1;
i++) {
boolean flag=false;
//表示本次遍历是否发生过交换
for (int j = len-1;
j >i;
j--) {
if(nums[j-1]>nums[j]){
int temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
flag=true;
}
}
if(!flag)break;
}
System.out.println(nums);
//本趟遍历没有发生过交换，说明有序
}
}
2.快速排序
- 时间复杂度：最好O(n l o g 2 n {log_2{n}} log2?n)、最坏O(n2)、平均O(n l o g 2 n {log_2{n}} log2?n)
- 空间复杂度：O(n l o g 2 n {log_2{n}} log2?n) 递归用到栈
- 不稳定
文章图片
推荐阅读
- 算法|递归和非递归详解
- OJ|OJ---腐烂的橘子
- leetcode|算法之快慢指针
- leetcode|快慢指针之练习【2】
- 神经网络|基于语音的疲劳度检测算法研究
- 算法|2021/2022届-Matlab数字图像处理—选题推荐
- 图文并茂！推荐算法架构——粗排
- 算法|深度优先和广度优先算法
- LeetCode|98. 验证二叉搜索树