排序算法——详解

排序算法

（冒泡、选择、插入、快排、归并、堆排、计数、桶、基数）

稳定性 (Stability): 如果排序算法能保证，当待排序序列中存在值相等的元素时，排序后这些元素的相对次序保持不变，那么该算法就是稳定的。 例如：如果原始序列中有两个相同的元素 A 和 B (A在B前面)，排序后 A 仍然在 B 的前面，则该排序算法是稳定的。

1. 冒泡排序 (Bubble Sort)

• 思想: 重复遍历待排序的列表，比较相邻的两个元素，如果顺序错误就交换它们，直到没有元素可以交换，即排序完成。每次遍历都会将最大（或最小）的元素“冒泡”到其最终位置。

• C++ 示例 (伪代码):

  void bubbleSort(int arr[], int n) {
      for (int i = 0; i < n - 1; ++i) {
          bool swapped = false; // 优化：如果一趟没有发生交换，说明已经有序
          for (int j = 0; j < n - 1 - i; ++j) {
              if (arr[j] > arr[j+1]) {
                  std::swap(arr[j], arr[j+1]);
                  swapped = true;
              }
          }
          if (!swapped) break;
      }
  }
  

2. 选择排序 (Selection Sort)

• 思想: 每次遍历（或扫描）整个待排序的无序部分，找到其中最小（或最大）的元素，然后将其放到无序部分的起始位置。重复这个过程直到所有元素都排好序。

• C++ 示例 (伪代码):

  void selectionSort(int arr[], int n) {
      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;
              }
          }
          if (min_idx != i) {
              std::swap(arr[i], arr[min_idx]);
          }
      }
  }
  

3. 插入排序 (Insertion Sort)

• 思想: 将一个元素插入到已经排序好的部分。从第二个元素开始，将其与前面已排序的元素进行比较，如果它比前面的元素小，就将前面的元素后移，直到找到合适的位置插入该元素。

• C++ 示例 (伪代码):

  void insertionSort(int arr[], int n) {
      for (int i = 1; i < n; ++i) {
          int key = arr[i];
          int j = i - 1;
          // 将比 key 大的元素向后移动
          while (j >= 0 && arr[j] > key) {
              arr[j+1] = arr[j];
              j--;
          }
          arr[j+1] = key; // 插入 key
      }
  }
  

4. 快速排序 (Quick Sort)

• 思想: 采用分治策略。从数组中选择一个元素作为“基准”（pivot），将数组分割成两个子数组：一个子数组的所有元素都小于基准，另一个子数组的所有元素都大于基准。然后递归地对这两个子数组进行排序。

• C++ 示例 (手写实现见下文)。

  #include <iostream>
  #include <vector>
  #include <algorithm> // For std::swap
  
  // 辅助函数：分区操作
  // 返回基准元素最终的索引
  int partition(std::vector<int>& arr, int low, int high) {
      int pivot = arr[high]; // 选择最后一个元素作为基准
      int i = (low - 1);     // 小于基准的元素区域的结束索引
  
      for (int j = low; j <= high - 1; j++) {
          // 如果当前元素小于或等于基准
          if (arr[j] <= pivot) {
              i++; // 增加小于基准的元素区域的结束索引
              std::swap(arr[i], arr[j]);
          }
      }
      std::swap(arr[i + 1], arr[high]); // 将基准元素放到正确的位置
      return (i + 1);
  }
  
  // 快速排序主函数
  void quickSort(std::vector<int>& arr, int low, int high) {
      if (low < high) {
          // pi 是分区点索引，arr[pi] 现在在正确的位置
          int pi = partition(arr, low, high);
  
          // 递归地对左右两部分进行排序
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }
  
  /*
  // 示例使用
  int main() {
      std::vector<int> arr = {10, 7, 8, 9, 1, 5};
      int n = arr.size();
      std::cout << "Original array: ";
      for (int x : arr) {
          std::cout << x << " ";
      }
      std::cout << std::endl;
  
      quickSort(arr, 0, n - 1);
  
      std::cout << "Sorted array (Quick Sort): ";
      for (int x : arr) {
          std::cout << x << " ";
      }
      std::cout << std::endl;
      return 0;
  }
  */
  

5. 归并排序 (Merge Sort)

• 思想: 采用分治策略。将待排序的序列递归地分成两半，直到每个子序列只包含一个元素（这被认为是自然有序的）。然后将这些有序的子序列两两合并，形成更大的有序序列，直到所有序列合并成一个完整的有序序列。

• C++ 示例 (手写实现见下文)。

  #include <iostream>
  #include <vector>
  #include <algorithm> // Not strictly needed for merge, but good for general use
  
  // 辅助函数：合并两个有序子数组
  void merge(std::vector<int>& arr, int left, int mid, int right) {
      int n1 = mid - left + 1;
      int n2 = right - mid;
  
      // 创建临时数组
      std::vector<int> L(n1);
      std::vector<int> R(n2);
  
      // 复制数据到临时数组 L[] 和 R[]
      for (int i = 0; i < n1; i++) {
          L[i] = arr[left + i];
      }
      for (int j = 0; j < n2; j++) {
          R[j] = arr[mid + 1 + j];
      }
  
      // 合并临时数组回到 arr[left..right]
      int i = 0; // L[] 的起始索引
      int j = 0; // R[] 的起始索引
      int k = left; // 合并后数组的起始索引
  
      while (i < n1 && j < n2) {
          if (L[i] <= R[j]) {
              arr[k] = L[i];
              i++;
          } else {
              arr[k] = R[j];
              j++;
          }
          k++;
      }
  
      // 复制 L[] 中剩余的元素 (如果有)
      while (i < n1) {
          arr[k] = L[i];
          i++;
          k++;
      }
  
      // 复制 R[] 中剩余的元素 (如果有)
      while (j < n2) {
          arr[k] = R[j];
          j++;
          k++;
      }
  }
  
  // 归并排序主函数
  void mergeSort(std::vector<int>& arr, int left, int right) {
      if (left >= right) { // 基本情况：如果只有一个或零个元素
          return;
      }
      int mid = left + (right - left) / 2; // 计算中间点，防止溢出
      mergeSort(arr, left, mid);           // 递归排序左半部分
      mergeSort(arr, mid + 1, right);      // 递归排序右半部分
      merge(arr, left, mid, right);        // 合并已排序的两半
  }
  
  /*
  // 示例使用
  int main() {
      std::vector<int> arr = {12, 11, 13, 5, 6, 7};
      int n = arr.size();
      std::cout << "Original array: ";
      for (int x : arr) {
          std::cout << x << " ";
      }
      std::cout << std::endl;
  
      mergeSort(arr, 0, n - 1);
  
      std::cout << "Sorted array (Merge Sort): ";
      for (int x : arr) {
          std::cout << x << " ";
      }
      std::cout << std::endl;
      return 0;
  }
  */
  

6. 堆排序 (Heap Sort)

• 思想: 利用堆（通常是最大堆）的数据结构。首先将待排序的序列构建成一个最大堆。然后，重复地将堆顶元素（最大值）与堆的最后一个元素交换，并缩小堆的范围，重新调整剩余元素以保持堆的性质。

• C++ 示例 (伪代码):

  void heapify(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) {
          std::swap(arr[i], arr[largest]);
          heapify(arr, n, largest); // 递归地堆化受影响的子树
      }
  }
  
  void heapSort(int arr[], int n) {
      // 构建最大堆 (从最后一个非叶子节点开始)
      for (int i = n / 2 - 1; i >= 0; i--)
          heapify(arr, n, i);
  
      // 一个个从堆顶取出元素
      for (int i = n - 1; i > 0; i--) {
          std::swap(arr[0], arr[i]); // 将当前最大元素移到数组末尾
          heapify(arr, i, 0); // 对剩余元素进行堆化
      }
  }
  

7. 计数排序 (Counting Sort)

• 思想: 非比较排序。适用于待排序元素是整数，且范围不大的情况。它统计每个数字出现的次数，然后根据统计结果将数字按顺序输出。

• C++ 示例 (伪代码):

  void countingSort(int arr[], int n) {
      int max_val = arr[0];
      for (int i = 1; i < n; ++i) {
          if (arr[i] > max_val) {
              max_val = arr[i];
          }
      }
  
      std::vector<int> count(max_val + 1, 0);
      std::vector<int> output(n);
  
      for (int i = 0; i < n; ++i) {
          count[arr[i]]++;
      }
  
      for (int i = 1; i <= max_val; ++i) {
          count[i] += count[i - 1]; // 累加计数，表示小于等于当前值的元素个数
      }
  
      // 从后向前遍历，保证稳定性
      for (int i = n - 1; i >= 0; --i) {
          output[count[arr[i]] - 1] = arr[i];
          count[arr[i]]--;
      }
  
      for (int i = 0; i < n; ++i) {
          arr[i] = output[i];
      }
  }
  

8. 桶排序 (Bucket Sort)

• 思想: 非比较排序。将待排序的元素分散到有限数量的桶中，每个桶再分别进行排序（可以使用其他排序算法，如插入排序），最后将所有桶中的元素依次取出。

• C++ 示例 (伪代码):

  void bucketSort(float arr[], int n) {
      // 创建 n 个空桶
      std::vector<std::vector<float>> buckets(n);
  
      // 将元素放入对应的桶中
      for (int i = 0; i < n; ++i) {
          int bucket_idx = n * arr[i]; // 假设元素在 [0, 1) 之间
          buckets[bucket_idx].push_back(arr[i]);
      }
  
      // 对每个桶进行排序 (可以使用插入排序或其他简单排序)
      for (int i = 0; i < n; ++i) {
          std::sort(buckets[i].begin(), buckets[i].end()); // 使用std::sort简化
      }
  
      // 将桶中的元素按顺序放回原数组
      int index = 0;
      for (int i = 0; i < n; ++i) {
          for (float val : buckets[i]) {
              arr[index++] = val;
          }
      }
  }
  

9. 基数排序 (Radix Sort)

• 思想: 非比较排序。根据数字的各个位（或基数）进行排序。从最低有效位（LSD）或最高有效位（MSD）开始，对每一位使用稳定的子排序算法（通常是计数排序）进行排序。

• C++ 示例 (伪代码，通常结合计数排序实现):

  // 辅助函数：根据指定位数对数组进行计数排序
  void countSortForRadix(int arr[], int n, int exp) {
      std::vector<int> output(n);
      std::vector<int> count(10, 0); // 0-9
  
      for (int i = 0; i < n; i++) {
          count[(arr[i] / exp) % 10]++;
      }
  
      for (int i = 1; i < 10; i++) {
          count[i] += count[i - 1];
      }
  
      for (int i = n - 1; i >= 0; i--) {
          output[count[(arr[i] / exp) % 10] - 1] = arr[i];
          count[(arr[i] / exp) % 10]--;
      }
  
      for (int i = 0; i < n; i++) {
          arr[i] = output[i];
      }
  }
  
  void radixSort(int arr[], int n) {
      int max_val = arr[0];
      for (int i = 1; i < n; ++i) {
          if (arr[i] > max_val) {
              max_val = arr[i];
          }
      }
  
      // 对每一位进行计数排序
      for (int exp = 1; max_val / exp > 0; exp *= 10) {
          countSortForRadix(arr, n, exp);
      }
  }
  

• 注:
  • n 表示待排序元素的数量。
  • k 表示待排序元素的范围（例如，计数排序中最大值-最小值+1）。
  • d 表示数字的位数（基数排序）。
  • 快速排序的最坏时间复杂度 O(n2) 发生在输入已经有序或接近有序，且选择的基准不好的情况下。
  • 桶排序的最坏时间复杂度 O(n2) 发生在所有元素都分到同一个桶里，并且桶内排序算法是 O(n2) 的时候。