常见的排序算法

冒泡排序，通过不停交换相邻的元素进行排序，实现稳定但效率低下。时间复杂度为O(n^2)，空间复杂度为O(1)。

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

选择排序(简单)，通过选择剩余元素中最大或最小的元素放在已排序元素末尾，效率低且不稳定。时间复杂度为O(n^2)，空间复杂度为O(1)。

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

插入排序，将未排序的某个元素插入到已排序元素的合适位置，对于小规模数据或者比较有序的数据，效率较高。时间复杂度为O(n^2)，空间复杂度为O(1)。

vector insertionSort(vector 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;
    }
    return arr;
}

快速排序，先选择一个基准数，这里采用单指针遍历元素，分别将小于和大于基准数的元素分别两个部分，用递归将两个部分的元素继续拆分，直到各个部分的元素有序，再合并起来即可，实际应用中效率很高。时间复杂度为O(nlogn) 平均情况下，最坏情况 O(n2)，空间复杂度为O(logn)。

//分区函数
int partition(vector& 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;//返回基准数pivot最终位置
}
//递归函数
vector quickSort(vector& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high); 
    }
    return arr;
}

归并排序，采用分治法将数组分割，递归排序后合并。排序比较稳定，适用于大规模的数据排序。时间复杂度为O(nlogn) ，O(n)。

// 归并两个有序数组
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++];


    // 复制回原数组
    for (k = 0; k < temp.size(); k++) arr[left + k] = temp[k];
}
// 归并排序
vector mergeSort(vector& arr, int left, int right) {
    if (left >= right) return arr; // 终止条件
    int mid = left + (right - left) / 2;


    mergeSort(arr, left, mid);     // 递归左半部分
    mergeSort(arr, mid + 1, right); // 递归右半部分
    merge(arr, left, mid, right);  // 归并两个部分
    return arr;
}

堆排序，利用完全二叉树构建堆这种数据结构，保证父节点大于子节点，构建大顶堆，不断将最大值(根节点)取出，但不是稳定排序。适用于要求时间复杂度较优且对空间要求低。时间复杂度为O(nlogn)，空间复杂度为O(1)。

//建堆函数
void heapify(vector& 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);//递归，确保交换元素后每个子树始终是大顶堆
    }
}
vector 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);//每次交换后再重新将剩余元素重新构建堆
    }
    return arr;
}

希尔排序，可以看出一种改进版的插入排序。通过间距分组来提高效率，这里我们用每个分组大小减半，对每个分组再进行“插入排序”，不算稳定，适用于中等规模数据。平均时间复杂度为O(n^1.5)左右，和分组的间距大小有一定关系，空间复杂度为O(1)。

vector shellSort(vector& arr) {
    int n = arr.size();
    // 逐步缩小 gap，初始 gap = n/2，之后 gap /= 2
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 从 gap 开始，逐个对比并插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 当前待插入的元素
            int j = i;
            // 对间隔为 gap 的子序列进行插入排序
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];  // 向右移动元素
                j -= gap;
            }
            arr[j] = temp;  // 插入正确位置
        }
    }
    return arr;
}

计数排序，统计每个元素出现的次数，然后按顺序重构有序数组。。适用于数据范围有限的排序问题，非比较排序。时间复杂度为O(n+k)，空间复杂度为O(k),n是所有元素个数，k是数据范围。

vector countingSort(vector& arr) {
    int n = arr.size();
    if (n == 0) return arr;  // 处理空数组
    // 找到数组中的最大值和最小值
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    // 创建计数数组 count，大小为 (maxVal - minVal + 1)
    vector count(maxVal - minVal + 1, 0);
    // 统计每个元素出现的次数
    for (int num : arr) {
        count[num - minVal]++;
    }
    // 存储排序后的数组
    vector sortedArr;
    // 遍历计数数组，根据计数结果填充排序数组
    for (int i = 0; i < count.size(); ++i) {
        while (count[i]--) {  // 只要 count[i] 不为 0，就添加对应的元素
            sortedArr.push_back(i + minVal);
        }
    }
    return sortedArr;
}

桶排序，先设定初始桶大小，根据待排序元素范围划分桶的数量，划分公式为(元素最大值-元素最小值)/桶大小+1，这样能保证每个桶的范围都统一，再将相应范围的元素放入对应的桶，最后对每个桶内元素排序即可，适用于数据分配均匀的场景。时间复杂度为O(n + k)，空间复杂度为O(n)，其中 n 是元素数量，k 是桶的数量。

vector bucketSort(vector& arr, int bucketSize) {//bucketSize是初定桶大小
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int bucketCount = (maxVal - minVal) / bucketSize + 1;  // 计算桶的数量
    vector> buckets(bucketCount);  // 创建桶


    if (arr.empty()) return arr;//处理空数组
    if (minVal == maxVal) return arr; // 所有元素相同，直接返回


    // 将元素放入桶
    for (int num : arr) {
        int index = (num - minVal) / bucketSize;  // 计算桶索引
        buckets[index].push_back(num);
    }
    // 对每个桶内部进行排序
    vector sortedArr;
    for (auto& bucket : buckets) {
        Sort(bucket);  // 这里用任意排序方式
        sortedArr.insert(sortedArr.end(), bucket.begin(), bucket.end());
    }
    return sortedAr;
 }

基数排序，它按照位数（从最低位到最高位或反向）依次对数据进行稳定排序，这里采用从低位到高位。适用于数据量大且数据具有较少的位数时，效率较高。时间复杂度为O(nk)，空间复杂度为O(n+k),其中 n 是元素数量，k 是数字位数。

ector radixSort(vector& arr) {
    if (arr.empty()) return arr; // 处理空数组
    int maxVal = *max_element(arr.begin(), arr.end()); // 直接获取最大值


    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector count(10, 0);
        vector output(arr.size());


        // 统计当前位数上的数字出现次数
        for (int i = 0; i < arr.size(); ++i) {
            count[(arr[i] / 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;
    }
    return arr;
}

以下是总结：