【C++】十大排序算法之堆排序计数排序

本次介绍内容参考自：十大经典算法>排序算法（C++实现） - fengMisaka - 博客园 (cnblogs.com)

算法>排序算法是《数据结构与算法》中最基本的算法之一。

十种常见算法>排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。

【十大经典算法>排序算法分类】

【十大经典算法>排序算法的复杂度分析】

名词解释：

时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。
n：待排序列的个数。
k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。
In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。
Out-place：非原地算法，占用额外内存。
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

一、堆排序（Heap-Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种算法>排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1.1、算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

1.2、动图演示

堆排序动图演示

1.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file HeapSort.hpp
* @brief 堆排序
* @autor 写代码的小恐龙er
* @date 2024/03/06
*/

// 时间复杂度O(n * log n)
// 空间复杂度O(k)

void HeapAdjust(int* arr, int start, int end)
{
	int tmp = arr[start];
	for (int i = 2 * start + 1; i <= end; i = i * 2 + 1)
	{
        // 有右孩子并且左孩子小于右孩子
		if (i < end&& arr[i] < arr[i + 1]) {
			i++;
		}//i一定是左右孩子的最大值
		if (arr[i] > tmp) {
			arr[start] = arr[i];
			start = i;
		}
		else {
			break;
		}
	}
	arr[start] = tmp;
}
void HeapSort(int* arr, int len)
{
	//第一次建立大根堆，从后往前依次调整
	for(int i=(len-1-1)/2;i>=0;i--) {
		HeapAdjust(arr, i, len - 1);
	}
	//每次将根和待排序的最后一次交换，然后在调整
	int tmp = 0;
	for (int i = 0; i < len - 1; i++) {
		tmp = arr[0];
		arr[0] = arr[len - 1-i];
		arr[len - 1 - i] = tmp;
		HeapAdjust(arr, 0, len - 1-i- 1);
	}
}

1.4 、算法分析

堆排序是不稳定排序，适合数据量较大的序列，它的平均时间复杂度为 Ο(n * log n)，空间复杂度为 O(1)。
此外，堆排序仅需一个记录大小供交换用的辅助存储空间。

二、计数排序（Counting Sort）

计数排序（Counting Sort）不是基于比较的算法>排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

2.1 、算法描述

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
~~对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；~~
~~反向填充目标数组：将每个元素i放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。~~

2.2 、动图演示

计数排序动图演示

2.3、C++编码

/**
* @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* @file CountingSort.hpp
* @brief 计数排序
* @autor 写代码的小恐龙er
* @date 2024/03/06
*/

// 时间复杂度O(n + k)
// 空间复杂度O(k)

void CountingSort(int arr[], int n) {
    if (arr == NULL) return;
    // 定义辅助空间并初始化
    int max = arr[0], min = arr[0];
    int i;
    for (i = 1; i < n; i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    int r = max - min + 1;
    vector<int> C(r, 0);

    // 统计每个元素出现的次数
    for (i = 0; i < n; i++) C[arr[i] - min]++;

    i = 0;
    for(int j = 0; j < r; j++){
        while(C[j]--){
            arr[i++] = j + min;
        }
    }

    // 其实当记录了每个元素出现的个数和相对映射 则无需再进行下面的操作,
    // 直接将辅助空间的元素赋值到原数组中

    // // 对辅助空间内数据进行计算
    // for (i = 1; i < r; i++) C[i] += C[i - 1];
    // // 反向填充目标数组
    // for (i = n - 1; i >= 0; i--) R[--C[arr[i] - min]] = arr[i];
    // // 目标数组里的结果重新赋值给 arr
    // for (i = 0; i < n; i++) arr[i] = R[i];

}