网站怎么做成手机版,专业网站建设明细报价表,更改文章标题字体wordpress,在自己的网站上做查分系统计数排序就是一种时间复杂度为 O(n) 的排序算法#xff0c;该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时#xff0c;它的复杂度为 O(nk)#xff08;其中 k 是整数的范围大小#xff09;。
伪计数排序
我们需要对一列数组排序#xff0c;这个数…计数排序就是一种时间复杂度为 O(n) 的排序算法该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时它的复杂度为 O(nk)其中 k 是整数的范围大小。
伪计数排序
我们需要对一列数组排序这个数组中每个元素都是 [1,9] 区间内的整数。那么我们可以构建一个长度为 9 的数组用于计数计数数组的下标分别对应区间内的 9 个整数。然后遍历待排序的数组将区间内每个整数出现的次数统计到计数数组中对应下标的位置。最后遍历计数数组将每个元素输出输出的次数就是对应位置记录的次数。
void countingSort9(std::vectorint arr) {// Create an array of length 9, where indices 0-8 correspond to numbers 1-9//建立长度为 9 的数组下标 0~8 对应数字 1~9std::vectorint counting(9, 0);// Iterate through each element in the input array//建立长度为 9 的数组下标 0~8 对应数字 1~9for (int element : arr) {// Count the occurrences of each integer and store them in the counting array//建立长度为 9 的数组下标 0~8 对应数字 1~9counting[element - 1];}int index 0;// Iterate through the counting array and output each element//遍历计数数组将每个元素输出for (int i 0; i 9; i) {// Output each element as many times as it appears in the input//遍历计数数组将每个元素输出while (counting[i] ! 0) {arr[index] i 1;counting[i]--;}}
}算法非常简单但这里的排序算法 并不是 真正的计数排序。因为现在的实现有一个非常大的弊端排序完成后arr 中记录的元素已经不再是最开始的那个元素了他们只是值相等但却不是同一个对象。
在纯数字排序中这个弊端或许看起来无伤大雅但在实际工作中这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性但这份算法将被排序对象的其他属性都丢失了。
伪计数排序 2.0
对于这个问题我们很容易想到一种解决方案在统计元素出现的次数时同时把真实的元素保存到列表中输出时从列表中取真实的元素。
void countingSort9(std::vectorint arr) {// Create an array of length 9, where indices 0-8 correspond to numbers 1-9// 建立长度为 9 的数组下标 0~8 对应数字 1~9std::vectorint counting(9, 0);// Record the actual elements at each index, using a queue to maintain stability//记录每个下标中包含的真实元素使用队列可以保证排序的稳定性std::unordered_mapint, std::queueint records;// Iterate through each element in the input array//遍历 arr 中的每个元素for (int element : arr) {// Count the occurrences of each integer and store them in the counting array// 将每个整数出现的次数统计到计数数组中对应下标的位置counting[element - 1];// Initialize a queue for each unique element if it doesnt exist//初始化每个唯一元素的队列如果不纯在if (records.find(element - 1) records.end()) {records[element - 1] std::queueint();}// Add the element to the corresponding queue//将元素添加到相应的队列records[element - 1].push(element);}int index 0;// Iterate through the counting array and output each element// 遍历计数数组将每个元素输出for (int i 0; i 9; i) {// Output the element as many times as it appears in the input//输出的次数就是对应位置记录的次数while (counting[i] ! 0) {// Output the actual element from the queue//输出的次数就是对应位置记录的次数arr[index] records[i].front();records[i].pop();counting[i]--;}}
}在这份代码中我们通过队列来保存真实的元素计数完成后将队列中真实的元素赋到 arr 列表中这就解决了信息丢失的问题并且使用队列还可以保证排序算法的稳定性。
但是这也不是 真正的计数排序计数排序中使用了一种更巧妙的方法解决这个问题
真正的计数排序
举个例子班上有 10 名同学他们的考试成绩分别是7,8,9,7,6,7,6,8,6,6他们需要按照成绩从低到高坐到 09 共 10 个位置上。 用计数排序完成这一过程需要以下几步 1.第一步仍然是计数统计出: 4名同学考了 6 分3名同学考了 7分2名同学考了 8 分1名同学考了9分; 2.然后从头遍历数组: 第一名同学考了7分共有 4个人比他分数低所以第一名同学坐在 4 号位置(也就是第5个位置) 3.第二名同学考了 8 分共有 7 个人 (4 3) 比他分数低所以第二名同学坐在 7 号位置; 4.第三名同学考了 9分共有 9 个人 (4 3 2)比他分数低所以第三名同学坐在 9 号位置 5.第四名同学考了7分共有 4 个人比他分数低并且之前已经有一名考了 7分的同学坐在了 4 号位置所以第四名同学坐在5号位置。 6…依次完成整个排序
区别就在于计数排序并不是把计数数组的下标直接作为结果输出而是通过计数的结果计算出每个元素在排序完成后的位置然后将元素赋值到对应位置
void countingSort(std::vectorint arr) {// Check for empty or single-element array//判空及防止数组越界if (arr.empty() || arr.size() 1) return;// Find the maximum and minimum values in the array//找到最大值最小值int max arr[0];int min arr[0];for (int i 1; i arr.size(); i) {if (arr[i] max) max arr[i];else if (arr[i] min) min arr[i];}// Determine the counting array size//确定计数范围int range max - min 1;// Create a counting array of length range//建立长度为 range 的数组下标 0~range-1 对应数字 min~maxstd::vectorint counting(range, 0);// Iterate through the input array and count the occurrences of each element//遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置这里需要将每个元素减去 min才能映射到 0range-1 范围内counting[element - min];}// Calculate the cumulative counts//记录前面比自己小的数字的总数int preCounts 0;for (int i 0; i range; i) {// 当前的数字比下一个数字小累计到 preCounts 中preCounts counting[i];// 将 counting 计算成当前数字在结果中的起始下标位置。位置 前面比自己小的数字的总数。counting[i] preCounts - counting[i];}// Create a result arraystd::vectorint result(arr.size());// Place elements in the result array according to their countsfor (int element : arr) {// counting[element - min] 表示此元素在结果数组中的下标result[counting[element - min]] element;// 更新 counting[element - min]指向此元素的下一个下标counting[element - min];}// Copy the sorted result back to the original array//将结果赋值返回arrfor (int i 0; i arr.size(); i) {arr[i] result[i];}
}倒序遍历的计数排序
void countingSort(std::vectorint arr) {// Check for empty or single-element array//判空及防止数组越界if (arr.empty() || arr.size() 1) return;// Find the maximum and minimum values in the array//找到最大值最小值int max arr[0];int min arr[0];for (int i 1; i arr.size(); i) {if (arr[i] max) max arr[i];else if (arr[i] min) min arr[i];}// Determine the counting array size//确定计数范围int range max - min 1;// Create a counting array of length range//建立长度为 range 的数组下标 0~range-1 对应数字 min~maxstd::vectorint counting(range, 0);// Iterate through the input array and count the occurrences of each element//遍历 arr 中的每个元素for (int element : arr) {// 将每个整数出现的次数统计到计数数组中对应下标的位置这里需要将每个元素减去 min才能映射到 0range-1 范围内counting[element - min];}//每个元素在结果数组中的最后一个下标位置 前面比自己小的数字的总数 自己的数量 - 1。我们将 counting[0] 先减去 1后续 counting 直接累加即可//记录前面比自己小的数字的总数counting[0]--;for (int i 1; i range; i) {// 将 counting 计算成当前数字在结果中的最后一个下标位置。位置 前面比自己小的数字的总数 自己的数量 - 1// 由于 counting[0] 已经减了 1所以后续的减 1 可以省略。counting[i] counting[i-1];}// Create a result arraystd::vectorint result(arr.size());// 从后往前遍历数组通过 counting 中记录的下标位置将 arr 中的元素放到 result 数组中for (int i arr.size() - 1; i 0; i--) {// counting[arr[i] - min] 表示此元素在结果数组中的下标result[counting[arr[i] - min]] arr[i];// 更新 counting[arr[i] - min]指向此元素的前一个下标counting[arr[i] - min]--;}// Copy the sorted result back to the original array//将结果赋值返回arrfor (int i 0; i arr.size(); i) {arr[i] result[i];}
}
