摘要：通常情況下，快速排序的時(shí)間復(fù)雜度為，但在最壞情況下它的時(shí)間復(fù)雜度會(huì)退化至，不過我們可以通過對(duì)輸入數(shù)組進(jìn)行隨機(jī)化打亂元素的排列順序來避免最壞情況的發(fā)生。

導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的offer，要被延期，offer失效，工作重新找。把準(zhǔn)備過程紀(jì)錄下來，共勉。

最初級(jí)

    public void bubbleSort(int[] a){
        int len = a.length;

        for(int i = 0; i < len; i++){
            for(int j = 1; j < len; j++){
                if(a[j - 1] > a[j]){
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

小優(yōu)化

    public void bubbleSort(int[] a){
        int len = a.length;

        for(int i = 0; i < len; i++){
            for(int j = 1; j < len - i; j++){
                if(a[j - 1] > a[j]){
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

大優(yōu)化，一次冒泡過程沒有交換，直接退出排序

    public void bubbleSort(int[] a){
        int len = a.length;

        boolean flag = true;

        while(flag){
            flag = false;
            for(int j = 0; j < len - 1; j++){
                if(a[j] > a[j + 1]){
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
        }
    }

快速排序是目前應(yīng)用最廣泛的排序算法之一，它是一般場(chǎng)景中大規(guī)模數(shù)據(jù)排序的首選，它的實(shí)際性能要好于歸并排序。通常情況下，快速排序的時(shí)間復(fù)雜度為O(nlogn)，但在最壞情況下它的時(shí)間復(fù)雜度會(huì)退化至O(n^2)，不過我們可以通過對(duì)輸入數(shù)組進(jìn)行“隨機(jī)化”（打亂元素的排列順序）來避免最壞情況的發(fā)生。除了實(shí)際執(zhí)行性能好，快速排序的另一個(gè)優(yōu)勢(shì)是它能夠?qū)崿F(xiàn)“原地排序”，也就是說它幾乎不需要額外的空間來輔助排序。

public static void quickSort(int[] a){
    qSort(a, 0, a.length - 1);
}

private static void qSort(int[] a, int low, int high){
    if(low < high){
        int pivot = partition(a, low, high);
        qSort(a, low, pivot - 1);
        qSort(a, pivot + 1, high);
    }
}

private static void partition(int[] a, int low, int high){
    int pivotValue = a[low];
    while(low < high){
        while(low < high && a[high] >= pivotValue){
            high--;
        }
        a[low] = a[high];
        
        while(low < high && a[low] <= pivotValue){
            low++;
        }
        a[high] = a[low];
    }
    a[low] = pivotValue;
    return low;
}

關(guān)于快排的不穩(wěn)定性

穩(wěn)定性的概念并不復(fù)雜，它只表示兩個(gè)值相同的元素在排序前后是否有位置變化。如果前后位置變化，則排序算法是不穩(wěn)定的，否則是穩(wěn)定的。穩(wěn)定性的定義符合常理，兩個(gè)值相同的元素?zé)o需再次交換位置，交換位置是做了一次無用功。
兩個(gè)循環(huán)在進(jìn)行元素比較時(shí)，分別用了小于和大于操作（也可以改用小于等于和大于等于，但是對(duì)性能沒有影響）。這就意味著如果出現(xiàn)和pivot值相同的元素，它都會(huì)被作為交換對(duì)象而移動(dòng)到pivot的前面或者后面，這就出現(xiàn)了值相同的元素會(huì)交換順序的問題，因而是不穩(wěn)定的。

本節(jié)參考 http://blog.csdn.net/yutianzu...

快排的優(yōu)化

優(yōu)化選取樞軸,優(yōu)化不必要的交換
三數(shù)取中，即取三個(gè)關(guān)鍵字先進(jìn)行排序，將中間數(shù)作為樞軸， 一般是取左端、右端和中間三個(gè)數(shù)， 也可以隨機(jī)選取。
修改partition算法

private static int partition(int[] a, int low, int high){
    choosePivotValue(a, low, high);
    int pivotValue = a[low];
    
    while(low < high){
        while(low < high && a[high] > pivotValue){
            high--;
        }
        //swap(a,low ,high);交換
        //采用替換而不是交換的方式進(jìn)行操作
        a[low] = a[high];
        while(low < high && a[low] < pivotValue){
            low++;
        }
        a[high] = a[low];
    }
    a[low] = pivotValue;
    return low;
}

private static void swap(int[] a,int low,int high){
    int temp = a[low];
    a[low] = a[high];
    a[high] = temp;
}
//使中間值處于a[low]的位置
private static void  choosePivotValue(int[] a,int low,int high){
    int mid = (low + high) / 2;
    if(a[low] > a[high]){ // 保證左端較小
        swap(a, low, high);
    }
    if(a[mid] > a[high]){//保證中間較小
        swap(a, mid, high);
    }
    if(a[mid] > a[low]){//保證中間較小
        swap(a, low, mid);
    }
}

優(yōu)化小數(shù)組時(shí)的排序方案
快速排序適用于非常大的數(shù)組的解決辦法， 那么相反的情況，如果數(shù)組非常小，其實(shí)快速排序反而不如直接插入排序來得更好(直接插入是簡(jiǎn)單排序中性能最好的)。其原因在于快速排序用到了遞歸操作，在大量數(shù)據(jù)排序時(shí)，這點(diǎn)性能影響相對(duì)于它的整體算法優(yōu)勢(shì)是可以忽略的，但如果數(shù)組只有幾個(gè)記錄需要排序時(shí)，這就成了大材小用，因此我們需要改進(jìn)一下 qSort函數(shù)。

public static void qSort(int[] a, int low, int high){
    if((high - low) > MAX_LENGTH){
        int pivot = partition(a, low, high);
        qSort(a, low, pivot - 1);
        qSort(a, pivot + 1, high);
    }else{
        insertSort(a);
    }
}

private static void insertSort(int[] a){
    for(int i = 1; i < a.length; i++){
        int key = a[i];
        int j = i - 1;    
        while(j >= 0 && a[j] > key){
            a[j + 1] = a[j];
        }
        a[j + 1] = key;
    }
}

優(yōu)化遞歸操作
遞歸對(duì)性能是有一定影響的， qSort 函數(shù)在其尾部有兩次遞歸操作。
如果待排序的序列劃分極端不平衡，遞歸深度將趨近與N ，而不是平衡時(shí)的 logN,就不僅僅是速度快慢的問題了，棧的大小是很有限的，每次遞歸調(diào)用都會(huì)耗費(fèi)一定的空間 ，函數(shù)的參數(shù)越多，每次遞歸耗費(fèi)的空間也越多。如果能減少遞歸，將會(huì)提高性能。我們對(duì) qSort 實(shí)施尾遞歸優(yōu)化。

public static void qSort(int[] a, int low, int high){
    if((high - low) > MAX_LENGTH){
        while(low < high){
            int pivot = partition(a, low, high);
            qSort(a, low, pivot - 1);
            low = pivot + 1;
        }
    }else{
        insertSort(a);
    }
}

當(dāng)我們將 if 改成 while 后，因?yàn)榈谝淮芜f歸以后，變量low就沒有用處了，所以可以將pivot+1 賦值給low，再循環(huán)后，來一次 partition(arr,low,high)時(shí)，其效果等同于“qSort(arr, pivot+1, high);”。結(jié)果相同，但因采用迭代而不是遞歸的方法可以縮減堆棧深度，從而提高了整體性能。

本節(jié)參考 http://blog.csdn.net/scgaligu...

public static void sort(int[] a, int low, int high){
    int mid = (low + high) / 2;
    sort(a, low, mid);
    sort(a, mid + 1, high);
    merge(a, low, mid, high);
}

private static void merge(int[] a, int low, int mid, int high){
    int i = low;
    int j = mid + 1;
    int k = 0;
    int[] temp = new int[high - low + 1];
    
    while(i <= mid && j <= high){
        if(a[i] < a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    
    while(i <= mid){
        temp[k++] = a[i++];
    }
    
    while(j <= high){
        temp[k++] = a[j++];
    }
    
    for(k = 0; k < temp.length; k++){
        a[low + k] = temp[k];
    }
    
}

public static void choseSort(int[] a){
    for(int i = 0; i < a.length; i++){
        int lowIndex = i;
        
        for(int j = i; j < a.length; j++){
            if(a[j] < a[lowIndex]){
                lowIndex = j;
            }
        }
        
        int temp = a[i];
        a[i] = a[lowIndex];
        a[lowIndex] = temp;
    }
}

    public static void insertSort(int[] a){
        for(int i = 1; i < a.length; i++){
            int j = i - 1;
            int key = a[i];
            while(j >= 0 && a[j] > key){
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }

本文參考 http://blog.csdn.net/xsf50717...