C++实现经典排序算法

本文将探讨七种常用的排序算法，并通过表格形式展示它们的性能指标。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序列表，比较相邻元素并交换顺序不对的元素。这个过程会使得每一趟遍历后最大的元素逐渐移动到列表末尾。如果在某一轮遍历中没有发生任何交换，则说明列表已经有序，可以提前结束排序。

// O(n²) 冒泡排序 (稳定排序)
void bubbleSort(vector& a) {
    int n = a.size();
    for (int i = 0; i         bool swapped = false;
        for (int j = 0; j             if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

2. 选择排序

选择排序每次从未排序部分中选出最小的元素，并将其与未排序部分的第一个元素交换。这样，经过若干轮操作后，整个数组会被排好序。

// O(n²) 选择排序 (不稳定排序)
void selectionSort(vector& a) {
    int n = a.size();
    for (int i = 0; i         int minIndex = i;
        for (int j = i + 1; j             if (a[j]                 minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(a[i], a[minIndex]);
        }
    }
}

3. 插入排序

插入排序类似于打牌时整理手牌的过程，即逐步将新元素插入到已排序序列中的正确位置。该算法适用于小规模或接近有序的数据集。

// O(n²) 插入排序 (稳定排序)
void insertionSort(vector& a) {
    int n = a.size();
    for (int i = 1; i         int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

4. 希尔排序

希尔排序是插入排序的一种改进版本，它通过设定增量间隔对数组进行分组排序，从而加速排序过程。随着增量逐渐减小，最终达到完全有序的状态。

// O(nlogn) 至 O(n²) 希尔排序 (不稳定排序)
void shellSort(vector& a) {
    int n = a.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i             int temp = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > temp; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = temp;
        }
    }
}

5. 堆排序

堆排序利用了二叉堆数据结构来实现高效的排序。首先构建一个最大堆，然后反复从堆顶取出最大值并重新调整堆，直到所有元素都被处理完毕。

#include 
using namespace std;

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

void heapSort(vector& 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);
    }
}

6. 归并排序

归并排序采用分治法思想，将数组递归地分为两个子数组分别排序，再合并成一个有序数组。其特点是稳定性和较低的空间复杂度。

#include 
using namespace std;

void merge(vector& arr, int left, int mid, int right) {
    vector temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    copy(temp.begin(), temp.end(), arr.begin() + left);
}

void mergeSort(vector& arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

7. 快速排序

快速排序也是一种基于分治策略的高效排序算法。它通过选择一个基准值（pivot），将数组划分为两部分，一部分小于等于基准值，另一部分大于基准值，再递归地对这两部分进行排序。

#include 
using namespace std;

void quickSort(vector& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left];
    int i = left, j = right;
    while (i         while (i = pivot) --j;
        arr[i] = arr[j];
        while (i         arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}