数据结构里选择排序与堆排序：从根基到高效实现的透彻探究

文章标题：

数据结构中选择排序与堆排序：从基础到高效实现的深入剖析

文章内容：

文章目录

• 选择排序
  • 1基本思想：
  • 2 直接选择排序:
  • 3. 堆排序
  • 基本思想
  • 堆排序的C语言实现
  • 堆排序的工作原理
  • 堆排序的性能分析
  • 4. 选择排序与堆排序的比较
  • 5. 选择排序的变种与优化
  • 结语

选择排序

1基本思想：

每一次从待排序的数据元素里找出最小（或者最大）的那一个元素，把它放到序列的起始位置，一直到所有待排序的数据元素都排好序为止。

2 直接选择排序:

在元素集合array[i]到array[n-1]之中去挑选关键码最大（小）的数据元素，如果这个元素不是这组元素里的最后一个（第一个）元素，就把它和这组元素里的最后一个（第一个）元素进行交换。接着在剩下的array[i]到array[n-2]（array[i+1]到array[n-1]）集合中，重复上面的步骤，直到剩下的集合里只有1个元素为止。

核心思路：通过遍历找到最小值，然后把这个最小值交换到最左边。
优化：我们同时去寻找最大值和最小值，把最小值放到最左边，最大值放到最右边。

// 单趟选择排序
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1; // 数组下标范围是[0, n-1]

    // 初始化最大值和最小值的下标
    int mini = begin;
    int maxi = begin;

    // 遍历数组来寻找最大值和最小值的下标
    for(int i = begin + 1; i <= end; i++) // i从begin+1开始，因为第一个元素已经被初始化为mini和maxi了
    {
        // 寻找最大值的下标
        if(a[i] > a[maxi])
        {
            maxi = i;
        }
        // 寻找最小值的下标
        if(a[i] < a[mini])
        {
            mini = i;
        }
    }

    // 把最小值交换到最左边
    Swap(&a[begin], &a[mini]);
    // 把最大值交换到最右边
    Swap(&a[end], &a[maxi]);
}

接下来是多趟排序的实现：

// 交换函数
void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 选择排序完整实现
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;

    while (begin < end) 
    {
        int mini = begin, maxi = begin;

        // 遍历当前未排序的部分，寻找最大值和最小值
        for (int i = begin + 1; i <= end; i++)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
            if (a[i] < a[mini])
            {
                mini = i;
            }
        }

        // 将最小值交换到最左边
        Swap(&a[begin], &a[mini]);

        // 将最大值交换到最右边
        Swap(&a[end], &a[maxi]);

        // 缩小未排序的区间
        begin++;
        end--;
    }
}

这里存在一个很大的陷阱

当maxi和begin重合的时候，mini先和begin交换，交换完之后，maxi再和end交换的时候，maxi对应的值已经改变了，变成了mini指向的值，所以这时候要把maxi置为mini。

所以完整的代码实现如下：

void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    // 寻找最小数和最大数的下标
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; i++)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
            if (a[i] < a[mini])
            {
                mini = i;
            }
        }
        Swap(&a[begin], &a[mini]);// 最小值与最左边交换
        Swap(&a[end], &a[maxi]);// 最大值与最右边交换
        // 处理特殊情况：如果最大值正好在begin位置，需要调整maxi
        if (begin == maxi)
        {
            maxi = mini; // 因为mini和begin交换后，最大值的位置发生了变化
        }
        begin++;
        end--;
    }
}

直接选择排序的特性总结：
1. 直接选择排序的思路很好理解，但是效率不太高。在实际中很少被使用。
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

3. 堆排序

堆排序（Heap Sort）是选择排序的一种高效实现方式，它利用堆这种数据结构来优化最大/最小值的查找过程。

基本思想

1. 把待排序的序列构建成一个大顶堆（或者小顶堆）。
2. 这时候，整个序列的最大值（或者最小值）就是堆顶的根节点。
3. 将它和末尾元素进行交换，这时候末尾就成为了最大值。
4. 然后把剩下的n-1个元素重新构建成一个堆，这样就能得到n个元素中的次小值。
5. 重复这样的操作，就能得到一个有序的序列了。
   

堆排序的C语言实现

#include <stdio.h>

// 交换函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆
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 n) {
    // 构建最大堆（从最后一个非叶子节点开始）
    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);
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

// 测试代码
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

堆排序的工作原理

1. 建堆 ：从最后一个非叶子节点开始，自底向上调整堆，确保每个父节点都大于其子节点，从而构建出一个最大堆。
2. 排序 ：
   • 将堆顶元素（最大值）与最后一个元素交换
   • 减少堆的大小（排除已排序的最大值）
   • 调整剩余的堆，使其重新成为最大堆
   • 重复这个过程，直到堆中只剩下一个元素

堆排序的性能分析

• 时间复杂度 ：
  • 建堆过程：O(n)
  • 每次调整堆：O(log n)
  • 总时间复杂度：O(n log n)
• 空间复杂度 ：O(1)，是一种原地排序算法
• 稳定性 ：不稳定。在交换堆顶元素和末尾元素时，可能会改变相同值的相对顺序

4. 选择排序与堆排序的比较

5. 选择排序的变种与优化

除了上面提到的同时寻找最大值和最小值的优化方法外，选择排序还有以下几种常见的变种和优化方式：
1. 双向选择排序 ：同时从数组的两端进行选择排序，分别找到最小值和最大值。
2. 锦标赛排序 ：通过锦标赛（树形选择）的方式来减少比较次数。
3. 堆排序 ：利用堆结构来优化选择过程，把时间复杂度降低到O(n log n)。

结语

选择排序作为一种基础的排序算法，虽然在实际应用中因为其O(n²)的时间复杂度而不常被使用，但是它的思想简单清晰，是学习更复杂排序算法的基础。理解选择排序的原理和实现细节，对于掌握算法设计和分析的基本方法有着重要的意义。

堆排序作为选择排序的高效变种，通过利用堆这种数据结构，把时间复杂度优化到了O(n log n)，在大规模数据排序中有着重要的应用价值。