常见算法总结

发表于 | 分类于
| 字数统计 2.3k | 阅读时长 11

排序

1、插入排序
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if(arr == null || arr.length < 2){
    return arr;
}
for(int i=1;i<arr.length;i++){
    for(intj=i;j>0;j--){
        if(arr[j]<arr[j-1]){
            int temp=arr[j];
            arr[j]=arr[j-1];
            arr[j-1]=temp;
        }else{
            //接下来是无用功
            break;
        }
    }
}
return arr;

2、冒泡排序
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
int temp = 0;
for (int i = a.length - 1; i > 0; --i)
{
    for (int j = 0; j < i; ++j)
    {
        if (a[j + 1] < a[j])
        {
            temp = a[j];
            a[j] = a[j + 1];
            a[j + 1] = temp;
        }
    }
}

3、快速排序
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保以某个数为基准点的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
main()
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];

    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }

        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/

        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }

        a[j] = a[i];        
    }

    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
    /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

4、选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
main()
{
int i,j,min,t;
for(i=0;i<n-1;i++)
{
    min=i;//查找最小值
    for(j=i+1;j<n;j++)
        if(a[min]>a[j])
        min=j;//交换

        if(min!=i)
        {
            t=a[min];
            a[min]=a[i];
            a[i]=t;
        }
    }
}

升序排序（选择排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void sort(int a[],int n)
{

int i, j, index;

for(i = 0; i < n - 1; i++) {

index = i;

for(j = i + 1; j < n; j++) {

if(a[index] > a[j]) {

index = j;

}

}

if(index != i) {

int temp = a[i];

a[i] = a[index];

a[index] = temp;

}

}

}

int main(int argc, const char * argv[]) {

int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8};

sort(numArr, 10);

for (int i = 0; i < 10; i++) {

printf("%d, ", numArr[i]);

}

printf("\n");

return 0;

}

降序排序（冒泡排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main(int argc, char *argv[]) {

    int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};

    int num = sizeof(array)/sizeof(int);

    for(int i = 0; i < num-1; i++) {

        for(int j = 0; j < num - 1 - i; j++) {

            if(array[j] < array[j+1]) {

                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }

    for(int i = 0; i < num; i++) {

        printf("%d", array[i]);
        if(i == num-1) {
            printf("\n");
        }
        else {
            printf(" ");
        }
    }
}

二分法

二分法查找只适用与已排序的数列。
思路：首先将值 x 与数组 v 的中间元素比较，如果 x 小于中间的元素，则将 end 值设为 中间元素-1，同理，若 x 大于中间元素，则将中间元素 + 1作为 start，再在 start 与 end 之间进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
int start = 0;
int end = data.length-1;
int mid = (start+end)/2;//a
while(data[mid]!=aim&&end>start){
    if(data[mid]>aim){
        end = mid-1;
    }else if(data[mid]<aim){
        start = mid+1;
    }
    mid = (start+end)/2;
}
return (data[mid]!=aim)?-1:mid;

斐波那契数列

数列：1,1,2,3,5,8,13,21… 求第n项的值

1
2
3
4
5
6
7
8
9
10
11
int f1,f2,f,i,n;    
f1=f2=1;
if(n<=2)    
    printf("%d",1);    
else 
{                        //加上括号
    for(i=3;i<=n;i++)      
{   
f=f1+f2;         
f1=f2;   
f2=f;

请用代码或者伪代码打印输出一个菱形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void print(int n)
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n-i; j++){ printf(" "); }
        for(j=n-i+1; j<n+i; j++){ printf("*"); }
        printf("\n");
    }
    for(i=n-1; i>=1; i--)
    {
        for(j=1; j<=(n-i); j++){ printf(" "); }
        for(j=n-i+1; j<n+i; j++){ printf("*"); }
        printf("\n");
    }
}

打印0-100之间的素数

思路：与小于根号n的数取余，结果为0则是合数，否则就是素数（质数）

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 1;i<100;i++){
    int r = [self isPrime:i];
    if(r==1){
        NSLog(@"%d",i);
    }
}

-(int)isPrime:(int)number{
    for(int i=0;i<=sqrt(number);i++){
        if(number%i==0)  return0;  
    }
    return 1;
}

求两个整数的最大公约数

思路：如果较大数与较小数取余为0，则最大公约数为较小数，否则，拿较小数与上一步取余结果取余，直到结果为0，最后的较小数为最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int gcd(int a,int b){
    int temp = 0;
    if(a<b){
        temp = a;
        a = b;
        b = temp;
    }

    while (b!=0) {
        temp = a % b;
        a = b;
        b = temp;
        NSLog(@"a:%d b:%d",a,b);
    }
    return a;
}

给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2

思路：创建一个空数组，默认元素都为-1，遍历字符串一遍，存下每个字母的位置，如果存过一次，就把位置设置为-2，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include     <stdio.h>
#include     <stdlib.h>
#include     <string.h>

int find_char(const char* str)
{
    static int pos[256];
    const unsigned char* p = (const unsigned char*)str;
    int i = 0;
    if( (!str) || (!(*str)) ) return -1;
    memset(pos,-1,sizeof(pos));
    while(*p){
        if(pos[*p] == -1){
            pos[*p] = p-(const unsigned char*)str;
        }else{
            pos[*p] = -2;
        }
        p++;
    }
    for(i=0;i<sizeof(pos)/sizeof(pos[0]);i++){
        if(pos[i]>=0)return pos[i];
    }
    return -1;
}

int main()
{
    const char* p = "abaccddeeef";
    int pos = find_char(p);
    printf("index:%d, it is '%c'\n",pos,pos!=-1?p[pos]:' ');

    p = "abcdefghijklmnopqrstuvwxyz abcdefghijklmnopqrstu wxyz ";
    pos = find_char(p);
    printf("index:%d, it is '%c'\n",pos,pos!=-1?p[pos]:' ');
    return 0;
}

给定一个整数，问这个整数转成2进制后，里面包含有多少个1？比如：10，二进制表示为，1010则，输出2

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
int howmany(int x)
{
    int count = 0;
    while (x)
    {
        if ((x&1) == 1)
        {
            count++;
        }
        x = x>>1;
    }
    return count;
}

计算阶乘

1
2
3
4
5
6
7
8
9
int f(int i)
{
    int t=1,j;

    for(j=1;j<=i;j++)
    t=t*j;

    return t;
}

现有一个M行N列的数组,要求安装反向斜对角线(右上->左下)的方式,打印该数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//    int m = 5,n = 4;
int m ,n;
scanf("%d%d",&m,&n);
int a[m][n];
int count=0;
for (int i=0; i<m; i++) {
    for (int j=0; j<n; j++) {
        a[i][j]=count++;
        printf("%d ",a[i][j]);
    }
    printf("\n");
}

for (int k = 0; k<m+n-1; k++) {
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (i+j==k) {
                printf("%d ",a[i][j]);
            }
        }
    }
    printf("\n");
}

printf("*****优化后的算法*****\n");
int low=0;   //i的下限
while (num<(m+n-1)) {//i+j=5，3*4的数组循环6次

    if(num>=n){ //打印下半部分的时候i的下标开始+1
        low++;
    }
    for (int i=low;i<m; i++) {
        printf("%d ",a[i][num-i]);
        if (num==i) { //列的下标等于0的时候，跳出。
            break;
        }
    }
    printf("\n");//加一个换行可以看得更加明了
    num++;
}
-------------本文结束感谢您的阅读-------------