原文發(fā)表在我的博客：整數(shù)排序
求關(guān)注、求交流、求意見、求建議。

問題

LintCode：整數(shù)排序

描述

給一組整數(shù)，按照升序排序，使用選擇排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

樣例

對于數(shù)組 [3, 2, 1, 4, 5] ， 排序后為：[1, 2, 3, 4, 5] 。

實現(xiàn)

排序是最常見的算法了，但也不是人人都能信手拈來的。toptal 提供了 Sorting Algorithms Animations 幫助人們理解和對比各種排序，每一種排序都有介紹、偽代碼以及不同情況下的動畫演示，在這里向大家推薦。

意識排序

意識排序就是潛意識下寫出來的排序，并沒有一個名字。

class Solution {
public:
    void sortIntegers(vector<int>& A) {
        // 29ms
        int i, j, buffer;
        int size = A.size();
        for (i = 0; i < size; ++i)
            for (j = 0; j < i; ++j) {
                if (A[i] < A[j]) {
                    buffer = A[j];
                    A[j] = A[i];
                    A[i] = buffer;
                }
    }
}

冒泡排序

class Solution {
public:
    void sortIntegers(vector<int>& A) {
        // 33ms
        int i, j, buffer;
        bool swapped = true;
        int size = A.size();
        for (i = 0; i < size && swapped; ++i)
            for (j = size - 1, swapped = false; j > i; --j)
                if (A[j] < A[j - 1]) {
                    buffer = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = buffer;
                    swapped = true;
                }
    }
}

選擇排序

class Solution {
public:
    void sortIntegers(vector<int>& A) {
        // 28ms
        int i, j, key, buffer;
        int size = A.size();
        for(i = 0; i < size; ++i){
            key = i;
            for(j = i; j < size; ++j) {
                if(A[j] < A[key]) key = j;
            }
            buffer = A[i];
            A[i] = A[key];
            A[key] = buffer;
        }
    }
}

插入排序

class Solution {
public:
    void sortIntegers(vector<int>& A) {
        // 20ms
        int i, j, temp;
        int size = A.size();
        for(i = 1; i < size; ++i) {
            if(A[i] >= A[i - 1]) continue;
            temp = A[i];
            for (j = i - 1; j >= 0 && A[j] > temp; --j){
                A[j + 1] = A[j];
            }
            A[j + 1] = temp;
        }
    }
}

快速排序

class Solution {
public:
    void sortIntegers(vector<int>& A) {
        // 14ms
        Qsort(A, 0, A.size() - 1);
    }
    
    void Qsort(vector<int>& A, int low, int high) {
        if(low >= high) return;
        int begin = low;
        int end = high;
        int temp = A[low];
        while (begin < end) {
            while(A[end] >= temp) --end;
            A[begin] = A[end];
            while(begin < end && A[begin] <= temp) ++begin;
            A[end] = A[begin];
        }
        A[begin] = temp;
        Qsort(A, low, begin - 1);
        Qsort(A, begin + 1, high);
    }
}

總結(jié)

因為是很常見的排序，就沒有寫具體的分析，而且 Sorting Algorithms Animations 上給的很清晰。務(wù)必要打開看一下，非常好的網(wǎng)站。
雖然排序各種標準庫里都有，但是還是要多思考、多了解一點，不僅可以鍛煉一下邏輯能力，還可以在某些特殊情況下有奇效。