C++排序和查找
·
1.判断素数
思路：如果n<=1,不是素数
如果n==2，是素数
如果n是偶数，n%2==0,不是素数
如果n是奇数，i从3开始，i<=sqrt(n),i它们之间的奇数，n%i==0,不是素数
#include<bits/stdc++.h>
using namespace std;
// 函数注释：明确功能、参数、返回值
// 功能：判断整数n是否为素数
// 参数：n - 待判断的整数
// 返回：true=素数，false=非素数
bool isPrime(int n) { // 函数名语义化（prime→isPrime）
if (n <= 1) return false; // 小于等于1：非素数
if (n == 2) return true; // 2是唯一偶素数
if (n % 2 == 0) return false;// 其他偶数：非素数
// 优化：用i <= n/i替代sqrt(n)，避免浮点精度/溢出问题
for (int i = 3; i <= n / i; i += 2) {
if (n % i == 0) return false; // 有因数→非素数
}
return true; // 无因数→素数
}
int main() {
int n;
cout << "请输入要判断的数n：" << endl; // 提示更友好
cin >> n;
bool result = isPrime(n);
// 简化判断（==true可省略，语义等价）
if (result) {
cout << n << "是素数" << endl; // 输出带数值，更清晰
} else {
cout << n << "不是素数" << endl;
}
return 0;
}
素数（也叫质数）是指 大于 1 的自然数，且满足：👉 除了 1 和它自身外，不能被任何其他自然数整除（即没有除 1 和自身以外的因数）。
2.斐波那契数列
fib(0)=0,fib(1)=1,
fib(n)=fib(n-1)+fib(n-2)
#include<bits/stdc++.h>
using namespace std;
int fib(int n)
{
if(n==0) return 0;
if(n==1) return 1;
else
{
return fib(n-1)+fib(n-2);
}
}
int main()
{
int n;
cin>>n;
int result=fib(n);
cout<<result;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
// 迭代版：高效计算斐波那契数列第n项
long long fib(int n) { // 用long long避免溢出
// 异常输入处理
if (n < 0) {
cout << "错误：n不能为负数！" << endl;
return -1; // 返回异常标记
}
// 基准条件
if (n == 0) return 0;
if (n == 1) return 1;
// 迭代计算：仅遍历一次，无重复计算
long long a = 0, b = 1, res; // a=F(0), b=F(1)
for (int i = 2; i <= n; i++) {
res = a + b;
// 溢出检测（可选）
if (res < 0) { // long long溢出会出现负数
cout << "警告：数值超出long long范围！" << endl;
return -1;
}
a = b; // a更新为前一项
b = res; // b更新为当前项
}
return b;
}
int main() {
int n;
cout << "请输入要计算的斐波那契数列项数n：" << endl;
cin >> n;
long long result = fib(n);
if (result != -1) { // 仅输出有效结果
cout << "斐波那契数列第" << n << "项为：" << result << endl;
}
return 0;
}3.排序
#include <bits/stdc++.h>
using namespace std;
int main()
{
// 请在此输入您的代码
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}1.冒泡排序
#include<bits/stdc++.h>
using namespace std;
// 冒泡排序函数（逻辑完全正确，无需修改）
void bubbleSort(int arr[], int n)
{
for(int i=0; i<n-1; i++)
{
for(int j=0; j<n-i-1; j++)
{
if(arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]); // 升序交换逻辑正确
}
}
}
}
int main()
{
int n; // 第一步：先声明n，再使用
cout << "请输入数组长度n：" << endl;
cin >> n;
// 第二步：用已声明的n创建vector动态数组
vector<int> arr(n);
cout << "请输入" << n << "个整数（空格分隔）：" << endl;
for(int i=0; i<n; i++)
{
cin >> arr[i];
}
// 第三步：传vector底层数组地址（&arr[0]），匹配bubbleSort的参数要求
bubbleSort(&arr[0], n);
// 输出排序结果
cout << "排序后的数组：" << endl;
for(int i=0; i<n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
2.选择排序
选择排序的核心：先遍历找到最小值的索引，再退出内层循环后，将最小值与当前轮起始位置（i）交换
#include<bits/stdc++.h>
using namespace std;
void selectSort(int arr[],int n)
{
for(int i=0;i<n;i++)
{
int min=i;
for(int j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
{
min=j;
}
}
swap(arr[min], arr[i]);
}
}
int main()
{
int n;
cout<<"请输入你要排序的个数："<<endl;
cin>>n;
vector<int> arr(n);
cout<<"请输入你要排的数："<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
selectSort(arr.data(),n);
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}3.插入排序
#include<bits/stdc++.h>
using namespace std;
void insertSort(int a[],int n)
{
for(int i=1;i<n;i++)
{
int k=a[i];
int j=i-1;
while(j>=0&&a[j]>k)
{
a[j+1]=a[j];
j--;
}
a[j+1]=k;
}
}
int main()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
insertSort(a.data(),n);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}4. 合并排序数组
问题描述
给定排序数组 A 和 B，实现一个算法将 B 按排序顺序合并到 A 中。介绍如下：
数组 A 和 B 的均为排序数组，数字按从小到大排列。
数组 A 的的长度为 nn，其中前 mm 个为数字，后 n−mn−m 个为
None；数组 B 的长度为 n−m。需要将数组 B 的数字依次添加到数组 A 中，添加元素后 A 的依旧是排序数组。
输入描述
第一行为两个数字 n,m(1<n,m<1000)n,m(1<n,m<1000)，空格隔开，含义如题干所示。
第二行为 mm 个数字，数组 A 中的前 mm 项元素。
第三行为 n−mn−m 个数字，数组 B 中的元素。
输出描述
输出一行，为合并后的 A 数组。
#include <bits/stdc++.h>
using namespace std;
int main()
{
// 请在此输入您的代码
int n,m;
cin>>n>>m;
vector<int>a(n);
vector<int>b(n-m);
for(int i=0;i<m;i++)
{
cin>>a[i];
}
for(int i=0;i<n-m;i++)
{
cin>>b[i];
}
for(int i=0;i<n-m;i++)
{
a[m+i]=b[i];
}
sort(a.begin(),a.end());
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}5.快速排序
#include<bits/stdc++.h>
using namespace std;
int a[5]={2,4,7,5,1};
void quick_sort(int left,int right)
{
if(left>right) return;
int i=left;
int j=right;
int mid=(left+right)/2;
int p=a[mid];
while(i<=j)
{
while(a[i]<p) i++;
while(a[j]>p) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(left<=j) quick_sort(left,j);
if(i<=right) quick_sort(i,right);
}
int main()
{
quick_sort(0,4);
for(int i=0;i<5;i++)
{
cout<<a[i]<<" ";
}
return 0;
}4.查找
1.线性查找Linear Search
从第一个开始一个一个查找，直到找到目标或者检查完所有的元素O(n)
2.二分查找Binary Search
数据集合具有某种有序性，通过每次检查中间元素，排除一半不可能的查找区间O(logn)
#include<bits/stdc++.h>
using namespace std;
int binary_search(int a[],int value,int n)
{
int left=0,right=n-1;
while(left<=right)
{
int mid=(left+right)/2;
if(a[mid]==value)
return mid;
else if(a[mid]>value)
right=mid-1;
else
left=mid+1;
}
return -1;
}
int main()
{
int n, value;
vector<int> a;
cin>>n>>value;
a.resize(n); // 动态调整数组长度为n
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(), a.end());
cout<<binary_search(a.data(),value,n)<<endl;
return 0;
}3.哈希查找Hash Lookup
将要查找的目标直接映射到一个存储地址上，利用额外的存储空间来缩短查找时间O(1)
5.无重复字符的最长字串
首先定义一个集合，来判断窗口中的字符是否重复unordered_set<char> u_set;
窗口包括重复的字符，移动左边界把重复的字符给消掉u_set.erase()；
否则把右边界的元素放入哈希表，u_set.insert()
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left=0,right=0,length=0,maxlength=0;
unordered_set<char>charSet;
for(;right<s.length();right++)
{
while(left<=right&&charSet.count(s[right]))
{
length--;
charSet.erase(s[left]);
left++;
}
charSet.insert(s[right]);
length++;
maxlength = max(length, maxlength);
}
return maxlength ;
}
};
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)