排序算法

排序算法是计算机科学中用于将一组数据按照特定顺序进行排列的算法。本节不讨论 C++ STL中的排序算法，而是介绍一些基本的排序算法及其实现。

对于当前的排序算法, 主要分为两大类: 1. 比较排序算法 (Comparison-based Sorting Algorithms): 这些算法通过比较元素之间的大小关系来决定它们的顺序。常见的比较排序算法包括快速排序 (Quick Sort)、归并排序 (Merge Sort)、堆排序 (Heap Sort) 、冒泡排序 (Bubble Sort) 和插入排序 (Insertion Sort) 等。 2. 非比较排序算法 (Non-comparison-based Sorting Algorithms): 这些算法不直接比较元素的大小，而是利用元素的特定属性进行排序。常见的非比较排序算法包括计数排序 (Counting Sort)、基数排序 (Radix Sort) 和桶排序 (Bucket Sort) 等。

插入排序 (Insertion Sort)

插入排序是一种简单直观的排序算法，适用于小规模数据集。它的基本思想是将数组分为已排序和未排序两部分，然后逐步将未排序部分的元素插入到已排序部分的正确位置。

void InsertSorting(vector<int>& nums){
  if(nums.size()<=1) return;  // 如果向量为空或只有一个元素，则它已经是有序的

  // 从第二个元素（索引为 1）开始遍历
  // 我们假设第一个元素（索引为 0）构成了初始的已排序子序列
  for(int i=1;i<nums.size();i++){
    // 1. 选定当前需要插入的元素并保存起来
    //    `key` 是我们要在 `nums[0...i-1]` 这个已排序序列中找到合适位置的元素
    int key = nums[i];

    // 2. 在已排序序列中从后向前查找, `j` 指向已排序序列的最后一个元素
    int j = i-1;

    // 3. 移动元素
    //    循环条件：
    //    a. `j >= 0`：确保我们没有越过数组的起始边界
    //    b. `nums[j] > key`：如果当前已排序序列中的元素 `nums[j]` 大于 `key`
    //
    //    操作：
    //    将 `nums[j]` 向右移动一位到 `nums[j+1]`
    //    然后 `j` 向前移动一位，继续与 `key` 比较
    while(j>=0 && nums[j]>key){
      nums[j+1] = nums[j];   // 元素向右移动
      j--;            // 索引向前移动
    }

    // 4. 插入元素
    //    当循环停止时，`j` 的位置有两种可能：
    //    a. `j = -1`：意味着 `key` 比所有已排序的元素都小，应放在最前面（索引 0）。
    //    b. `nums[j] <= key`：意味着 `key` 应该插入到 `nums[j]` 的后面。
    //    
    //    在这两种情况下，`j + 1` 都是 `key` 应该在的正确位置。
    nums[j + 1] = key;
  }
}

它的特点包括: - 时间复杂度：平均和最坏情况下为 O(n^2)，最好情况下为 O(n)。 - 空间复杂度：O(1)，属于原地排序算法。 - 稳定性：插入排序是稳定的排序算法。 - 适用场景：适用于小规模数据集或部分有序的数据集。

冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历要排序的数列，比较相邻元素并交换它们的位置，使得较大的元素逐渐“冒泡”到数列的末端。

void BubbleSorting(vector<int>& nums){
  int n = nums.size();
  if(n<=1) return; // 如果向量为空或只有一个元素，则它已经是有序的

  // 1. 外层循环：控制总共需要进行的“趟数”
  //    对于 n 个元素，最多需要 n-1 趟。
  //    i 表示已经有多少个元素被“冒泡”到了它们在数组末尾的最终位置。
  //    i 不到 n-1 是因为最后一个元素在前面的趟数中已经被排序好了。
  for (int i = 0; i < n - 1; ++i) {
      
      // 2. 优化标志：
      //    设置一个标志 `swapped`，用于检查在这一趟中是否发生了交换。
      //    如果在一整趟内层循环中都没有发生交换，说明数组已经有序，
      //    可以提前终止排序。
      bool swapped = false;

      // 3. 内层循环：执行一趟冒泡
      //    j 遍历当前未排序的部分。
      //    比较的范围是 nums[0] 到 nums[n - 1 - i]。
      //    "- i" 是因为数组末尾的 i 个元素在之前的趟数中已经被确定是最大的，无需再比较。
      //    "- 1" 是因为我们要比较 j 和 j+1。
      for (int j = 0; j < n - 1 - i; ++j) {
          
          // 4. 比较和交换
          //    如果前一个元素 (nums[j]) 大于后一个元素 (nums[j+1])
          if (nums[j] > nums[j + 1]) {
              
              // 执行交换，将较大的元素向右“冒泡”
              std::swap(nums[j], nums[j + 1]);
              
              // 标记在这一趟中发生了交换
              swapped = true;
          }
      }

      // 5. 检查优化标志
      //    如果这一趟 (整个内层 j 循环) 没有任何交换发生
      if (!swapped) {
          // 说明数组已经完全有序，跳出外层循环
          break;
      }
  }
}

它的特点包括: - 时间复杂度：平均和最坏情况下为 O(n^2)，最好情况下为 O(n)。 - 空间复杂度：O(1)，属于原地排序算法。 - 稳定性：冒泡排序是稳定的排序算法。 - 适用场景：适用于小规模数据集，但通常不如插入排序高效。

归并排序 (Merge Sort)

归并排序是一种分治法的排序算法，其基本思想是将数组递归地分成两半，分别对这两半进行排序，然后将排序好的两半合并在一起。

```cpp
#include <vector>
using namespace std;

class Solution {
    // 合并两个有序子数组 nums[left...mid] 和 nums[mid+1...right]
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp(right - left + 1); // 临时数组存放合并结果

        int i = left, j = mid + 1, k = 0;  // i 和 j 分别指向两个子数组的起始位置，k 指向 temp 的起始位置

        // 比较两个子数组的元素，按顺序放入 temp
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        }
        // 如果左半部分还有剩余，全部拷贝到 temp
        while (i <= mid) temp[k++] = nums[i++];
        // 如果右半部分还有剩余，全部拷贝到 temp
        while (j <= right) temp[k++] = nums[j++];
        // 将合并后的结果拷贝回原数组
        for (int t = 0; t < temp.size(); ++t) nums[left + t] = temp[t];     // 这里的 left + t 保证了正确的索引位置, 因为在本次合并中, 我们处理的是 nums 的子区间[left, right]
    }

    // 归并排序递归函数，将 nums[left...right] 排序
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return; // 递归终止条件
        int mid = left + (right - left) / 2;  

        mergeSort(nums, left, mid);      // 排序左半部分
        mergeSort(nums, mid + 1, right); // 排序右半部分
        merge(nums, left, mid, right);   // 合并两个有序子数组
    }
public:
    // 对整个数组进行归并排序
    void MergeSort(vector<int>& nums) {
        if (nums.size() <= 1) return;
        mergeSort(nums, 0, nums.size() - 1);
    }
};

快速排序 (Quick Sort)

快速排序是一种高效的排序算法，采用分治法的思想。基本步骤如下： 1. 选择基准 (Pivot)：从数组中挑选一个元素，称为“基准”或“枢轴”(pivot)。 2. 分区 (Partition)：重新排列数组，将所有小于基准的元素移动到基准的左边，所有大于基准的元素移动到基准的右边。在此操作之后，基准元素就位于其最终的排序位置。 3. 递归 (Recurse)：递归地对基准左边的子数组和基准右边的子数组应用上述步骤。

// 快速排序的递归辅助函数
void quickSortRecursive(std::vector<int>& nums, int low, int high) {
    
    // 递归的基线条件 (Base Case):
    // 如果子数组有 0 或 1 个元素 (low >= high)，则它已经有序。
    if (low < high) {  // 开始 partitioning 
        
        // 1. 选取基准 (Pivot)
        //    我们选择这个子数组的最后一个元素 (nums[high]) 作为 pivot。
        int pivotValue = nums[high];

        // 2. 初始化 "小于" 区域的边界
        //    `i` 用来追踪 "小于" pivot 区域的最后一个元素的索引。
        //    初始时，这个区域是空的，所以 i 设置为 low - 1。
        int i = low - 1;

        // 3. 遍历子数组 (从 low 到 high-1)
        //    `j` 是当前正在检查的元素。
        for (int j = low; j < high; ++j) {
            
            // 4. 比较当前元素与 pivot
            //    如果当前元素 nums[j] 小于 pivotValue
            if (nums[j] < pivotValue) {
                
                // 5. 扩展 "小于" 区域
                //    将 `i` 向右移动一位，并与 `nums[j]` 交换。
                //    这确保了 [low...i] 范围内的所有元素都小于 pivot。
                i++;
                std::swap(nums[i], nums[j]);
            }
        }

        // 6. 将 pivot 放到正确的位置
        //    循环结束后，[low...i] 都是小于 pivot 的。
        //    [i+1...high-1] 都是大于等于 pivot 的。
        //    因此，pivot (它在 nums[high]) 应该在的位置是 i + 1。
        std::swap(nums[i + 1], nums[high]);

        // 7. 获取 pivot 的最终索引
        //    这个索引 'pi' 将用于分割下一次递归。
        int pi = i + 1;
        
        // 8. 递归排序左半部分
        //    对 pivot 左边的子数组 (从 low 到 pi - 1) 进行快速排序。
        quickSortRecursive(nums, low, pi - 1);

        // 9. 递归排序右半部分
        //    对 pivot 右边的子数组 (从 pi + 1 到 high) 进行快速排序。
        quickSortRecursive(nums, pi + 1, high);
    }
}

void QuickSort(std::vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return;
    
    // 调用递归辅助函数，对整个数组 (索引 0 到 n-1) 进行排序
    quickSortRecursive(nums, 0, n - 1);
}

它的特点包括: - 时间复杂度：平均情况下为 O(n log n)，最坏情况下为 O(n^2)（当数组已经有序或接近有序时, 每次选择的基准都是最大或最小元素, 只能将一个元素分割出去）。 - 空间复杂度：平均情况下为 O(log n)，主要用于递归调用栈空间。最坏情况下为 O(n), 即每次分区都只能分出一个元素, 退化为链表. - 不稳定性：快速排序通常是不稳定的排序算法。 - 适用场景：适用于大规模数据集，是实际应用中非常常用的排序算法。

优化: 为了避免最坏情况，可以采用随机选择基准或三数取中法来选择基准元素。

快速选择

快速选择 (Quickselect) 是一种用于在无序数组中查找第 k 大/小元素的高效算法。它基于快速排序的分区思想，但只递归处理包含第 k 小元素的那一部分数组，从而提高效率。

例如, 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。(LC 215)

int partition(vector<int>& nums, int target, int left, int right){
    if(left>right) return -1;
    int pivot = nums[right];
    int i=left;

    for(int j=left;j<right;j++){
        if(nums[j]<pivot){
            swap(nums[j], nums[i]);
            i++;
        }
    }
    swap(nums[i], nums[right]);
    if(i==target) return nums[i];
    else if(i>target){
        return partition(nums, target, left, i-1);
    }else{
        return partition(nums, target, i+1, right);
    }
}

int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    int target = n-k;
    return partition(nums, target, 0, n-1);
}

这里的partition函数与快速排序中的类似，但为了处理大量重复元素的情况，做了一些调整，使得与基准相同的元素均匀分布，避免退化。 而findKthLargest函数则只关注包含第 k 大元素的那一半子数组，其平均时间复杂度为 O(n)。

<algorithms>标准库中的 std::nth_element 函数就是基于快速选择算法实现的，可以用来高效地找到第 k 大/小元素。 例如, nth_element(v.begin(), v.begin() + (k - 1), v.end()); 会将第 k 小的元素放到正确的位置上, 并且保证该位置左边的元素都不大于它, 右边的元素都不小于它.

桶排序

桶排序 (Bucket Sort) 是一种非比较排序算法，适用于均匀分布的数据。它的基本思想是将数据分布到多个“桶”中，然后对每个桶内的数据进行排序，最后再将所有桶中的数据合并起来。

void bucketSort(std::vector<int>& nums, int bucketSize) {
    if (nums.empty()) return;

    // 1. 找到数据的最小值和最大值
    int minValue = *std::min_element(nums.begin(), nums.end());
    int maxValue = *std::max_element(nums.begin(), nums.end());

    // 2. 计算桶的数量
    int bucketCount = (maxValue - minValue) / bucketSize + 1;
    std::vector<std::vector<int>> buckets(bucketCount);

    // 3. 将元素分配到各个桶中
    for (int num : nums) {
        int bucketIndex = (num - minValue) / bucketSize;
        buckets[bucketIndex].push_back(num);
    }

    // 4. 对每个桶内的元素进行排序（这里使用插入排序）
    nums.clear();
    for (auto& bucket : buckets) {
        InsertSorting(bucket);  // 使用前面定义的插入排序函数
        nums.insert(nums.end(), bucket.begin(), bucket.end());
    }
}

其特点包括: - 时间复杂度：平均情况下为 O(n + k)，其中 n 是元素数量，k 是桶的数量。最坏情况下为 O(n^2)（当所有元素都落入同一个桶时）。 - 因为每个桶内使用插入排序, 有k个桶, 每个桶平均有n/k个元素, 所以每个桶排序的时间复杂度为O((n/k)^2), 总共k个桶, 所以总时间复杂度为O(k*(n/k)^2) = O(n^2/k). 当k接近n时, 时间复杂度接近O(n). - 空间复杂度：O(n + k)，需要额外的空间来存储桶。 - 稳定性：桶排序是稳定的排序算法（取决于桶内排序算法）。 - 适用场景：适用于均匀分布的数据集，尤其是当数据范围较大且元素数量较少时。

堆排序

堆排序 (Heap Sort) 是一种基于堆数据结构的比较排序算法。它的基本思想是将数组构建成一个最大堆，然后不断地将堆顶元素（最大值）与数组的最后一个元素交换，并缩小堆的范围，重复此过程直到堆为空。

void heapify(std::vector<int>& nums, int n, int i) {
    int largest = i;       // 初始化最大值为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点比根节点大
    if (left < n && nums[left] > nums[largest])
        largest = left;

    // 如果右子节点比当前最大值还大
    if (right < n && nums[right] > nums[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        std::swap(nums[i], nums[largest]); // 交换

        // 递归地堆化受影响的子树
        heapify(nums, n, largest);
    }
}
void heapSort(std::vector<int>& nums) {
    int n = nums.size();

    // 1. 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);

    // 2. 一个个从堆中取出元素
    for (int i = n - 1; i >= 0; i--) {
        std::swap(nums[0], nums[i]); // 将当前最大值移到数组末尾
        heapify(nums, i, 0);         // 重新堆化剩余元素
    }
}

其特点包括: - 时间复杂度：平均和最坏情况下均为 O(n log n)。 - 空间复杂度：O(1)，属于原地排序算法。 - 不稳定性：堆排序通常是不稳定的排序算法。 - 适用场景：适用于大规模数据集，尤其是在内存空间有限的情况下。

但是, 堆排序在实际应用中通常不如快速排序高效, 因为堆排序的内存访问模式不如快速排序友好, 导致缓存命中率较低; 而且堆排序的常数因子较大 快速排序：分区操作主要是顺序访问内存，具有良好的缓存局部性. 而堆排序：堆的操作经常需要跳跃式访问内存（父子节点可能相距较远），缓存命中率较低。 另一方面, heapify 过程中需要多次比较和条件判断，这会增加分支预测失败的风险，进一步影响流水线性能。而快速排序分区过程中的比较操作相对简单，对CPU的分支预测器友好。