C语言与Object-C中的常用经典排序算法
2017-03-04 本文已影响75人
KingLionsFrank
一提到算法，想必各位童鞋都不陌生，但是也很头疼，因为算法会出没在编程领域的各个专业方向，但是做算法对专业能力的要求又很高，思想很绕，一个不小心就被算法折腾的晕头转向了，所以今天就整理一下C语言和Object-C中的一些经典算法，这些算法都是许多人的智慧结晶,也是编程中常用的算法,这里面包含了众多算法思想,掌握这些算法,对于学习更高级的、更难的算法都会有很大帮助
几种常见算法排序最好最坏比较次数可参考：
http://blog.csdn.net/u013176681/article/details/41786263
C语言经典算法题
1、从键盘输入一个字符串，将其中的大写字母变小写字母，小写字母变大写字母，并输出 。
#include<stdio.h>
void main()
{
int i=0;
char a[100],c;
printf("请输入字符串的内容:\t");
do{
scanf("%c",&a[i]);
c = a[i];
i++;
}while(c != '\n');
a[i] = '\0';
i=0;
printf("输入字符串的内容为:\t");
while(a[i] != '\0')
{
printf("%c",a[i]);
i++;
}
printf("转换后字符串的内容为:\t");
i = 0;
while(a[i] != '\0')
{
c=a[i];
if(c >= 'a' && c <= 'z')
a[i] -= 32;
else if(c >= 'A' && c <= 'Z')
a[i] += 32;
printf("%c",a[i]);
i++;
}
}
2、 把一个整数按大小顺序插入已排好序的数组中.
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,p,q,s,n,a[11]={127,3,6,28,54,68,87,105,162,18};
for(i=0;i<10;i++)
{ p=i;q=a[i];
for(j=i+1;j<10;j++)
if(q<a[j]) {p=j;q=a[j];}
if(p != i)
{
s=a[i];
a[i]=a[p];
a[p]=s;
}
printf("%d ",a[i]);
}
printf("\ninput number:\n");
scanf("%d",&n);
for(i=0;i<10;i++)
if(n>a[i])
{for(s=9;s>=i;s--) a[s+1]=a[s];
break;}
a[i]=n;
for(i=0;i<=10;i++)
printf("%d ",a[i]);
printf("\n");
getch();
}
3.求水仙花数...
【释义】输入一个三位数，判断是否事一个水仙花数。水仙花数是指3位数的各位数字的立方和等于这个3位数本身。例如，153=111+555+333
#include<stdio.h>
#include<conio.h>
void main()
{
int i,n,x1,x2,x3,sum;
for(i=100;i<1000;i++)
{
n=i;
x1=n%10;
x2=n/10%10;
x3=n/100;
sum=x1*x1*x1+x2*x2*x2+x3*x3*x3;
if(sum==n)
printf("%d is a shuixianhua number!\n",i);
}
}
4.从键盘输入一个字符串与一个指定字符，将字符串中出现的指定字符全部删除.
#include "stdio.h"
#include "conio.h"
#include "string.h"
void prochar(char *str,char c)
{
char *p;
for(p=str;*p!='\0';p++)
if(*p!=c)
*str ++= *p;
*str = '\0';
}
void main()
{
char str[80],char_c;
printf("请输入字符串：");
gets(str);
printf("请输入要删除的指定字符：");
scanf("%c",&char_c);
prochar(str,char_c);
puts(str);
printf("按任意键退出~");
getch();
}
5.杨辉三角
#include <stdio.h>
#include <conio.h>
#define N 10
void yanghui(int a[][N],int n);
void main()
{
int i,j,n,b[N][N];
printf("【行数不能超过所定义的N的值】请输入行数：");
scanf("%d",&n);
yanghui(b,n);
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
printf("%-4d",b[i][j]);
printf("\n");
}
}
void yanghui(int a[][N],int n)
{
int i,j;
for(i=0;i<n;i++) /*生成三角形边上元素*/
{
a[i][0]=1; /*即：0列与i行i列的元素为1*/
a[i][i]=1;
}
for(i=2;i<n;i++)
for(j=1;j<i;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
}
6.从键盘上输入5个数,输出最大、最小元素的值以及它们的下标
#define N 5
#include <stdio.h>
void main()
{
int i,j,k,max,min;
static int a[5];
for(i=0;i<5;i++)
{printf("请输入第%d个数字：",i+1);
scanf("%d",&a[i]);
}
max=min=a[0];
j=k=0;
for(i=0;i<5;i++)
{
if(max<a[i]) {max=a[i];j=i;}
else if(min>a[i]) {min=a[i];k=i;}
}
printf("max:a[%d]=%d,min:a[%d]=%d",j,max,k,min);
}
7.求两个数的最小公倍数.
#include <stdio.h>
#include <conio.h>
int divisor(int a,int b)
{
int r;
while ((r=a%b)!=0)
{a=b;b=r;}
return b;
}
int multiple(int a,int b)
{
int d;
d=divisor(a,b);
return a*b/d;
}
void main()
{
int a,b,c;
printf("输入第一个数a:");
scanf("%d",&a);
printf("输入第二个数b:");
scanf("%d",&b);
c=multiple(a,b);
printf("a和b的最小公倍数c为:%d",c);
}
8.求两、三个数中较大者的函数
#include <stdio.h>
#include <conio.h>
int max(int,int,int);
void main()
{
int a,b,c,t;
printf("依次输入三个数，请输入第一个数:");
scanf("%d",&a);
printf("请输入第二个数:");
scanf("%d",&b);
printf("请输入第三个数:");
scanf("%d",&c);
t=max(a,b,c);
printf("最大的数为 :%d",t);
}
int max(int a,int b,int c)
{
int t;
if (a>b)
if (a>c)
t=a;
else
t=c;
else
if (b>c)
t=b;
else
t=c;
return t;
}
9.电文加密问题
[释义]已知电文加密规律为：将字母变成其后面的第4个字母，其它字符保持不变。例如a→e,A→E,W→A。
#include <stdio.h>
#include <conio.h>
void main()
{
clrscr();
char ch;
while ((ch=getchar())!='\n')
{
if ((ch>='a' && ch<='z') || (ch>='A' && ch<='Z'))
{
ch += 4; /*ch是字母，进行加密处理*/
if ((ch>'Z' && ch<'a') || (ch>'z'))
/*ch在加密后越界*/
ch -= 26;
}
printf("%c",ch);
}
}
10.冒泡排序法
【释义】：排序过程：
（1）比较第一个数与第二个数，若为逆序a[0]>a[1]，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上；
（2）对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置；
（3）重复上述过程，共经过n-1趟冒泡排序后，排序结束。
#include <stdio.h>
main()
{ int a[11],i,j,t;
printf("Input 10 numbers:
");
for(i=1;i<11;i++)
scanf("%d",&a[i]);
printf(" ");
for( j = 1 ; j <= 9 ; j++ )
for( i = 1 ; i <= 10 - j ; i++ )
if( a[i] > a[i + 1] )
{t = a[i]; a[i] = a[i + 1]; a[ i + 1] = t;}
printf("The sorted numbers:
");
for(i=1;i<11;i++)
printf("%d ",a[i]);
}
11.字符数组：（逆序排列）如：< ABCDE - EDCBA >.
【释义】把输入的字符串逆序排列，如输入ABCDE，输出为EDCBA.
#include<string.h>
int main()
{
char c,str[80];
int i,j;
printf("hu:");
scanf("%s",str); /* 也可以gets(str);puts(str); */
for( i = 0 , j = strlen(str)-1 ; i < j ; i++ , j-- )
{
c = str[i];
str[i] = str[j];
str[j] = c;
}
printf("Reversed string:%s",str);
return 0;
}
12.递归调用(求n的阶乘)
#include <stdio.h>
float fac(int n)
{
float f;
if(n<0)
{
printf("n<0,data error!");
}else if (n==0 || n==1)
{
f=1;
}else
f=fac(n-1)*n;
return(f);
}
int main()
{
int n,i;
float y=0;
printf("Input a integer number:");
scanf("%d",&n);
y=fac(n);
printf("%d! =%f",n,y);
return 0;
}
13.求1到n的阶乘的和.
#include <stdio.h>
float fac(int n)
{
float f;
if(n<0){
printf("n<0,输入有误！!");
}
else if(n==0||n==1){
f=1;
}
else{
f=fac(n-1)*n;
}
return(f);
}
int main()
{
int n, i;
float y=0;
printf("请输入一个数字:");
scanf("%d",&n);
for( i = 0;i <= n; i++ ){
y = y + fac(i);
}
printf("%d! =%f",n,y);
return 0;
}
OC中常用的排序算法
因为OC中的基本数据类型无法存放到数组中，所以如下示例使用NSNumber对象对数据进行处理
冒泡排序：
通过N-1次对剩余未排序元素中最大（小）元素的上浮来实现排序，上浮过程通过交换相邻元素实现。
#pragma - mark 冒泡排序
+ (void)buddleSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 1; i < array.count; i++) {
for (int j = 0; j < array.count - i; j++) {
if ([array[j] compare:array[j+1]] == NSOrderedDescending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
NSLog(@"排序中:%@",array);
}
}
}
选择排序：
通过N-1次将剩余未排序元素中最大（小）元素放置到数组尾部来实现排序。
+ (void)selectSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
int min_index;
for (int i = 0; i < array.count; i++) {
min_index = i;
for (int j = i + 1; j<array.count; j++) {
if ([array[j] compare:array[min_index]] == NSOrderedAscending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:min_index];
}
NSLog(@"排序中:%@",array);
}
}
}
插入排序：
插入排序使用的是增量（incremental）方法；在排好子数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；
#pragma - mark 插入排序
+ (void)inserSort:(NSMutableArray *)array
{
if(array == nil || array.count == 0){
return;
}
for (int i = 0; i < array.count; i++) {
NSNumber *temp = array[i];
int j = i-1;
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
[array replaceObjectAtIndex:j+1 withObject:array[j]];
j--;
NSLog(@"排序中:%@",array);
}
[array replaceObjectAtIndex:j+1 withObject:temp];
}
}
快速排序：
思想简单明了,核心精髓在于分割
1:选基数,假设每次都取最左边的为基数,并假设该基数是最小的(最终结果也是升序,倒序也可以效仿)
2:划分,扫描所要排序的区间;小于基数的放到左侧,并且交换
3:分别对左侧和右侧重复第二部的操作
#pragma - mark 快速排序
/**
快速排序
@param array 排序数组
@param low 排序起始元素位置
@param high 排序截止元素位置
*/
+ (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high
{
if(array == nil || array.count == 0){
return;
}
if (low >= high) {
return;
}
//取中值
int middle = low + (high - low)/2;
NSNumber *prmt = array[middle];
int i = low;
int j = high;
//开始排序，使得left<prmt 同时right>prmt
while (i <= j) {
while ([array[i] compare:prmt] == NSOrderedAscending) {
i++;
}
while ([array[j] compare:prmt] == NSOrderedDescending) {
j--;
}
if(i <= j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
i++;
j--;
}
NSLog(@"排序中:%@",array);
}
if (low < j) {
[self quickSort:array low:low high:j];
}
if (high > i) {
[self quickSort:array low:i high:high];
}
}
以上只是部分排序算法中的典例，主要是用来理解算法思想
可参看这篇博客http://www.jianshu.com/p/70619984fbc6 ，实现了部分UI效果，更方便思维上的理解
