深入淺出交換類排序算法

　　1）冒泡排序

　　冒泡排序在眾多排序算法中算比較簡單的一個，基本思想是重復的進行整個數列的排序，一次比較兩個元素(兩兩排序)，如果它們順序不符合就交換，重復這樣直到數列沒有再需要交換的數為止(結束條件)。就好像氣泡一樣，輕的氣泡會往上漂浮，在不斷漂浮的過程中，發生了兩兩交換過程，所以叫冒泡排序。

　　其實也可以用生活中的例子理解，就比如: 在軍訓排隊時，按個子高的和個子矮的的順序進行排列，個子高的和個子矮的會進行兩兩進行比較。

　　我們來大致看下算法的流程:

　　選一組序列 4, 3 , 5, 6, 2, 1 (極端情況)

　　從頭開始進行冒泡排序，1號和2號進行交換，4 > 3, 所以需要進行交換:

　　-> 3, 4, 5, 6, 2, 1

　　2號和3號進行交換，4<5，不交換

　　-> 3, 4, 5, 6, 2, 1

　　3號和4號進行交換，5<6，不交換

　　-> 3, 4, 5, 6, 2, 1

　　4號和5號進行交換，6>2，交換

　　-> 3, 4, 5, 2, 6, 1

　　5號和6號進行交換，6>1，交換

　　-> 3, 4, 5, 2, 1, 6

　　第一輪冒泡排序結束，把最大的數交換到最后一位，如此循環，直到沒有需要交換的元素為止，冒泡排序才結束。

　　代碼實現如下:

void BubbletSort(int*a,int len) {
    int m;
    for (bool bSwap=true; bSwap; len--) {
        bSwap = false;
        for (int j=1;j<len;j++) {
            if (a[j-1]>a[j]) {   // 交換值
                m=a[j];
                a[j]=a[j-1];
                a[j-1]=m;
                bSwap=true;
            }
        }
    }
}

　　其實冒泡排序整體看來是非常"傻"的，有很多可以優化的余地。比方說，每次比較如果發現較小的元素在后面，就交換兩個相鄰的元素，而如果我只掃描元素，記下最小元素，等一次掃描完后，再交換兩者為止，這樣最小元素就排到了前面，每掃描一次，只需要一次真正的交換，而剛才的冒泡可能需要交換多次，剛才說的算法優化其實就是選擇排序，以后我會細說，他屬于選擇排序的范疇。

　　我們來考慮下冒泡算法的復雜度:

　　在時間復雜度上，若待排序的序列為完全逆序，則每次都需要進行元素之間的交換，所以時間復雜度為O(   )，若待排序為順序，也就是不需要交換元素，但是需要掃描，所以還是需要O()的時間復雜度，平均情況下時間復雜度為O() 。

　　在空間復雜度上，需要輔助空間只有一個m(如上面代碼)，所以空間復雜度為O(1)。

　　2) 快速排序

　　如果大家還記得折半插入排序的過程：在一個有序序列中，插入關鍵字和折半序列的中間關鍵字進行比較，若小則在關鍵字左邊，若大則在關鍵字右邊。而快速排序和折半插入排序有異曲同工之妙，差別在于折半插入排序插入的序列自身是個有序序列，選取中間關鍵字時兩邊已經有序。而快速排序在于它不一定是有序的，它的操作過程是：隨便選取一個關鍵字(一般選取第一個)，讓所有關鍵字和它進行比較一次，小的放在左邊，大的放在它右邊，然后遞歸地對左邊和右邊進行排序。把該區間內的所有數依次與關鍵字比較，我們就可以在線性的時間里完成分割的操作。

　　我們來看下算法的步驟:

　　初始狀態：            【49，38，65，97，76，13，27，49'】
　　一次劃分后：         【27，38，13】 49 【76，97，65，49'】
　　分別進行快速排序:  【13】 27 【38】 【49'，65】76【97】
　　有序序列:             【13，27，38，49，49'，65，76，97】

　　上面是算法的大致步驟，一般完成分割操作有很多有技巧性的實現方法，比如最常用的一種是定義兩個指針，一個從前往后找找到比關鍵字大的，一個從后往前找到比關鍵字小的，然后兩個指針對應的元素交換位置并繼續移動指針重復剛才的過程。這只是大致的方法，具體的實現還有很多細節問題。

　　我們來看一下一輪快排序的細節步驟:

　　原始序列(i和j分別指向序列的最低和最高位置)：

　　選取第一個數49作為比較排序關鍵字。

　　1、使用j,從序列最右端開始掃描遇到比49小的則停止。

　　2、將27交換到i的位置

　　3、使用i，從序列最左端開始掃描遇到比49大的數則停止

　　4、將65交換到j的位置

　　5、再使用j向前掃描遇到比49小的13停止，并把13交換到i位置。

　　6、使用i向后掃描遇到比49大的97停止，并交換到j的位置

　　7、繼續使用j向前掃描遇到比49小的并停止，這時發現i和j相遇，代表掃描結束。

　　8、最后把49放置在ij的位置

　　從上面的一輪快排可以看出，49把整個序列劃分為兩個部分，小于49的在它左邊，大于49的在它右邊。根據算法思想再分別把49兩邊的序列進行快排一次。另外從整個排序過程來看，先對整個序列進行一次快排，然后再對其中子序列再進行快排，如此反復直到有序為止，整個過程是個遞歸的思想。所以代碼比較好寫，我們來實現一下。

// head=>序列的開頭
// tail=>序列的結尾
void quickSort(int array[], int head, int tail) {
    if (head > tail) {
        return;
    }
    // i,j指向頭和尾巴
    int i=head;
    int j=tail;
    int iPivot=array[i]; /**< 選取樞軸 */
    while (i<j) {
        // 使用j,從序列最右端開始掃描,直到遇到比樞軸小的數
        while ((i<j) && (iPivot <= array[j])) {
            j--;
        }
        // 交換位置
        if (i<j) {
            array[i++]=array[j];
        }
        // 使用i,從序列最左端開始掃描,直到遇到比樞軸小的數樞軸大的數
        while ( (i<j) && (array[i] <= iPivot) ) {
            i++;
        }
        // 交換位置
        if (i<j) {
            array[j--]=array[i];
        }
    }
    // 最后填入樞軸位置
    array[j]=iPivot;
    // 這里就是對樞軸兩邊序列進行排序的遞歸調用
    quickSort(array, head, i-1);
    quickSort(array, i+1, tail);
}

　　代碼已經嚴格測試過，一般不會有問題。下面我們來看下時間復雜度和空間復雜度。

　　快速排序有個特點，待排序列越接近無序，算法效率越高，也就是在基本有序的情況下時間復雜度為O()，最好情況下為O(  )，平均復雜度為O(  )，從所有內排序來看，快排是所有內排序中平均復雜度最好的，另外空間復雜度也為O( )。因為上面的算法實現是遞歸進行的，遞歸需要棧空間。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈