冒泡排序

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool flag = false; // 优化：无交换则提前退出
        for (int j = 0; j < n-i-1; j++) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

选择排序

void selectionSort(int a[], int n) {
   for (int i = 0; i < n; i++) {
       int minPos = i;
       for (int j = i+1; j < n; j++) {
           if (a[j] < a[minPos]) minPos = j;
       }
       swap(a[i], a[minPos]);
   }
}

排序

void insertionSort(int a[], int n) {
   for (int i = 1; i < n; 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;
   }
}

希尔排序

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j;
            for (j = i; j >= gap && a[j - gap] > key; j -= gap) {
                a[j] = a[j - gap];
            }
            a[j] = key;
        }
    }
}

归并排序

void merge(int a[], int l, int mid, int r) {
    int temp[MAXN];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    for (i = 0; i < k; i++) a[l + i] = temp[i];
}
void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

快速排序

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        a[i] = a[j];
        while (i < j && a[i] <= pivot) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
}

堆排序

void heapify(int a[], int n, int i) {
    int largest = i;
    int left = 2*i+1;
    int right = 2*i+2;
    if (left < n && a[left] > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}
void heapSort(int a[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(a, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

计数排序

void countingSort(int a[], int n, int maxVal) {
    int* cnt = new int[maxVal + 1](); // 动态分配
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    int k = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (cnt[i] > 0) {
            a[k++] = i;
            cnt[i]--;
        }
    }
    delete[] cnt;
}

桶排

void bucketSort(int a[], int n, int maxVal) {
    int bucketSize = 10; // 桶的数量，可调整
    vector<int>* buckets = new vector<int>[bucketSize];
    // 分配元素到桶
    for (int i = 0; i < n; i++) {
        int idx = (a[i] * bucketSize) / (maxVal + 1);
        buckets[idx].push_back(a[i]);
    }
    // 桶内排序（用插入排序）
    for (int i = 0; i < bucketSize; i++) {
        insertionSort(buckets[i].data(), buckets[i].size());
    }
    // 合并桶
    int k = 0;
    for (int i = 0; i < bucketSize; i++) {
        for (int num : buckets[i]) a[k++] = num;
    }
    delete[] buckets;
}

基数排序

void radixSort(int a[], int n) {
    int maxVal = *max_element(a, a + n);
    // 按每一位排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> output(n);
        int cnt[10] = {0};
        // 统计每个数字的出现次数
        for (int i = 0; i < n; i++) cnt[(a[i]/exp)%10]++;
        // 计算位置
        for (int i = 1; i < 10; i++) cnt[i] += cnt[i-1];
        // 反向填充，保证稳定性
        for (int i = n-1; i >= 0; i--) {
            int digit = (a[i]/exp) % 10;
            output[cnt[digit] - 1] = a[i];
            cnt[digit]--;
        }
        // 复制回原数组
        for (int i = 0; i < n; i++) a[i] = output[i];
    }
}