八大排序的思想及其代码

• 时间复杂度：最好O(n) 、最坏O(n²) 、平均O(n²)
• 稳定
  
  

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) 递归用到栈
不稳定