你可能会用到的几个简单的算法

发表于

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

从最开始学习的最简单的冒泡算法开始进行整理，不断的学习积累，相信终有一天会取得巨大的进步。

冒泡算法

算法原理

冒泡排序算法的运作如下：（从后往前）
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现（C语言）

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
#include <stdio.h>
#define SIZE 8
 
void bubble_sort(int a[], int n);
 
void bubble_sort(int a[], int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
}
 
int main()
{
    int number[SIZE] = {95, 45, 15, 78, 84, 51, 24, 12};
    int i;
    bubble_sort(number, SIZE);
    for (i = 0; i < SIZE; i++)
    {
        printf("%d", number[i]);
    }
    printf("\n");
}

快速排序

概念

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码

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
void sort(int *a, int left, int right)
{
    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 为止
}

二分查找

概念

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

代码实现（C语言）

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
int BinSearch(SeqList *R，int n,KeyType K)
{
//在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
int low=0，high=n-1，mid；//置当前查找区间上、下界的初值
while(low<=high)
{
if(R[low].key==K)
return low;
if(R[high].key==k)
return high;
//当前查找区间R[low..high]非空
mid=low+((high-low)/2)；
//使用(low+high)/2会有整数溢出的问题
//（问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
//这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题
if(R[mid].key==K)
return mid；//查找成功返回
if(R[mid].key<K)
low=mid+1；//继续在R[mid+1..high]中查找
 
 
else
high=mid-1;//继续在R[low..mid-1]中查找
 
}
if(low>high)
return -1；//当low>high时表示所查找区间内没有结果，查找失败
}//BinSeareh
 
------------上面代码复杂难懂-----------------
int bsearchWithoutRecursion(intarray[],int low,int high,int target)
{
while(low<=high)
{
int mid=(low+high)/2;
if(array[mid]>target)
high=mid-1;
elseif(array[mid]<target)
low=mid+1;
else//findthetarget
return mid;
}
//the array does not contain the target
return-1;
}

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
intbinary_search(constintarr[],intlow,inthigh,intkey)
{
int mid=low+(high-low)/2;
if(low>high)
return -1;
else{
if(arr[mid]==key)
return mid;
else if(arr[mid]>key)
return binary_search(arr,low,mid-1,key);
else
return binary_search(arr,mid+1,high,key);
}
}

链表

大数阶乘

树

二叉树