文章目录提示：该文章主要整理复习考研时使用的一些基本算法
- 一、排序算法
- 1. 快速排序
- 2.直接插入排序
- 3.冒泡排序
- 4.希尔排序
- 5.简单选择排序
- 6. 归并排序
- 7.堆排序
- 二、查找
- 1.折半查找法
- 2.顺序查找
- 三、常见算法问题
- 1.水仙花数
- 2.回文问题
提示：以下是本篇文章正文内容，下面案例可供参考
一、排序算法 1. 快速排序快速排序的原理是设置一个基准数，分别从数组开头找大于基准数的数，数组末尾找小于基准数的数（即不合顺序数）然后将基准数归位，使基准数前面的数都比它小，基准数后面的数都比他大。再利用归位好的基准数将数组切分为两部分，再分别对前半部和后半部的数组进行相同的处理。
void QuickSort(int arr[],int begin,int end){
if(begin>end) //序列不合法
return ;
int temp = arr[begin]; //设置哨兵
int i = begin;
int j = end;
if(i!=j){
while(arr[j]>temp && ij){
swap(arr[i],arr[j]);
}
}
swap(temp,arr[i]); //基点归位
QuickSort(arr,begin,i-1);
QuickSort(arr,i+1,end);
}
2.直接插入排序
此处使用的是哨兵模式的插入排序，将数组的第一格设置为不存储数值的哨兵单元，可以用来暂时缓存数据，所以开始i循环是从2开始。当存在数组序列值的大小出错时，循环遍历当前数值之前的单位，找到可以插入的地方，将哨兵中的缓存值插入。
void InsertSort(int a[],int n){ //带哨兵模式
int i,j;
for(i=2; i<=n; i++)
if(a[i]
a[0] = a[i];
for(j=i-1; a[0]
3.冒泡排序
相邻两个数据相互对比进行交换
void BubbleSort(int a[],int n){
for(int i=0; i
bool flag = false;
for(int j=n-1; j>i; j--)
if(a[j-1]>a[j]){
swap(a[j-1],a[j]);
flag = true;
}
if(flag == flase)
return ;
}
}
4.希尔排序
算是一种插入排序的改进法
void ShellSort(int a[],int n){
int d,i,j; //增量d
for(d=n/2;d>=1;d=d/2)
for(i=d+1;i<=n;++i)
if(a[i]
a[0]=a[i];
for(j=i-d;j>0&&a[0]
5.简单选择排序
遍历找到数组中最小的数值，将其放在首位，其次找到第二小的数值，放在第二位，以此类推。
void SelectSort(int a[], int n){
for(int i=0; i
int min = i; //设i为最小值位置
for(int j=i+1; i
6. 归并排序
将两个有序数组合并成一个数组进行排序。
int *b = (int *)malloc(n*sizeof(int)); //创建一个大型的数组供给两个数组的合并存储
void Merge(int a[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++)
b[k] = a[k]; //将两个数组合并起来放到B数组空间中
for(i = low,j = mid+1,k = i; i<=mid && j<=high; k++){ //i的范围为第一个数组的范围（low,mid);j的范围为第二个数组的范围（mid+1，high）
if(b[i]
a[k]=b[i++];
}
else{
a[k]=b[j++]; //比较两个数组的同步数值，将小的放在原数组中进行排序
}
}
while(i<=mid)
a[k++]=b[i++];
while(j<=high)
a[k++]=b[j++];
}
void MergeSort(int a[],int low,int high){
if(low //当数组合法时，可以进行归并排序
int mid = (low+high)/2;
MergeSort(a,low,mid);
MergeSort(a,mid+1;high);
Merge(a,low,mid,high);
}
}
7.堆排序
首先构造大根堆，然后通过新插入的数据上升，低端的数据下降来形成堆排序。
void HeadAdjust(int a[], int k, int len){
a[0] = a[k];
for(int i=2*k; i<=len; i*=2){
if(i=a[i])
break;
else{
a[k] = a[i];
k=i;
}
}
a[k] = a[0];
}
void HeapSort(int a[],int len){
BuildMaxHeap(a,len);
for(int i=len; i>1; i--){
swap(a[i],a[1]);
HeadAdjust(a,1,i-1);
}
}
二、查找
1.折半查找法
也叫二分查找法
int search(int a[],int low,int high,int k){
int mid;
while(low
mid=(low+high)/2;
if(a[mid==k]){
return mid;
}
else if(a[mid]>k){
high = mid-1;
}
else{
low=mid+1;
}
}
return 0;
}
2.顺序查找
也叫线性查找法
代码如下（示例）：
typedef sturct{
ElemType *elem;
int TableLen;
}SSTable;
int Search(SSTable ST,ElemType key){
int i;
for(i=0; i
三、常见算法问题
1.水仙花数
求100-999之间的水仙花数
int main()
{
int hun, ten, ind, n;
printf("result is:");
for( n=100; n<1000; n++ )
{
hun = n / 100;
ten = (n-hun*100) / 10;
ind = n % 10;
if(n == hun*hun*hun + ten*ten*ten + ind*ind*ind)
printf("%d ", n);
}
printf("n");
return 0;
}
2.回文问题
void main(){
char s[100]; // 存放输入的字符串
int i, j, n;
printf("输入字符串：");
gets(s);
n=strlen(s);
for(i=0,j=n-1;i=j)
printf("是回文串n");
else
printf("不是回文串n");
}
