怎么用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(n²)（最坏和平均），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(n²)
• 空间复杂度：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(n²)（最坏和平均），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(n²)
• 空间复杂度：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(n²)（最坏）
• 空间复杂度：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)
• 稳定排序

总结比较

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n log n)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	稳定
桶排序	O(n + k)	O(n²)	O(n + k)	稳定
基数排序	O(nk)	O(nk)	O(n + k)	稳定

在实际应用中，应根据数据特点选择合适的排序算法： - 小规模数据：插入排序 - 大规模随机数据：快速排序 - 需要稳定性：归并排序 - 整数排序：计数/基数排序 - 内存受限：堆排序

希望本文能帮助你理解并掌握这十大排序算法的C++实现！ “`