怎么用C++實現十大排序算法

# 怎么用C++實現十大排序算法

排序算法是計算機科學中最基礎的算法之一，本文將通過C++代碼示例詳細講解十大經典排序算法的實現原理，包括：
- 冒泡排序
- 選擇排序
- 插入排序
- 希爾排序
- 歸并排序
- 快速排序
- 堆排序
- 計數排序
- 桶排序
- 基數排序

## 1. 冒泡排序（Bubble Sort）

### 基本思想
通過重復遍歷待排序序列，比較相鄰元素并交換位置，使較大元素逐漸"浮"到右側。

### C++實現
```cpp
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前終止優化
    }
}

復雜度分析

• 時間復雜度：O(n2)（最壞和平均），O(n)（最好，已排序情況）
• 空間復雜度：O(1)
• 穩定排序

2. 選擇排序（Selection Sort）

基本思想

每次從未排序部分選擇最?。ɑ蜃畲螅┰?，放到已排序部分的末尾。

C++實現

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

復雜度分析

• 時間復雜度：O(n2)
• 空間復雜度：O(1)
• 不穩定排序

3. 插入排序（Insertion Sort）

基本思想

將未排序元素逐個插入到已排序部分的正確位置。

C++實現

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

復雜度分析

• 時間復雜度：O(n2)（最壞和平均），O(n)（最好）
• 空間復雜度：O(1)
• 穩定排序

4. 希爾排序（Shell Sort）

基本思想

插入排序的改進版，通過將原始列表分成多個子序列來提高效率。

C++實現

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
                arr[j] = arr[j-gap];
            }
            arr[j] = temp;
        }
    }
}

復雜度分析

• 時間復雜度：O(n log n) 到 O(n2)
• 空間復雜度：O(1)
• 不穩定排序

5. 歸并排序（Merge Sort）

基本思想

分治法的典型應用，將數組分成兩半分別排序，然后合并結果。

C++實現

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp(r - l + 1);
    int i = l, j = m + 1, k = 0;
    
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    
    for (int p = 0; p < k; p++) {
        arr[l + p] = temp[p];
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

復雜度分析

• 時間復雜度：O(n log n)
• 空間復雜度：O(n)
• 穩定排序

6. 快速排序（Quick Sort）

基本思想

分治法，選擇一個基準元素將數組分成兩部分，左邊小于基準，右邊大于基準。

C++實現

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

復雜度分析

• 時間復雜度：O(n log n)（平均），O(n2)（最壞）
• 空間復雜度：O(log n)
• 不穩定排序

7. 堆排序（Heap Sort）

基本思想

利用堆這種數據結構設計的排序算法，分為建堆和排序兩個階段。

C++實現

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

void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // 構建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // 逐個提取元素
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

復雜度分析

• 時間復雜度：O(n log n)
• 空間復雜度：O(1)
• 不穩定排序

8. 計數排序（Counting Sort）

基本思想

適用于整數排序，通過統計元素出現次數來實現排序。

C++實現

void countingSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    int min_val = *min_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;
    
    vector<int> count(range), output(arr.size());
    
    for (int num : arr) count[num - min_val]++;
    
    for (int i = 1; i < range; i++) 
        count[i] += count[i - 1];
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }
    
    arr = output;
}

復雜度分析

• 時間復雜度：O(n + k)（k為數值范圍）
• 空間復雜度：O(n + k)
• 穩定排序

9. 桶排序（Bucket Sort）

基本思想

將元素分到有限數量的桶里，每個桶再分別排序。

C++實現

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);
    
    // 將元素分配到桶中
    for (float num : arr) {
        int bucket_idx = n * num;
        buckets[bucket_idx].push_back(num);
    }
    
    // 對每個桶排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }
    
    // 合并桶
    int index = 0;
    for (auto& bucket : buckets) {
        for (float num : bucket) {
            arr[index++] = num;
        }
    }
}

復雜度分析

• 時間復雜度：O(n + k)（k為桶的數量）
• 空間復雜度：O(n + k)
• 穩定排序

10. 基數排序（Radix Sort）

基本思想

按照低位先排序，然后收集；再按照高位排序，再收集；依次類推。

C++實現

void countingSortForRadix(vector<int>& arr, int exp) {
    vector<int> output(arr.size());
    vector<int> count(10, 0);
    
    for (int num : arr) 
        count[(num / exp) % 10]++;
    
    for (int i = 1; i < 10; i++) 
        count[i] += count[i - 1];
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    arr = output;
}

void radixSort(vector<int>& arr) {
    int max_val = *max_element(arr.begin(), arr.end());
    
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        countingSortForRadix(arr, exp);
    }
}

復雜度分析

• 時間復雜度：O(nk)（k為最大數字的位數）
• 空間復雜度：O(n + k)
• 穩定排序

總結比較

在實際應用中，應根據數據特點選擇合適的排序算法： - 小規模數據：插入排序 - 大規模隨機數據：快速排序 - 需要穩定性：歸并排序 - 整數排序：計數/基數排序 - 內存受限：堆排序

希望本文能幫助你理解并掌握這十大排序算法的C++實現！ “`