Linux C++中如何實現高效排序算法

在Linux環境下使用C++實現高效的排序算法，可以采用多種方法。以下介紹幾種常用且高效的排序算法，并附上相應的C++實現示例：

1. 標準庫中的 std::sort

C++標準庫提供了高效的排序函數 std::sort，它通?；诳焖倥判颍≦uickSort），并結合了插入排序（Insertion Sort）和堆排序（HeapSort）以保證最壞情況下的性能。std::sort 在大多數情況下表現優異，是首選的排序方法。

示例代碼

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data = {5, 2, 9, 1, 5, 6};
    
    // 使用 std::sort 進行排序
    std::sort(data.begin(), data.end());
    
    // 輸出排序結果
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

編譯與運行

g++ -o sort_example sort_example.cpp
./sort_example

2. 歸并排序（Merge Sort）

歸并排序是一種穩定的排序算法，時間復雜度為O(n log n)。適用于需要穩定排序的場景。

示例代碼

#include <iostream>
#include <vector>

void merge(std::vector<int> &data, int left, int mid, int right) {
    std::vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while(i <= mid && j <= right){
        if(data[i] <= data[j]){
            temp[k++] = data[i++];
        }
        else{
            temp[k++] = data[j++];
        }
    }
    
    while(i <= mid){
        temp[k++] = data[i++];
    }
    
    while(j <= right){
        temp[k++] = data[j++];
    }
    
    for(int p = 0; p < temp.size(); ++p){
        data[left + p] = temp[p];
    }
}

void mergeSort(std::vector<int> &data, int left, int right){
    if(left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(data, left, mid);
    mergeSort(data, mid + 1, right);
    merge(data, left, mid, right);
}

int main(){
    std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(data, 0, data.size() - 1);
    
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

3. 快速排序（QuickSort）

快速排序是一種高效的排序算法，平均時間復雜度為O(n log n)。通過選擇合適的樞軸（pivot）可以優化性能。

示例代碼

#include <iostream>
#include <vector>

int partition(std::vector<int> &data, int low, int high){
    int pivot = data[high]; // 選擇最后一個元素作為樞軸
    int i = low - 1;
    
    for(int j = low; j < high; ++j){
        if(data[j] <= pivot){
            i++;
            std::swap(data[i], data[j]);
        }
    }
    std::swap(data[i + 1], data[high]);
    return i + 1;
}

void quickSort(std::vector<int> &data, int low, int high){
    if(low < high){
        int pi = partition(data, low, high);
        quickSort(data, low, pi - 1);
        quickSort(data, pi + 1, high);
    }
}

int main(){
    std::vector<int> data = {10, 7, 8, 9, 1, 5};
    quickSort(data, 0, data.size() - 1);
    
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

4. 堆排序（Heap Sort）

堆排序利用堆這種數據結構進行排序，時間復雜度為O(n log n)，且不需要額外的空間。

示例代碼

#include <iostream>
#include <vector>

void heapify(std::vector<int> &data, int n, int i){
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if(left < n && data[left] > data[largest]){
        largest = left;
    }
    
    if(right < n && data[right] > data[largest]){
        largest = right;
    }
    
    if(largest != i){
        std::swap(data[i], data[largest]);
        heapify(data, n, largest);
    }
}

void heapSort(std::vector<int> &data){
    int n = data.size();
    
    // 構建最大堆
    for(int i = n / 2 - 1; i >= 0; --i){
        heapify(data, n, i);
    }
    
    // 一個個從堆中取出元素
    for(int i = n - 1; i >= 0; --i){
        std::swap(data[0], data[i]);
        heapify(data, i, 0);
    }
}

int main(){
    std::vector<int> data = {12, 11, 13, 5, 6, 7};
    heapSort(data);
    
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

5. 基數排序（Radix Sort）

基數排序是一種非比較型整數排序算法，適用于整數排序，時間復雜度為O(nk)，其中k是數字的位數。

示例代碼

#include <iostream>
#include <vector>
#include <algorithm>

// 獲取數字的第d位數字
int getDigit(int num, int d){
    int power = 1;
    for(int i = 0; i < d; ++i) power *= 10;
    return (num / power) % 10;
}

void radixSort(std::vector<int> &data){
    if(data.empty()) return;
    
    // 找到最大數以確定位數
    int maxNum = *std::max_element(data.begin(), data.end());
    int digits = 0;
    while(maxNum > 0){
        maxNum /= 10;
        digits++;
    }
    
    std::vector<int> output(data.size());
    std::vector<int> count(10, 0);
    
    int exp = 1;
    for(int d = 0; d < digits; ++d){
        // 清空計數數組
        std::fill(count.begin(), count.end(), 0);
        
        // 統計每個桶中的元素個數
        for(auto num : data){
            int digit = getDigit(num, d);
            count[digit]++;
        }
        
        // 計算每個桶的結束位置
        for(int i = 1; i < 10; ++i){
            count[i] += count[i - 1];
        }
        
        // 將元素放入輸出數組中
        for(int i = data.size() - 1; i >= 0; --i){
            int digit = getDigit(data[i], d);
            output[count[digit] - 1] = data[i];
            count[digit]--;
        }
        
        // 將輸出數組復制回原數組
        data = output;
    }
}

int main(){
    std::vector<int> data = {170, 45, 75, 90, 802, 66, 2, 24, 6};
    radixSort(data);
    
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

6. 并行排序

對于大規模數據，可以利用多線程或并行計算庫（如OpenMP或C++17的并行算法）來加速排序過程。

使用 C++17 并行算法示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>

int main(){
    std::vector<int> data = {5, 2, 9, 1, 5, 6};
    
    // 使用并行排序
    std::sort(std::execution::par, data.begin(), data.end());
    
    for(const auto &num : data){
        std::cout << num << " ";
    }
    return 0;
}

注意：使用并行算法需要確保編譯器支持C++17及以上標準，并且在編譯時啟用相應的標志，例如使用 -std=c++17。

總結

在Linux環境下使用C++實現高效排序算法時，推薦優先使用標準庫中的 std::sort，因為它經過高度優化，適用于大多數場景。如果需要特定的排序特性（如穩定性或特定數據類型的排序），可以考慮實現歸并排序、快速排序或堆排序等經典算法。對于大規模數據，可以探索并行排序以利用多核處理器的優勢。

希望以上內容對你有所幫助！