常见排序算法以及时间复杂度

一、冒泡排序：

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

冒泡排序最好的情况是一趟就排完时间复杂度为O(n);

最坏的情况就是刚好是反序的需要循环（n-1）趟每趟需要循环（n-1-i）次时间复杂度为（(n-1)*n）/2 也就是O(n^2)

所以冒泡排序的平均时间复杂度为O(n^2)；

二、选择排序：

public void selectSort(int[] a) {
        for(int i=0;i<a.length;i++){
            int k=i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[k]){
                    k=j;
                }
            }
            if(k>i){
                int temp = a[i];
                a[i]=a[k];
                a[k]=temp;
            }
        }
    }

选择排序最好、最差、平均时间复杂度均为：O(n^2)

三、快速排序：

public class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
 
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素
长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过logn趟划分,时间复杂度为O(nlogn)


平均情况下：T(n)=2*T(n/2)+n;      第一次划分

      =2*（2*T(n/4)+n/2）+n;     第二次划分  (=2^2*T(n/4)+2*n)

      =2*(2*(2*T(n/8)+n/4)+n/2)+n;     第三次划分(=2*3*T(n/8)+3*n)

      =.....................

      =2^m+m*n;  第m次划分

因为2^m=n,所以等价于 = n+m*n
所以m=logn，所以T(n)=n+n*logn;   

快速排序的平均时间复杂度是O(n*logn)