深入C语言底层系列26-内省排序（Introsort）

内省排序（Introsort）是一种高效的混合排序算法，它结合了​​快速排序​​、​​堆排序​​和​​插入排序​​的优点，旨在保持快速排序在平均情况下高性能的同时，通过堆排序避免最坏情况下的性能退化，并对小数组使用插入排序进行优化。

以下是它的工作原理和关键机制：

🔁 一、核心机制与工作原理

内省排序的运作遵循一个精心设计的流程，以确保在各种情况下都能高效运行。其核心决策机制和流程可以参考下表：

🛠️ 二、C语言实现关键代码

以下是用C语言实现内省排序的关键函数和逻辑。

1. ​​辅助函数：交换与插入排序​​

   首先需要实现一些辅助函数，包括交换元素和插入排序。

   #include <stdio.h>
   #include <stdlib.h>
   #include <math.h>
   
   // 交换两个整数
   void swap(int *a, int *b) {
       int temp = *a;
       *a = *b;
       *b = temp;
   }
   
   // 插入排序 (用于小数组)
   void insertionSort(int arr[], int low, int high) {
       for (int i = low + 1; i <= high; i++) {
           int key = arr[i];
           int j = i - 1;
           while (j >= low && arr[j] > key) {
               arr[j + 1] = arr[j];
               j--;
           }
           arr[j + 1] = key;
       }
   }

2. ​​辅助函数：堆排序​​

   当递归过深时，需要堆排序来保证最坏情况下的性能。

   // 调整堆
   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) {
           swap(&arr[i], &arr[largest]);
           heapify(arr, n, largest);
       }
   }
   
   // 堆排序
   void heapSort(int arr[], int low, int high) {
       int n = high - low + 1;
       int *heapArr = arr + low; // 指向子数组起始位置的指针
   
       // 建堆
       for (int i = n / 2 - 1; i >= 0; i--)
           heapify(heapArr, n, i);
   
       // 一个个从堆顶取出元素
       for (int i = n - 1; i >= 0; i--) {
           swap(&heapArr[0], &heapArr[i]);
           heapify(heapArr, i, 0);
       }
   }

3. ​​分区函数（Partition）​​

   这是快速排序的核心，采用“三数取中法”选择基准值（pivot）以避免最坏情况。

   // 三数取中法选择基准值索引
   int medianOfThree(int arr[], int low, int high) {
       int mid = low + (high - low) / 2;
       if (arr[low] > arr[mid])
           swap(&arr[low], &arr[mid]);
       if (arr[low] > arr[high])
           swap(&arr[low], &arr[high]);
       if (arr[mid] > arr[high])
           swap(&arr[mid], &arr[high]);
       return mid; // 返回中间值的索引
   }
   
   // 快速排序的分区操作
   int partition(int arr[], int low, int high) {
       // 三数取中，并将基准值交换到high位置
       int pivotIdx = medianOfThree(arr, low, high);
       swap(&arr[pivotIdx], &arr[high]);
   
       int pivot = arr[high]; // 基准值
       int i = (low - 1);    // 小于基准值的区域的边界
   
       for (int j = low; j <= high - 1; j++) {
           if (arr[j] <= pivot) {
               i++;
               swap(&arr[i], &arr[j]);
           }
       }
       swap(&arr[i + 1], &arr[high]);
       return (i + 1);
   }

4. ​​内省排序核心递归函数​​

   这个函数实现了算法的核心逻辑决策过程。

   void introSortUtil(int arr[], int low, int high, int depthLimit) {
       int size = high - low + 1;
   
       // 如果大小小于等于16，使用插入排序
       if (size <= 16) {
           insertionSort(arr, low, high);
           return;
       }
   
       // 如果递归深度为0，使用堆排序
       if (depthLimit == 0) {
           heapSort(arr, low, high);
           return;
       }
   
       // 否则进行快速排序分区
       int pi = partition(arr, low, high);
   
       // 递归排序分区后的两部分
       introSortUtil(arr, low, pi - 1, depthLimit - 1);
       introSortUtil(arr, pi + 1, high, depthLimit - 1);
   }

5. ​​内省排序入口函数​​

   这是调用内省排序的入口。

   // 内省排序主函数
   void introSort(int arr[], int n) {
       // 计算最大递归深度限制: 2 * log2(n)
       int depthLimit = 2 * log2(n);
       introSortUtil(arr, 0, n - 1, depthLimit);
   }

⚙️ 三、性能分析

💡 四、优缺点

• ​​优点​​：

  • ​​高效​​：在大多数情况下，它保持了快速排序的高速度。
  • ​​鲁棒​​：通过堆排序避免了快速排序最坏情况的 O(n²) 时间复杂度，​​非常适合处理不可预测的输入数据​​。
  • ​​优化​​：对小数组使用插入排序，减少了不必要的递归开销。

• ​​缺点​​：

  • ​​不稳定​​：不能保证相等元素的原始顺序。
  • ​​实现复杂​​：比标准的快速排序或堆排序的实现要复杂得多。

🚀 五、适用场景

内省排序是一种​​通用的、高效的排序算法​​，非常适合作为默认的排序例程使用，特别是在需要良好性能且输入数据特征未知或可能包含最坏情况序列时。

• ​​C++标准库​​ std::sort()通常就采用内省排序或其变体。
• 适用于​​大规模数据排序​​，且对最坏情况性能有要求的场景。