算法刷题小模版|八大排序的思想及其代码

【算法刷题小模版|八大排序的思想及其代码】算法刷题小模版|八大排序的思想及其代码
文章图片

插入排序 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) 递归用到栈
  • 不稳定
    算法刷题小模版|八大排序的思想及其代码
    文章图片

    推荐阅读