简单选择排序和堆排序

最近在全面学习数据结构，常用算法记录：简单选择排序和堆排序，简单选择排序的基本思想是每一趟在待排序元素中选取关键字最小的元素加入有序子序列，直到所有元素有序，总共进行 $n-1$ 趟。
堆排序的基本思想见文末图片。

简单选择排序为不稳定排序。
堆排序为不稳定排序。

简单选择排序时间复杂度：

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

堆排序时间复杂度：

一个节点每下降一层，最多只需要比较两次关键字。若树高度为 $h$，某节点在第 $i$ 层，则将这个节点向下调整最多只需要下降 $h-i$ 层，那么对比次数不超过 ${2}(h-i)$，$n$ 个节点的完全二叉树树高 $h = \left\lfloor {{{\log }_2}n} \right\rfloor + 1$。

将整棵树调整为大根堆，关键字比较次数不超过：

$$ \sum\limits_{{\rm{i}} = h - 1}^1 {{2^{i - 1}}2(h - i) = } \sum\limits_{{\rm{i}} = h - 1}^1 {{2^i}(h - i) = } \sum\limits_{j = 1}^{h - 1} {{2^{h - j}}j \le 2n\sum\limits_{j = 1}^{h - 1} {\frac{j}{{{2^j}}}} } \le 4n $$

建堆的过程关键字的对比次数不超过 ${4}n$，建堆的时间复杂度：$O(n)$

heapSort总共需要 $n-1$ 趟，每一趟完成后都需要将根节点下坠，根节点最多下降 $h-1$ 层，因此，每一趟排序的复杂度不超过 $O(h)=O({{{\log }_2}n})$，总共 $n-1$ 趟，故总时间复杂度：$O(n{{{\log }_2}n})$

故堆排序的时间复杂度：$O(n)+O(n{{{\log }_2}n})=O(n{{{\log }_2}n})$
空间复杂度：$O(1)$

#include <iostream>

using namespace std;

void swap(int &a, int &b);
void selectSort(int arr[], int n);  //简单选择排序

void buildMaxHeap(int arr[], int len);  //建立大根堆
void headAdjust(int arr[], int k, int len);  //调整节点，使其较小节点下坠，使其符合大根堆的特性

void heapSort(int arr[], int len);  //堆排序（基于大根堆）

int main()
{
    int arr[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, heap_arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    selectSort(arr, length);
    for(auto item:arr)
        cout << item << " ";
    cout << endl;

    heapSort(heap_arr, length);
    for(int i = 1; i < length + 1; i++)
        cout << heap_arr[i] << " ";

    return 0;
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void selectSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)     //进行n-1次即可，最后一个数必然是最大的
    {
        int min = i;
        for (int j = i + 1; j < n; j++)     //从i后面一个数开始，找到一个最小的数
        {
            if (arr[j] < arr[min])
                min = j;    //记录最小数的下标
        }
        swap(arr[i], arr[min]);     //将最小数与i位置的数交换
    }
}

void buildMaxHeap(int arr[], int len)
{
    for (int i = len / 2; i > 0; i--)  //从最后一个分支节点开始调整，0为暂存节点
        headAdjust(arr, i, len);
}

void headAdjust(int arr[], int k, int len)
{
    arr[0] = arr[k];  //将当前节点暂存给arr[0]
    for (int i = 2 * k; i <= len; i *= 2)   //沿值较大的节点向下查找
    {
        if(i < len && arr[i] < arr[i + 1])  //i < len 保证当前节点有右孩子
            i++;    //记录左右子节点中较大的节点
        if(arr[0] >= arr[i])
            break;    //如果当前节点大于等于左右子节点，则不需要调整
        else{
            arr[k] = arr[i];   //将左右子节点中较大的节点放入当前双亲节点
            k = i;  //替换为较大的节点，进入下一次循环，看是否满足大于左右孩子的条件
        }
    }
    arr[k] = arr[0];  //将待调整的节点的值放入最终位置
}

void heapSort(int arr[], int len)
{
    buildMaxHeap(arr, len);     //建立大根堆
    for (int i = len; i > 1; i--)
    {
        swap(arr[1], arr[i]);   //堆顶和堆底交换，使堆底元素最大，注意堆顶是arr[1]，arr[0]是暂存节点
        headAdjust(arr, 1, i - 1);  //调整剩余的堆（i及其后面的序列已经有序），让堆顶元素下坠
    }
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/2090.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。