xiangjingyi Web安全 学习笔记

xiangjingyi

1冒泡排序  对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不相符时，即将这两个数据进行交换。如果从小到大排序，这时，较小的数据就会逐个向前移动，好像气泡上升一样。

[C] 纯文本查看 复制代码

#include <stdio.h>#include <stdlib.h>
/*从小往大排序（以五个数为例）*/
int main()
{   int arr[5],i,j,temp;
    for(i=0;i<5;i++)
        scanf("%d",&arr[i]);/*从键盘上输入数组的各个元素*/
    for(i=0;i<5-1;i++)/*外层循环*/
    {
        for(j=0;j<5-i-1;j++)/*内层循环*/
        {
            if(arr[j]>arr[j+1])/*比较大小*/
            {
                temp=arr[j];
                arr[j]=arr[j+1];/*交换大小与排序位置不相符的两个相邻的数的值*/
                arr[j+1]=temp;
            }
        }
    }
    for(i=0;i<5;i++)
        printf("%d ",arr[i]);/*输出排号的数字*/
    return 0;
}

2选择排序从头到尾扫描排序，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <stdlib.h>
/*选择排序（以七个数字为例）*/
int main()
{
   int a[7], i, j, k, x;
   for(i=0;i<7;i++)
      scanf("%d",&a[i]);/*输入七个数字*/
   for(i=0;i<6;i++)
   {
       k=i;/*先把第一个定位最小值的k*/
       for(j=i+1;j<7;j++)/*再往后挨个比较，如果有更小的，*/
                         /*就把它和k互换，并不断循环*/
       if(a[j]<a[k])
        k=j;
       if(i!=k)
       {
           x=a[i];
           a[i]=a[k];
           a[k]=x;
       }
   }
   for(i=0;i<7;i++)
    printf("%d ",a[i]);/*输出排好的七个数字*/
   return 0;
}

3.二分查找有n个数字，若要从中找出某一个，按顺序查找，最坏要查找n次，即复杂程度为n。但若是使用二分查找，效率会更快，复杂度只有log2n。

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <stdlib.h>
/*以从数组1到10中找出7为例*/
int main()
{
   int arr[]={1,2,3,4,5,6,7,8,9,10};
   int k=7;
   int sz=sizeof(arr)/sizeof(arr[0]);/*计算arr的长度*/
   int left=0;
   int right=sz-1;/*最右边的数的下标为长度减1*/
   while(left<=right)
   {
       int mid=(left+right)/2;
       if(arr[mid]>k)
          right=mid-1;
       else if(arr[mid]<k)
          left=mid+1;
       else
        {printf("找到了，下标是：%d\n",mid);
        break;}
   }
   if(left>right)
    {printf("找不到\n");}
    return 0;
}