1冒泡排序

传统冒泡排序

  

public static void bubble(int[] arr){        int temp;        for(int i=arr.length-1;i>0;i--){            for(int j=0;j
     
      arr[j+1]){                    temp=arr[j];                    arr[j]=arr[j+1];                    arr[j+1]=temp;                }            }        }    }
     

 

时间复杂度O(n^2),只需一个额外空间O(1),稳定

传统冒泡排序有一个缺点，不管数据是否已经排序完成都会固定执行n(n-1)/2次，

我们可以在程序中加入判断来判断何时可以提前中断程序，提高效率

public static void bubble(int[] arr){        int temp;                for(int i=arr.length-1;i>0;i--){            int flag=0;  //flag用来判断是否有执行交换的动作            for(int j=0;j
     
      arr[j+1]){                    temp=arr[j];                    arr[j]=arr[j+1];                    arr[j+1]=temp;                    flag++;          //如果有交换，flag不为0                }                                }            if(flag==0){                break;            }    //当一次扫描判断后flag==0，没有交换动作，说明以完成排序，所以直接跳出循环        }    }
     

 

2选择排序法

时间复杂度O(n^2),只需一个额外空间O(1),不稳定

  

public static void select(int[] arr){        int tmp;     for(int i=0;i

 

    

3插入排序

时间复杂度O(n),只需一个额外空间O(1),稳定,会造成数据的大量搬移，建议在链表上使用

 

public static void insert(int[] arr){        int i,j;        for(i=1;i
     
      =0&&tmp
     

   

4快速排序

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。

package example; class Demo{    public static void main(String args[]) {      int[] arr={26,17,5,33,87,53,27,49,28,78};    quick(arr,arr.length,0,arr.length-1);    System.out.println("排序结果：");    for(int a:arr){        System.out.print(a+" ");    }     }private static void quick(int[] arr, int length, int i, int j) {    int left;    int right;    int tmp;    if(i
     
      arr[i]){                    left=x;                    break;                }                left++;            }            for(int y=j;y>=i+1;y--){                if(arr[y]
      
       =right){            tmp=arr[i];            arr[i]=arr[right];            arr[right]=tmp;            quick(arr,length,i,right-1);            quick(arr,length,right+1,j);                                            }            }}}
      
     

处理过程: [26][17][5][33][87][53][27][49][28][78]

处理过程: [5][17][26][33][87][53][27][49][28][78]

处理过程: [5][17][26][33][87][53][27][49][28][78]

处理过程: [5][17][26][33][28][53][27][49][87][78]

处理过程: [5][17][26][33][28][27][53][49][87][78]

处理过程: [5][17][26][27][28][33][53][49][87][78]

处理过程: [5][17][26][27][28][33][53][49][87][78]

处理过程: [5][17][26][27][28][33][49][53][87][78]

排序结果：

5 17 26 27 28 33 49 53 78 87