网站制作公司技术部门,创建网站选哪家好,自己做的旅游网站 介绍,网站建网站建设企业排序算法
排序算法用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用#xff0c;因为有序数据通常能够被更高效地查找、分析和处理。
排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定#xff0c;如数字大小、字符 ASCII…排序算法
排序算法用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用因为有序数据通常能够被更高效地查找、分析和处理。
排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定如数字大小、字符 ASCII 码顺序或自定义规则。
评价维度
运行效率 期望排序算法的时间复杂度尽量低且总体操作数量较少时间复杂度中的常数项变小。对于大数据量的情况运行效率显得尤为重要。
就地性 顾名思义原地排序通过在原数组上直接操作实现排序无须借助额外的辅助数组从而节省内存。通常情况下原地排序的数据搬运操作较少运行速度也更快。
稳定性 稳定排序在完成排序后相等元素在数组中的相对顺序不发生改变。 稳定排序是多级排序场景的必要条件。
自适应性 自适应排序的时间复杂度会受输入数据的影响即最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等。 自适应性需要根据具体情况来评估。如果最差时间复杂度差于平均时间复杂度说明排序算法在某些数据下性能可能劣化因此被视为负面属性而如果最佳时间复杂度优于平均时间复杂度则被视为正面属性。
是否基于比较 基于比较的排序依赖比较运算符、、来判断元素的相对顺序从而排序整个数 组理论最优时间复杂度为 ( log ) 。而非比较排序不使用比较运算符时间复杂度可达 () 但其通用性相对较差。
理想排序算法
运行快、原地、稳定、正向自适应、通用性好。显然迄今为止尚未发现兼具以上所有特性的排序算法。因此在选择排序算法时需要根据具体的数据特点和问题需求来决定。
选择排序
选择排序selection sort的工作原理开启一个循环每轮从未排序区间选择最小的元素将其放到已排序区间的末尾。
设数组的长度为 选择排序的算法流程如图 1.初始状态下所有元素未排序即未排序索引区间为 [0, − 1] 。 2.选取区间 [0, − 1] 中的最小元素将其与索引 0 处的元素交换。完成后数组前 1 个元素已排序。 3.选取区间 [1, − 1] 中的最小元素将其与索引 1 处的元素交换。完成后数组前 2 个元素已排序。 4. 以此类推。经过 − 1 轮选择与交换后数组前 − 1 个元素已排序。 5. 仅剩的一个元素必定是最大元素无须排序因此数组排序完成
/* 选择排序 */
void selectionSort(vectorint nums) {int n nums.size();// 外循环未排序区间为 [i, n-1]for (int i 0; i n - 1; i) {// 内循环找到未排序区间内的最小元素int k i;for (int j i 1; j n; j) {if (nums[j] nums[k])k j; // 记录最小元素的索引}// 将该最小元素与未排序区间的首个元素交换swap(nums[i], nums[k]);}
}时间复杂度为 (^2)、非自适应排序外循环共 − 1 轮第一轮的未排序区间长度为 最后一轮的未排序区间长度为 2 即各轮外循环分别包含 、 − 1、…、3、2 轮内循环求和为 ((−1)(2))/2 。 空间复杂度为 (1)、原地排序指针 和 使用常数大小的额外空间。 非稳定排序如图所示元素 nums[i] 有可能被交换至与其相等的元素的右边导致两者的相对顺序发生改变。 冒泡排序
冒泡排序bubble sort通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样因此得名冒泡排序。
冒泡过程可以利用元素交换操作来模拟从数组最左端开始向右遍历依次比较相邻元素大小如果“左元素 右元素”就交换二者。遍历完成后最大的元素会被移动到数组的最右端。 算法流程 1.首先对 个元素执行“冒泡”将数组的最大元素交换至正确位置 2.接下来对剩余 − 1 个元素执行“冒泡”将第二大元素交换至正确位置 3.以此类推经过 − 1 轮“冒泡”后前 − 1 大的元素都被交换至正确位置 4.仅剩的一个元素必定是最小元素无须排序因此数组排序完成。 /* 冒泡排序 */
void bubbleSort(vectorint nums) {// 外循环未排序区间为 [0, i]for (int i nums.size() - 1; i 0; i--) {// 内循环将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j 0; j i; j) {if (nums[j] nums[j 1]) {// 交换 nums[j] 与 nums[j 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j 1]);}}}
}效率优化如果某轮“冒泡”中没有执行任何交换操作说明数组已经完成排序可直接返回结果。 增加一个标志位 flag 来监测这种情况一旦出现就立即返回冒泡排序的最差时间复杂度和平均时间复杂度仍为 (^2) 但当输入数组完全有序时可达到最佳时间复杂度 ()。
/* 冒泡排序标志优化*/
void bubbleSortWithFlag(vectorint nums) {// 外循环未排序区间为 [0, i]for (int i nums.size() - 1; i 0; i--) {bool flag false; // 初始化标志位// 内循环将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j 0; j i; j) {if (nums[j] nums[j 1]) {// 交换 nums[j] 与 nums[j 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j 1]);flag true; // 记录交换元素coutswap: nums[j] - nums[j1]endl;}}if (!flag)break; // 此轮“冒泡”未交换任何元素直接跳出}
}时间复杂度为 (^2)、自适应排序各轮“冒泡”遍历的数组长度依次为 − 1、 − 2、…、2、1 总和为 ( − 1)/2 。在引入 flag 优化后最佳时间复杂度可达到 () 。 空间复杂度为 (1)、原地排序指针 和 使用常数大小的额外空间。 稳定排序由于在“冒泡”中遇到相等元素不交换。
插入排序
插入排序insertion sort是一种简单的排序算法在未排序区间选择一个基准元素将该元素与其左侧已排序区间的元素逐一比较大小并将该元素插入到正确的位置。
设基准元素为 base 需要将从目标索引到 base 之间的所有元素向右移动一位然后将 base 赋值给目标索引。 算法流程 1.初始状态下数组的第 1 个元素已完成排序。 2.选取数组的第 2 个元素作为 base 将其插入到正确位置后数组的前 2 个元素已排序。 3.选取第 3 个元素作为 base 将其插入到正确位置后数组的前 3 个元素已排序。 4.以此类推在最后一轮中选取最后一个元素作为 base 将其插入到正确位置后所有元素均已排序
/* 插入排序 */
void insertionSort(vectorint nums) {// 外循环已排序元素数量为 1, 2, ..., nfor (int i 1; i nums.size(); i) {int base nums[i], j i - 1;// 内循环将 base 插入到已排序部分的正确位置while (j 0 nums[j] base) {nums[j 1] nums[j]; // 将 nums[j] 向右移动一位j--;}nums[j 1] base; // 将 base 赋值到正确位置 num[0]--j-1// coutbaseendl;}
}算法特性 时间复杂度为 (^2)、自适应排序在最差情况下每次插入操作分别需要循环 − 1、 − 2、…、2、1 次求和得到 ( − 1)/2 因此时间复杂度为 ( ^2) 。在遇到有序数据时插入操作会提前终止。当输入数组完全有序时插入排序达到最佳时间复杂度 () 。 空间复杂度为 (1)、原地排序指针 和 使用常数大小的额外空间。 稳定排序在插入操作过程中会将元素插入到相等元素的右侧不会改变它们的顺序。
插入排序的优势
插入排序的时间复杂度为 (^2) 而快速排序的时间复杂度为 ( log ) 。尽管插入排序的时间复杂度更高但在数据量较小的情况下插入排序通常更快。
这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 ( log ) 的算法属于基于分治策略的排序算法往往包含更多单元计算操作。而在数据量较小时^2 和 log 的数值比较接近复杂度不占主导地位每轮中的单元操作数量起到决定性作用。
虽然冒泡排序、选择排序和插入排序的时间复杂度都为 ( ^2) 但在实际情况中插入排序的使用频率显著高于冒泡排序和选择排序主要有以下原因 1.冒泡排序基于元素交换实现需要借助一个临时变量共涉及 3 个单元操作插入排序基于元素赋值实现仅需 1 个单元操作。因此冒泡排序的计算开销通常比插入排序更高 2.选择排序在任何情况下的时间复杂度都为 (^2) 。如果给定一组部分有序的数据插入排序通常比选 择排序效率更高。 3.选择排序不稳定无法应用于多级排序。
快速排序
快速排序quick sort是一种基于分治策略的排序算法运行高效应用广泛。 快速排序的核心操作是“哨兵划分”其目标是选择数组中的某个元素作为“基准数”将所有小于基准数的元素移到其左侧而大于基准数的元素移到其右侧。
具体来说哨兵划分的流程如图所示
选取数组最左端元素作为基准数初始化两个指针 i 和 j 分别指向数组的两端。设置一个循环在每轮中使用 ij分别寻找第一个比基准数大小的元素然后交换这两个元素。循环执行步骤 2. 直到 i 和 j 相遇时停止最后将基准数交换至两个子数组的分界线。
哨兵划分完成后原数组被划分成三部分左子数组、基准数、右子数组且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此我们接下来只需对这两个子数组进行排序。
/* 元素交换 */
static void swap(vectorint nums, int i, int j) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;
}/* 哨兵划分 */
static int partition(vectorint nums, int left, int right) {// 以 nums[left] 为基准数int i left, j right;while (i j) {while (i j nums[j] nums[left])j--; // 从右向左找首个小于基准数的元素while (i j nums[i] nums[left])i; // 从左向右找首个大于基准数的元素swap(nums, i, j); // 交换这两个元素}swap(nums, i, left); // 将基准数交换至两子数组的分界线return i; // 返回基准数的索引
}整体流程 1.首先对原数组执行一次“哨兵划分”得到未排序的左子数组和右子数组 2.然后对左子数组和右子数组分别递归执行“哨兵划分” 3.持续递归直至子数组长度为 1 时终止从而完成整个数组的排序 /* 快速排序尾递归优化 */
static void quickSort(vectorint nums, int left, int right) {// 子数组长度为 1 时终止while (left right) {// 哨兵划分操作int pivot partition(nums, left, right);// 对两个子数组中较短的那个执行快速排序if (pivot - left right - pivot) {quickSort(nums, left, pivot - 1); // 递归排序左子数组left pivot 1; // 剩余未排序区间为 [pivot 1, right]} else {quickSort(nums, pivot 1, right); // 递归排序右子数组right pivot - 1; // 剩余未排序区间为 [left, pivot - 1]}}
}时间复杂度为 ( log )、自适应排序在平均情况下哨兵划分的递归层数为 log 每层中的总循环数为 总体使用 ( log ) 时间。在最差情况下每轮哨兵划分操作都将长度为 的数组划分为长度为 0 和 −1 的两个子数组此时递归层数达到 每层中的循环数为 总体使用 (^2) 时间。 空间复杂度为 ()、原地排序在输入数组完全倒序的情况下达到最差递归深度 使用 () 栈帧空间。排序操作是在原数组上进行的未借助额外数组。 非稳定排序在哨兵划分的最后一步基准数可能会被交换至相等元素的右侧。
快速排序为什么快 尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同但通常快速排序的效率更高主要有以下原因 1.出现最差情况的概率很低虽然快速排序的最差时间复杂度为 (^2) 没有归并排序稳定但在绝大多数情况下快速排序能在 ( log ) 的时间复杂度下运行。 2.缓存使用效率高在执行哨兵划分操作时系统可将整个子数组加载到缓存因此访问元素的效率较 高。而像“堆排序”这类算法需要跳跃式访问元素从而缺乏这一特性。 3. 复杂度的常数系数小快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。
基准数优化
快速排序在某些输入下的时间效率可能降低。 极端例子假设输入数组是完全倒序的由于选择最左端元素作为基准数那么在哨兵划分完成后基准数被交换至数组最右端导致左子数组长度为 − 1、右子数组长度为 0 。如此递归下去每轮哨兵划分后都有一个子数组的长度为 0 分治策略失效快速排序退化为“冒泡排序”的近似形式。
为了尽量避免这种情况发生可以优化哨兵划分中的基准数的选取策略。例如可以随机选取一个元素作为基准数。然而如果运气不佳每次都选到不理想的基准数效率仍然不尽如人意。
为了进一步改进可以在数组中选取三个候选元素通常为数组的首、尾、中点元素并将这三个候选元素的中位数作为基准数。这样一来基准数“既不太小也不太大”的概率将大幅提升。当然还可以选取更多候选元素以进一步提高算法的稳健性。采用这种方法后时间复杂度劣化至 (^2) 的概率大大降低。
/* 哨兵划分三数取中值 */
static int partition(vectorint nums, int left, int right) {// 选取三个候选元素的中位数int med medianThree(nums, left, (left right) / 2, right);// 将中位数交换至数组最左端swap(nums, left, med);// 以 nums[left] 为基准数int i left, j right;while (i j) {while (i j nums[j] nums[left])j--; // 从右向左找首个小于基准数的元素while (i j nums[i] nums[left])i; // 从左向右找首个大于基准数的元素swap(nums, i, j); // 交换这两个元素}swap(nums, i, left); // 将基准数交换至两子数组的分界线return i; // 返回基准数的索引
}尾递归优化
在某些输入下快速排序可能占用空间较多。以完全有序的输入数组为例设递归中的子数组长度为 每轮哨兵划分操作都将产生长度为 0 的左子数组和长度为 − 1 的右子数组这意味着每一层递归调用减少的问题规模非常小只减少一个元素递归树的高度会达到 −1 此时需要占用 () 大小的栈帧空间。
为了防止栈帧空间的累积可以在每轮哨兵排序完成后比较两个子数组的长度仅对较短的子数组进行递归。 由于较短子数组的长度不会超过 /2 因此这种方法能确保递归深度不超过 log 从而将最差空间复杂度优化至 (log ) 。代码如下所示
/* 快速排序尾递归优化 */
static void quickSort(vectorint nums, int left, int right) {// 子数组长度为 1 时终止while (left right) {// 哨兵划分操作int pivot partition(nums, left, right);// 对两个子数组中较短的那个执行快速排序if (pivot - left right - pivot) {quickSort(nums, left, pivot - 1); // 递归排序左子数组left pivot 1; // 剩余未排序区间为 [pivot 1, right]} else {quickSort(nums, pivot 1, right); // 递归排序右子数组right pivot - 1; // 剩余未排序区间为 [left, pivot - 1]}}
}归并排序
归并排序merge sort是一种基于分治策略的排序算法包含“划分”和“合并”阶段。 1.划分阶段通过递归不断地将数组从中点处分开将长数组的排序问题转换为短数组的排序问题。 2.合并阶段当子数组长度为 1 时终止划分开始合并持续地将左右两个较短的有序数组合并为一个较长的有序数组直至结束。 “划分阶段” 从顶至底递归地将数组从中点切分为两个子数组。 1.计算数组中点 mid 递归划分左子数组区间 [left, mid] 和右子数组区间 [mid 1, right] 。 2.递归执行步骤 1. 直至子数组区间长度为 1 时终止。
“合并阶段” 从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是从长度为 1 的子数组开始合并合并阶段中的每个子数组都是有序的。 观察发现归并排序与二叉树后序遍历的递归顺序是一致的 后序遍历先递归左子树再递归右子树最后处理根节点。 归并排序先递归左子数组再递归右子数组最后处理合并。 归并排序的实现如以下代码所示。请注意nums 的待合并区间为 [left, right] 而 tmp 的对应区间为 [0, right - left] 。
/* 合并左子数组和右子数组 */
void merge(vectorint nums, int left, int mid, int right) {// 左子数组区间为 [left, mid], 右子数组区间为 [mid1, right]// 创建一个临时数组 tmp 用于存放合并后的结果vectorint tmp(right - left 1);// 初始化左子数组和右子数组的起始索引int i left, j mid 1, k 0;// 当左右子数组都还有元素时进行比较并将较小的元素复制到临时数组中while (i mid j right) {if (nums[i] nums[j])tmp[k] nums[i];elsetmp[k] nums[j];}// 将左子数组和右子数组的剩余元素复制到临时数组中while (i mid) {tmp[k] nums[i];}while (j right) {tmp[k] nums[j];}// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间for (k 0; k tmp.size(); k) {nums[left k] tmp[k];}
}时间复杂度为 ( log )、非自适应排序划分产生高度为 log 的递归树每层合并的总操作数量为 因此总体时间复杂度为 ( log ) 。 空间复杂度为 ()、非原地排序递归深度为 log 使用 (log ) 大小的栈帧空间。合并操作需要借助辅助数组实现使用 () 大小的额外空间。 稳定排序在合并过程中相等元素的次序保持不变。
链表排序
对于链表归并排序相较于其他排序算法具有显著优势可以将链表排序任务的空间复杂度优化至 (1) 。 划分阶段可以使用“迭代”替代“递归”来实现链表划分工作从而省去递归使用的栈帧空间。 合并阶段在链表中节点增删操作仅需改变引用指针即可实现因此合并阶段将两个短有序链表合并为一个长有序链表无须创建额外链表。
堆排序
堆排序heap sort是一种基于堆数据结构实现的高效排序算法。可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。 1.输入数组并建立小顶堆此时最小元素位于堆顶 2.不断执行出堆操作依次记录出堆元素即可得到从小到大排序的序列。
以上方法虽然可行但需要借助一个额外数组来保存弹出的元素比较浪费空间。 在实际中通常使用一种更加优雅的实现方式。
算法流程 1.输入数组并建立大顶堆。完成后最大元素位于堆顶 2.将堆顶元素第一个元素与堆底元素最后一个元素交换。完成交换后堆的长度减 1 已排序元素数量加1 3.从堆顶元素开始从顶到底执行堆化操作sift down。完成堆化后堆的性质得到修复 4.循环执行第 2. 步和第 3. 步。循环 − 1 轮后即可完成数组排序。 实际上元素出堆操作中也包含第 2. 步和第 3. 步只是多了一个弹出元素的步骤。 在代码实现中使用了与“堆”相同的从顶至底堆化 sift_down() 函数。值得注意的是由于堆的长度会随着提取最大元素而减小因此需要给 sift_down() 函数添加一个长度参数 用于指定堆的当前有效长度。代码如下所示
/*** File: heap_sort.cpp* Created Time: 2023-05-26* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 堆的长度为 n 从节点 i 开始从顶至底堆化 */
void siftDown(vectorint nums, int n, int i) {while (true) {// 判断节点 i, l, r 中值最大的节点记为 maint l 2 * i 1;int r 2 * i 2;int ma i;if (l n nums[l] nums[ma])ma l;if (r n nums[r] nums[ma])ma r;// 若节点 i 最大或索引 l, r 越界则无须继续堆化跳出if (ma i) {break;}// 交换两节点swap(nums[i], nums[ma]);// 循环向下堆化i ma;}
}/* 堆排序 */
void heapSort(vectorint nums) {// 建堆操作堆化除叶节点以外的其他所有节点for (int i nums.size() / 2 - 1; i 0; --i) {siftDown(nums, nums.size(), i);}// 从堆中提取最大元素循环 n-1 轮for (int i nums.size() - 1; i 0; --i) {// 交换根节点与最右叶节点交换首元素与尾元素swap(nums[0], nums[i]);// 以根节点为起点从顶至底进行堆化siftDown(nums, i, 0);}
}/* Driver Code */
int main() {vectorint nums {4, 1, 3, 1, 5, 2};heapSort(nums);cout 堆排序完成后 nums ;printVector(nums);return 0;
}算法特性 时间复杂度为 ( log )、非自适应排序建堆操作使用 () 时间。从堆中提取最大元素的时间复杂度为 (log ) 共循环 − 1 轮。 空间复杂度为 (1)、原地排序几个指针变量使用 (1) 空间。元素交换和堆化操作都是在原数组上进行的。 非稳定排序在交换堆顶元素和堆底元素时相等元素的相对位置可能发生变化。
桶排序
基于比较的排序算法”它们通过比较元素间的大小来实现排序。 此类排序算法的时间复杂度无法超越 ( log ) 。 “非比较排序算法”它们的时间复杂度可以达到线性阶。
桶排序bucket sort是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶每个桶对应一个数据范围将数据平均分配到各个桶中然后在每个桶内部分别执行排序最终按照桶的顺序将所有数据合并。 考虑一个长度为 的数组其元素是范围 [0, 1) 内的浮点数。 桶排序的流程如图所示 1.初始化 个桶将 个元素分配到 个桶中。 2.对每个桶分别执行排序这里采用编程语言的内置排序函数。 3.按照桶从小到大的顺序合并结果。
/*** File: bucket_sort.cpp* Created Time: 2023-03-30* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 桶排序 */
void bucketSort(vectorfloat nums) {// 初始化 k n/2 个桶预期向每个桶分配 2 个元素int k nums.size() / 2;vectorvectorfloat buckets(k);// 1. 将数组元素分配到各个桶中for (float num : nums) {// 输入数据范围为 [0, 1)使用 num * k 映射到索引范围 [0, k-1]int i num * k;// 将 num 添加进桶 bucket_idxbuckets[i].push_back(num);}// 2. 对各个桶执行排序for (vectorfloat bucket : buckets) {// 使用内置排序函数也可以替换成其他排序算法sort(bucket.begin(), bucket.end());}// 3. 遍历桶合并结果int i 0;for (vectorfloat bucket : buckets) {for (float num : bucket) {nums[i] num;}}
}/* Driver Code */
int main() {// 设输入数据为浮点数范围为 [0, 1)vectorfloat nums {0.49f, 0.96f, 0.82f, 0.09f, 0.57f, 0.43f, 0.91f, 0.75f, 0.15f, 0.37f};bucketSort(nums);cout 桶排序完成后 nums ;printVector(nums);return 0;
}算法特性 桶排序适用于处理体量很大的数据。例如输入数据包含 100 万个元素由于空间限制系统内存无法一次性加载所有数据。此时可以将数据分成 1000 个桶然后分别对每个桶进行排序最后将结果合并。
时间复杂度为 ( ) 假设元素在各个桶内平均分布那么每个桶内的元素数量为 / 。 假设排序单个桶使用 ( / log /) 时间则排序所有桶使用 ( log /) 时间。当桶数量 比较大时时间复杂度则趋向于 () 。合并结果时需要遍历所有桶和元素花费 ( ) 时间。 自适应排序在最差情况下所有数据被分配到一个桶中且排序该桶使用 (^2) 时间。 空间复杂度为 ( )、非原地排序需要借助 个桶和总共 个元素的额外空间。 桶排序是否稳定取决于排序桶内元素的算法是否稳定。
如何实现平均分配? 桶排序的时间复杂度理论上可以达到 () 关键在于将元素均匀分配到各个桶中因为实际数据往往不是均匀分布的。
为实现平均分配可以先设定一条大致的分界线将数据粗略地分到几个桶中。分配完毕后再将数据较多的桶继续划分为几个桶直至所有桶中的元素数量大致相等。 可以根据数据概率分布设置每个桶的分界线。值得注意的是数据分布并不一定需要特意统计也可以根据数据特点采用某种概率模型进行近似。
计数排序
计数排序通过统计元素数量来实现排序通常应用于整数数组。
给定一个长度为 的数组 nums 其中的元素都是“非负整数”计数排序的整体流程 1.遍历数组找出其中的最大数字记为 然后创建一个长度为 1 的辅助数组 counter 。 2.借助 counter 统计 nums 中各数字的出现次数其中 counter[num] 对应数字 num 的出现次数。统计方法很简单只需遍历 nums设当前数字为 num每轮将 counter[num] 增加 1 即可。 3.由于 counter 的各个索引天然有序因此相当于所有数字已经排序好了。接下来遍历 counter 根据各数字出现次数从小到大的顺序填入 nums 即可。
/*** File: counting_sort.cpp* Created Time: 2023-03-17* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 计数排序 */
// 简单实现无法用于排序对象
void countingSortNaive(vectorint nums) {// 1. 统计数组最大元素 mint m 0;for (int num : nums) {m max(m, num);}// 2. 统计各数字的出现次数// counter[num] 代表 num 的出现次数vectorint counter(m 1, 0);for (int num : nums) {counter[num];}// 3. 遍历 counter 将各元素填入原数组 numsint i 0;for (int num 0; num m 1; num) {for (int j 0; j counter[num]; j, i) {nums[i] num;}}
}从桶排序的角度看可以将计数排序中的计数数组 counter 的每个索引视为一个桶将统计数量的过程看作将各个元素分配到对应的桶中。本质上计数排序是桶排序在整型数据下的一个特例。
完整实现
如果输入数据是对象上述步骤 3. 就失效了。 首先计算 counter 的“前缀和”。顾名思义索引 i 处的前缀和 prefix[i] 等于数组前 i 个元素之和 前缀和具有明确的意义prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。 它告诉我们各个元素应该出现在结果数组的哪个位置。接下来我们倒序遍历原数组 nums 的每个元素 num 在每轮迭代中执行以下两步 1.将 num 填入数组 res 的索引 prefix[num] - 1 处。 2.令前缀和 prefix[num] 减小 1 从而得到下次放置 num 的索引。 遍历完成后数组 res 中就是排序好的结果最后使用 res 覆盖原数组 nums 即可。
/* 计数排序 */
// 完整实现可排序对象并且是稳定排序
void countingSort(vectorint nums) {// 1. 统计数组最大元素 mint m 0;for (int num : nums) {m max(m, num);}// 2. 统计各数字的出现次数// counter[num] 代表 num 的出现次数vectorint counter(m 1, 0);for (int num : nums) {counter[num];}// 3. 求 counter 的前缀和将“出现次数”转换为“尾索引”// 即 counter[num]-1 是 num 在 res 中最后一次出现的索引for (int i 0; i m; i) {counter[i 1] counter[i];}// 4. 倒序遍历 nums 将各元素填入结果数组 res// 初始化数组 res 用于记录结果int n nums.size();vectorint res(n);for (int i n - 1; i 0; i--) {int num nums[i];res[counter[num] - 1] num; // 将 num 放置到对应索引处counter[num]--; // 令前缀和自减 1 得到下次放置 num 的索引}// 使用结果数组 res 覆盖原数组 numsnums res;
}
算法特性
时间复杂度为 ( ) 涉及遍历 nums 和遍历 counter 都使用线性时间。一般情况下 ≫ 时间复杂度趋于 () 。 空间复杂度为 ( )、非原地排序借助了长度分别为 和 的数组 res 和 counter 。 稳定排序由于向 res 中填充元素的顺序是“从右向左”的因此倒序遍历 nums 可以避免改变相等元素之间的相对位置从而实现稳定排序。实际上正序遍历 nums 也可以得到正确的排序结果但结果是非稳定的。
局限性
仅通过统计数量就可以实现高效的排序。然而使用计数排序的前置条件相对较为严格。
计数排序只适用于非负整数。若想将其用于其他类型的数据需要确保这些数据可以转换为非负整数并且在转换过程中不能改变各个元素之间的相对大小关系。例如对于包含负数的整数数组可以先给所有数字加上一个常数将全部数字转化为正数排序完成后再转换回去。 计数排序适用于数据量大但数据范围较小的情况。比如在上述示例中 不能太大否则会占用过多空间。而当 ≪ 时计数排序使用 () 时间可能比 ( log ) 的排序算法还要慢。
基数排序
基数排序的核心思想与计数排序一致也通过统计个数来实现排序。 在此基础上基数排序利用数字各位之间的递进关系依次对每一位进行排序从而得到最终的排序结果。
以学号数据为例假设数字的最低位是第 1 位最高位是第 8 位基数排序的流程如图 对于一个 进制的数字 要获取其第 位 _ 可以使用以下计算公式 其中 ⌊⌋ 表示对浮点数 向下取整而 mod 表示对 取模取余。对于学号数据 10 且 ∈ [1, 8]。
/*** File: radix_sort.cpp* Created Time: 2023-03-26* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 获取元素 num 的第 k 位其中 exp 10^(k-1) */
int digit(int num, int exp) {// 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算return (num / exp) % 10;
}/* 计数排序根据 nums 第 k 位排序 */
void countingSortDigit(vectorint nums, int exp) {// 十进制的位范围为 0~9 因此需要长度为 10 的桶数组vectorint counter(10, 0);int n nums.size();// 统计 0~9 各数字的出现次数for (int i 0; i n; i) {int d digit(nums[i], exp); // 获取 nums[i] 第 k 位记为 dcounter[d]; // 统计数字 d 的出现次数}// 求前缀和将“出现个数”转换为“数组索引”for (int i 1; i 10; i) {counter[i] counter[i - 1];}// 倒序遍历根据桶内统计结果将各元素填入 resvectorint res(n, 0);for (int i n - 1; i 0; i--) {int d digit(nums[i], exp);int j counter[d] - 1; // 获取 d 在数组中的索引 jres[j] nums[i]; // 将当前元素填入索引 jcounter[d]--; // 将 d 的数量减 1}// 使用结果覆盖原数组 numsfor (int i 0; i n; i)nums[i] res[i];
}/* 基数排序 */
void radixSort(vectorint nums) {// 获取数组的最大元素用于判断最大位数int m *max_element(nums.begin(), nums.end());// 按照从低位到高位的顺序遍历for (int exp 1; exp m; exp * 10)// 对数组元素的第 k 位执行计数排序// k 1 - exp 1// k 2 - exp 10// 即 exp 10^(k-1)countingSortDigit(nums, exp);
}/* Driver Code */
int main() {// 基数排序vectorint nums {10546151, 35663510, 42865989, 34862445, 81883077,88906420, 72429244, 30524779, 82060337, 63832996};radixSort(nums);cout 基数排序完成后 nums ;printVector(nums);return 0;
}为什么从最低位开始排序 在连续的排序轮次中后一轮排序会覆盖前一轮排序的结果。举例来说如果第一轮排序结果 而第二轮排序结果 那么第二轮的结果将取代第一轮的结果。由于数字的高位优先级高于低位因此应该先排序低位再排序高位。
算法特性
相较于计数排序基数排序适用于数值范围较大的情况但前提是数据必须可以表示为固定位数的格式且位数不能过大。例如浮点数不适合使用基数排序因为其位数 过大可能导致时间复杂度 () ≫ (^2)。
时间复杂度为 ()设数据量为 、数据为 进制、最大位数为 则对某一位执行计数排序使用 ( ) 时间排序所有 位使用 (( )) 时间。通常情况下 和 都相对较小时间复杂度趋向 () 。 空间复杂度为 ( )、非原地排序与计数排序相同基数排序需要借助长度为 和 的数组 res 和 counter 。 稳定排序当计数排序稳定时基数排序也稳定当计数排序不稳定时基数排序无法保证得到正确的 排序结果。
小结 学习地址
学习地址https://github.com/krahets/hello-algo 重新复习数据结构所有的内容都来自这里。 文章转载自： http://www.morning.eviap.com.gov.cn.eviap.com http://www.morning.jgykx.cn.gov.cn.jgykx.cn http://www.morning.gtylt.cn.gov.cn.gtylt.cn http://www.morning.rpfpx.cn.gov.cn.rpfpx.cn http://www.morning.vnuwdy.cn.gov.cn.vnuwdy.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.tbknh.cn.gov.cn.tbknh.cn http://www.morning.ffhlh.cn.gov.cn.ffhlh.cn http://www.morning.nrjr.cn.gov.cn.nrjr.cn http://www.morning.pxdgy.cn.gov.cn.pxdgy.cn http://www.morning.qjdqj.cn.gov.cn.qjdqj.cn http://www.morning.grxsc.cn.gov.cn.grxsc.cn http://www.morning.pqjpw.cn.gov.cn.pqjpw.cn http://www.morning.dskmq.cn.gov.cn.dskmq.cn http://www.morning.fhlfp.cn.gov.cn.fhlfp.cn http://www.morning.haolipu.com.gov.cn.haolipu.com http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.yrbhf.cn.gov.cn.yrbhf.cn http://www.morning.kjtdy.cn.gov.cn.kjtdy.cn http://www.morning.hlfnh.cn.gov.cn.hlfnh.cn http://www.morning.rmqmc.cn.gov.cn.rmqmc.cn http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.nrzkg.cn.gov.cn.nrzkg.cn http://www.morning.yqhdy.cn.gov.cn.yqhdy.cn http://www.morning.3jiax.cn.gov.cn.3jiax.cn http://www.morning.fbjnr.cn.gov.cn.fbjnr.cn http://www.morning.wxfjx.cn.gov.cn.wxfjx.cn http://www.morning.dqwkm.cn.gov.cn.dqwkm.cn http://www.morning.blqmn.cn.gov.cn.blqmn.cn http://www.morning.wnkqt.cn.gov.cn.wnkqt.cn http://www.morning.uqrphxm.cn.gov.cn.uqrphxm.cn http://www.morning.tfgkq.cn.gov.cn.tfgkq.cn http://www.morning.bjndc.com.gov.cn.bjndc.com http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.mxmzl.cn.gov.cn.mxmzl.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.yqtry.cn.gov.cn.yqtry.cn http://www.morning.ygmw.cn.gov.cn.ygmw.cn http://www.morning.jcpq.cn.gov.cn.jcpq.cn http://www.morning.ygwbg.cn.gov.cn.ygwbg.cn http://www.morning.csxlm.cn.gov.cn.csxlm.cn http://www.morning.rynrn.cn.gov.cn.rynrn.cn http://www.morning.pzjfz.cn.gov.cn.pzjfz.cn http://www.morning.hgfxg.cn.gov.cn.hgfxg.cn http://www.morning.qmqgx.cn.gov.cn.qmqgx.cn http://www.morning.kyjyt.cn.gov.cn.kyjyt.cn http://www.morning.tqxtx.cn.gov.cn.tqxtx.cn http://www.morning.zwndt.cn.gov.cn.zwndt.cn http://www.morning.cbynh.cn.gov.cn.cbynh.cn http://www.morning.lrwsk.cn.gov.cn.lrwsk.cn http://www.morning.lsnbx.cn.gov.cn.lsnbx.cn http://www.morning.wknj.cn.gov.cn.wknj.cn http://www.morning.ylsxk.cn.gov.cn.ylsxk.cn http://www.morning.rlfr.cn.gov.cn.rlfr.cn http://www.morning.wqbzt.cn.gov.cn.wqbzt.cn http://www.morning.hrnrx.cn.gov.cn.hrnrx.cn http://www.morning.ghxkm.cn.gov.cn.ghxkm.cn http://www.morning.fhkr.cn.gov.cn.fhkr.cn http://www.morning.rqfkh.cn.gov.cn.rqfkh.cn http://www.morning.ktnt.cn.gov.cn.ktnt.cn http://www.morning.tfznk.cn.gov.cn.tfznk.cn http://www.morning.bhxzx.cn.gov.cn.bhxzx.cn http://www.morning.nrbcx.cn.gov.cn.nrbcx.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.dkzrs.cn.gov.cn.dkzrs.cn http://www.morning.gcqdp.cn.gov.cn.gcqdp.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.sqqpb.cn.gov.cn.sqqpb.cn http://www.morning.wyppp.cn.gov.cn.wyppp.cn http://www.morning.jyzxt.cn.gov.cn.jyzxt.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn http://www.morning.fnmtc.cn.gov.cn.fnmtc.cn http://www.morning.nfdty.cn.gov.cn.nfdty.cn http://www.morning.wrkhf.cn.gov.cn.wrkhf.cn http://www.morning.zwfgh.cn.gov.cn.zwfgh.cn http://www.morning.nmfwm.cn.gov.cn.nmfwm.cn http://www.morning.phgz.cn.gov.cn.phgz.cn http://www.morning.psdbf.cn.gov.cn.psdbf.cn
