tags: DSA Sort C++ 寫在前面

總結一下經典的排序算法, 這次是基本排序算法, 冒泡插入和選擇, 加上自己的理解與C++實現.

成都創(chuàng)新互聯公司秉承實現全網價值營銷的理念，以專業(yè)定制企業(yè)官網，網站制作、成都網站設計，小程序開發(fā)，網頁設計制作，成都手機網站制作，網絡營銷推廣幫助傳統(tǒng)企業(yè)實現“互聯網+”轉型升級專業(yè)定制企業(yè)官網,公司注重人才、技術和管理，匯聚了一批優(yōu)秀的互聯網技術人才,對客戶都以感恩的心態(tài)奉獻自己的專業(yè)和所長。輔助代碼

這里給出了輸出數組的函數, 通過STL的vector來完成.

#include#includeusing namespace std;
void printArray(const vector& arr) {for (size_t i = 0; i< arr.size(); ++i) cout<< arr[i]<< " ";
    cout<< endl;
}

冒泡

最為經典的排序算法, 雖然時間復雜度也相當高, 應該是很多同學入門編程語言學到的第一個排序算法.

思路很簡單, 就是通過每次比較相鄰兩數的大小, 保證較大的那個值在后面, 如此進行n輪(數組長度), 即可得到排序好的數組.

void BubbleSort(vector& arr) {int n = arr.size();
    for (int i = n; i >0; --i) {// 每一輪都標記是否進行過交換
        bool exchanged = false;
        for (int j = 1; j< i; ++j)
            if (arr[j - 1] >arr[j]) {swap(arr[j - 1], arr[j]);
                exchanged = true;
            }
        if (!exchanged) break;
    }
}

另一種寫法:

void BubbleSort(vector& arr) {int n = arr.size();
    for (int i = 1; i< n; ++i) {bool exchanged = false;
        for (int j = 0; j< n - i; ++j)
            if (arr[j] >arr[j + 1]) {swap(arr[j], arr[j + 1]);
                exchanged = true;
            }
        if (!exchanged) break;
    }
}

插入

按照算法導論上面的比喻, 插入排序就是從桌上扣過來的未排序的撲克牌中依次向手上的已排好序的撲克牌中插入.

void InsertionSort(vector&arr) {int n = arr.size();
    // 左邊為已排序區(qū),右邊是待排序區(qū)
    for (int j = 1; j< n; ++j) {int i = j - 1, tmp = arr[j]; // tmp:待插入元素
        // 往后挪元素,騰出來位置留給tmp
        while (i >= 0 && arr[i] >tmp) {arr[i + 1] = arr[i];
            --i;
        }
        // 上面的這個while循環(huán)可以用for一行完成:
        // for (; i >= 0 && arr[i] >tmp; --i) arr[i + 1] = arr[i];
        // 最后插入tmp
        arr[i + 1] = tmp;
    }
}

但是這里我就有一個困惑了, 為什么不能用從前向后的遍歷方式呢?

后來我寫了個前向遍歷, 才發(fā)現了問題所在.

void InsertionSort(vector&arr) {int n = arr.size();
    // 遍歷待插入元素
    for (int i = 1; i< n; ++i) {int tmp = arr[i], j{};
        // 從前往后遍歷, 尋找插入位置(遍歷已排好序的元素)
        while (j< i && arr[j]<= tmp) ++j;
        if (j == i) continue;
        int idx = j;
        // 下面兩種for循環(huán), 結果是一樣的
        // for (; i >idx; --i) arr[i] = arr[i - 1];
        for (int k{}; k<= i - idx; ++k) arr[i - k] = arr[i - 1 - k];
        arr[idx] = tmp;
    }
}

前向遍歷需要先找到待插入的位置, 然后往后移動騰出來待插入元素要放置的位置, 相當于在遍歷未排序部分的內部套了兩個循環(huán), 而不是像后往前遍歷那樣直接在尋找到要插入的位置之后就直接進行挪元素了, 省去了一重循環(huán), 并且寫起來方便很多.

選擇

通過每次遍歷數組的未排序部分, 找到大值(或者最小值)放在已排序數組的末尾, 即可.

void SelectSort(vector&arr) {int n = arr.size(), i{};
    while (i< n) {int min1 = i;
        for (int j = i + 1; j< n; ++j)
            if (arr[min1] >arr[j]) min1 = j;
        if (min1 != i) swap(arr[min1], arr[i]);
        i++;
    }
}

或者for寫法:

void SelectSort(vector&arr) {int n = arr.size();
    for (int i{}; i< n; ++i) {int min1 = i;
        for (int j = i + 1; j< n; ++j)
            if (arr[min1] >arr[j]) min1 = j;
        if (min1 != i) swap(arr[min1], arr[i]);
    }
}

總結

這三種都是比較經典的原地排序算法, 但是時間復雜度都比較高, 其中蘊含的思路可以為之后的快排等算法打基礎.

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享文章：冒泡排序,插入排序,選擇排序的C++實現-創(chuàng)新互聯
轉載來源：http://weahome.cn/article/dpophs.html