- @[toc]
- 一、排序算法
- 1、插入排序
- 1)直接插入排序
- 2)折半插入排序
- 3)希尔排序
- 2、交换排序
- 1)起泡法
- 2)快速排序
- 3、选择排序
- 1)简单选择排序
- 2)堆排序(大根堆)
- 4、归并排序
- 二、查找
- 1、顺序查找
- 2、二分查找
- 三、数值转换
- 1、十进制转二、四、八，十六进制：
- 2、十六进制转二、四、八，十进制:
- 四、串
- 1、求给定一个串的
- 1)next值(:next[0]=-1)
- 2)nextval值
- 2、BF算法
- 3、KMP算法
- 五、学过的一些简单程序
- 1、判断素数
- 2、求N以内的素数的和（包括N）
- 3、判断闰年
- 4、阶乘（递归，非递归）
- 1)递归
- 2)非递归
void InsertSort(int arr[], int n){
int i,j;
for(i=2;i<=n;i++){
if(arr[i]0&&arr[j]>arr[0];j--){
arr[j+1]=arr[j];
}
arr[j+1] = arr[0];
}
}
}
InsertSort
2)折半插入排序 void BInsertSort(int arr[], int n){
int i,j,low,height,mid; for(i=2;i<=n;i++){
if(arr[i]arr[0]) height = mid-1;
else low = mid+1;
}
for(j=i-1;j>height;j--){
arr[j+1]=arr[j];
}
arr[j+1] = arr[0];
}
}
}
BInsertSort
3)希尔排序void ShellInsert(int arr[],int n){
for(int gap = (n+1)/2;gap>0;gap/=2){
for(int i=gap;i<=n;i++){
int j = i;
while(j-gap>0&&arr[j]
ShellInsert
2、交换排序 1)起泡法void BubbleSort(int arr[],int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
if(arr[j]>arr[j+1]){
arr[0] = arr[j];
arr[j] = arr[j+1];
arr[j+1] = arr[0];
}
}
}
}
BubbleSort
2)快速排序int Partition(int arr[] ,int low ,int high){
int tmp = arr[low];
while(low=tmp){
high--;
}
arr[low]=arr[high];
while(low
QuickSort
3、选择排序
1)简单选择排序
void SelectSort(int arr[] ,int n){
int minValue;
for(int i=1;iarr[j]){
minValue=j;
}
}
if(minValue!=i){
arr[0] = arr[i];
arr[i] = arr[minValue];
arr[minValue] = arr[0];
}
}
}
SelectSort
2)堆排序(大根堆)
void HeapAdjust(int arr[],int s,int m){
int rc = arr[s];
for(int j=2*s;j<=m;j*=2){
if(j0;--i){
HeapAdjust(arr,i,n);
}
}
void HeapSort(int arr[],int n){
CreatHeap(arr,n);
for (int i=n;i>1;--i){
arr[0] = arr[1];
arr[1] = arr[i];
arr[i] = arr[0];
HeapAdjust(arr,1,i-1);
}
}
HeapSort
4、归并排序
void Merge(int arr[] ,int left ,int mid ,int right ,int temp[]){
int i=left;
int j = mid+1;
int t = 0;
while(i<=mid&&j<=right){
temp[t++]=arr[i]
MSort
二、查找
1、顺序查找
int Find(int arr[],int target,int length){
for(int i=0;i
Find
2、二分查找
int Find(int arr[],int target,int length){
int left = 0,right = length-1;
while(left<=right){
int mid = left+(right-left)/2;
if(arr[mid]==target) return mid;
if(arr[mid]>target) right = mid -1;
else left = mid+1;
}
return -1;
}
BFind
三、数值转换
1、十进制转二、四、八，十六进制：
#include
#include
#include "SeqStack.h"
using namespace std;
int main(){
int num;
SeqStack b;
cout<<"输入一个十进制数"<>num;
// 十进制转二进制
int num2 = num;
while(num2){
b.Push(num2%2);
num2/=2;
}
cout<<"该十进制数对应的二进制数为：";
while(!b.Empty()){
cout< c;
char sixteen(int);
int k = 0;
int num16 = num;
while(num16){
c.Push(sixteen(num16%16));
num16/=16;
k++;
}
cout<<"该十进制数对应的十六进制数为：";
while(!c.Empty()){
cout<
SeqStack.h
2、十六进制转二、四、八，十进制:
#include
#include
#include
#include "SeqStack.h"
using namespace std;
int main()
{
int n=0,k,j=0;char a[20];
string s;
SeqStack b;
cout<<"输入一个十六进制数"<>s;
k=s.size();//字符串的长度
//将十六进数转化成十进制数
while(k){
switch (s[s.size()-k]){
case 'A':n=n+pow(16,k-1)*10; break;
case 'B': n=n+pow(16,k-1)*11; break;
case 'C': n=n+pow(16,k-1)*12; break;
case 'D': n=n+pow(16,k-1)*13; break;
case 'E': n=n+pow(16,k-1)*14; break;
case 'F': n=n+pow(16,k-1)*15; break;
default: n=n+pow(16,k-1)*(s[s.size()-k]-'0');break;
}
k--;
}
cout<<"该十六进制数转化为十进制数为：" <
SeqStack.h
其它进制可以由十进制转换
四、串
1、求给定一个串的
1)next值(:next[0]=-1)
void GetNext(string &str, int next[]){
next[0] = -1;
int i = 0, j = -1;
while (i < str.size()-1){//前一位比较完就行了，最后一位比的话就越界了
if (j == -1 || str[i] == str[j]){
++i;
++j;
next[i] = j;
}
else{
j = next[j];
}
}
}
Next
2)nextval值
void GetNextval(string &str, int nextval[]){
nextval[0]=-1;
int i = 0, j = -1;
while(i < str.size()-1){
if (j == -1 || str[i] == str[j]){
++i;
++j;
if(str[i]!=str[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
}
nextval
2、BF算法
int BF(string &M, string &N)
{
int i=0, j=0;
while (M[i] != ' ' && N[j] != ' ')
{
if (M[i] == N[j])
{
i++; j++;
}
else
{
i = i - j + 1;
j = j - j; //也就是j=0
}
}
if (N[j] == ' ')
{
return (i - j);
}
else
return -1;
}
BF
3、KMP算法
int KMP(string &str1, string &str2,int next[])//str1表示主串，str2表示模式串
{
int m = str1.size(), n = str2.size();
GetNext(str2, next);//求解next数组
int i = 0, j = 0;
while (i < m && j < n) {
if (j == -1 || str1[i] == str2[j]) {
++i;
++j;
}
else {
j = next[j];
}
}
if (j == n) {
return i - j;//返回模式串在主串的起始位置
}
else {
return -1;//没有找到返回-1
}
}
KMP
五、学过的一些简单程序
1、判断素数
#include
using namespace std;
int main(){
int n, i;
bool isPrime = true;
cout << "输入一个正整数: ";
cin >> n;
for(i = 2; i <= n / 2; ++i){
if(n % i == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
cout << "是素数";
else
cout << "不是素数";
return 0;
}
2、求N以内的素数的和（包括N）
#include
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
for(int i = 2; i <= n; ++i)
{
int k;
for(k = 2; k < n; ++k)
if(i%k == 0) break;//如果找到一个因子k能将i除尽则跳出
if(k == i)//表明没有找到任何一个符合要求的因子k，所以为素数
sum+=i;
}
cout<
3、判断闰年
#include
using namespace std;
int main()
{
int n;
cout << "cinyear:";
cin >> n;
if (n % 100 == 0 && n % 400 == 0 || n % 100 != 0 && n % 4 == 0)
cout << "runnian" << endl;
else
cout << "feirun" << endl;
return 0;
}
4、阶乘（递归，非递归）
1)递归
#include
using namespace std;
int main(){
int fac(int);
int i,n;
cout<<"Enter number: ";
cin>>n;
cout<<"Factorial of "<
2)非递归
#include
using namespace std;
int main()
{
int i,fac,n;
cout<<"Enter number: ";
cin>>n;
for(i=1,fac=1;i<=n;++i)
{
fac=i*fac;
}
cout<<"Factorial of "<
