O(n)时间内对[0..n^-1]之间的n个数排序

2024-09-08 14:32
文章标签 时间 排序 个数 之间 ..

本文主要是介绍O(n)时间内对[0..n^-1]之间的n个数排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序

思路

把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序

代码

#include <iostream>
#include <cmath>
using namespace std;int n, radix, length_A, digit = 2;
void Print(int *A, int start, int end)
{int i;for(i = start; i <= end; i++){if(i == start)cout<<'{';else cout<<' ';cout<<A[i];}cout<<'}'<<endl;
}
//基数排序调用的稳定排序
void Stable_Sort(int *A, int *B, int k, int d)
{int i, j;//将C数组初始化为0,用于计数int *C = new int[k+1];for(i = 0; i <= k; i++)C[i] = 0;int *D = new int[length_A+1];for(j = 1; j <= length_A; j++){//D[j]表示第[j]个元素的第i位数字D[j] = A[j] % (int)pow(radix*1.0, d) / (int)pow(radix*1.0, d-1);//C[j]表示数字D[j]在数组A中出现的次数C[D[j]]++;}//C[i]表示所以<=i的数字出现过的次数for(i = 1; i <= k; i++)C[i] = C[i] + C[i-1];//初始化B为0,B用于输出排序结果for(i = 1; i <= length_A; i++)B[i] = 0;for(j = length_A; j >= 1; j--){//如果<=D[j]的数字的个数是x,那么排序后A[j]应该出现在第x个位置,即B[x]=A[j]B[C[D[j]]] = A[j];C[D[j]]--;}delete []C;delete []D;
}
//基数排序
void Radix_Sort(int *A, int *B)
{int i, j;//依次对每一位进行排序,从低位到高位for(i = 1; i <= digit; i++){Stable_Sort(A, B, radix-1, i);//输入的是A,输出的是B,再次排序时要把输出数据放入输出数据中for(j = 1; j <= length_A; j++)A[j] = B[j];}
}int main()
{cin>>n;length_A = n;int *A = new int[n+1];int *B = new int[n+1];bool flag[1000]  = {0};int i;//生产n个随机的数据范围在0到n^-1之间for(i = 1; i <= n; i++){do{A[i] = rand() % (n*n);}while(flag[A[i]]);flag[A[i]] = 1;}Print(A, 1, n);radix = n;Radix_Sort(A, B);Print(A, 1, n);return 0;
}

这篇关于O(n)时间内对[0..n^-1]之间的n个数排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148368

相关文章

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、