关于一维数组的排序和查找

排序算法
- 冒泡排序
- 改进的冒泡排序
查找算法
- 顺序查找
- 对半查找
先看例题

从键盘上任意输入8个整数，用冒泡排序法对8个数排序（由小到大）

从键盘上输入整数，利用for循环输入

printf("输入要输入的整数个数：");
scanf("%d",&max);
int i，a[max];
printf("输入数组元素：\n");
for(i=0;i<max;i++)
{ 
    scanf("%d",&a[i]);
}

排序算法

冒泡排序

思路：升序
通过相邻之间的比较和交换，使值较小的数逐渐从底部移向顶部，值较大的数逐渐移向底部；

就像水底的气泡一样逐渐向上冒；

======================================
原数据    第一轮    第二轮    第三轮    第四轮
    2        2        2        2        1
    5        4        3        1        2
    4        3        1        3        3
    3        1        4        4        4
    1        5        5        5        5
======================================
将原数据序列 2、5、4、3、1 按升序排列
------------------
第一轮结束时，5沉底
第二轮结束时，4沉底
第三轮结束时，3沉底
第四轮结束时，2沉底
------------------
从而得到从小到大的序列

由a[0] ~ a[n-1]组成的n个数据，从小到大进行冒泡排序的过程描述

首先将相邻的a[0]与a[1]进行比较，如果a[0]的值大于a[1]的值，则交换两者的位置，使较小的上浮，较大的下沉；接着比较a[1]与a[2]，同样使小1的上浮，大的下沉，以此类推，直到比较完a[n-2]和a[n-1]；此时，a[n-1]为最大值的元素，第一趟排序结束
然后在a[0] ~ a[n-2]区间内，进行第二趟排序，使剩余元素中最大的元素下沉到a[n-2]

直到整个数组有序，上述“下沉”的过程最多需要重复进行n-1次

if 0

简单的冒泡排序

endif

include

int main(void)
{

int a[8]={ 19,9,87,12,-76,0,-45,123};    /*初始化数组*/
int i,j,t;    /*定义循环变量和临时变量*/
printf("待排序数组：\t");
for(i=0;i<8;i++)
{ 
    printf("%6d",a[i]);    /*宽度为6*/
}
printf("\n");
/*开始排序（冒泡排序）*/
for(j=0;j<8-1;j++)    /*外循环：控制循环次数（两个两个比较只需比较8-1次）*/
{ 
    for(i=0;i<8-1-j;i++)    /*内循环：每趟参与比较的元素个数（每交换一次，减少一个需要比较元素）*/
    { 
        if(a[i]>a[i+1])    /*升序排列*/
        { 
            t=a[i];
            a[i]=a[i+1];
            a[i+1]=t;
        }
    }
    /*每趟循环结束打印一下排序的结果*/
    printf("第%d趟比较结束：\t",j+1);
    for(i=0;i<8;i++)
    { 
        printf("%6d",a[i]);
    }
    printf("\n");    /*换行*/
}
/*输出排序后的数据*/
printf("排序结束后：\t");
for(i=0;i<8;i++)
{ 
    printf("%6d",a[i]);
}
printf("\n");

}

在这里插入图片描述

改进的冒泡排序

思路
排序过程通过嵌套for循环完成，对8个元素的数组，一共进行7趟比较，每趟进行(7-j)次比较，以决出一个最大值

从上面的结果可以看出，在进行到第5趟时，数组已经排序完成，并必须要接着再循环，可以跳出，不用再判断了

#if 0
改进的冒泡排序（flag判断数据是否发生交换） 
#endif
#include<stdio.h>
int main()
{ 
    int a[8]={ 19,9,87,12,-76,0,-45,123};    /*初始化数组*/
    int i,j,t;    /*定义循环变量和临时变量*/
    printf("待排序数组：\t");
    for(i=0;i<8;i++)
    { 
        printf("%6d",a[i]);    /*宽度为6*/
    }
    printf("\n");
    int flag=0;    /*flag用来判断是否有交换*/
    for(j=0;j<8-1;j++)
    { 
        for(i=0;i<8-1-j;i++)
        { 
            if(a[i]>a[i+1])
            { 
                t=a[i];
                a[i]=a[i+1];
                a[i+1]=t;
                flag=1;    /*上面的if语句成功执行，则说明数据发生交换*/ 
            }
        }
        if(flag==1)
        { 
            flag=0;    /*若发生交换，则flag赋为0，以便下一次循环判断*/ 
        }
        else
        { 
            break;    /*无交换，跳出循环，不再判断*/ 
        }
        /*每趟循环结束打印一下排序的结果*/
        printf("第%d趟比较结束：\t",j+1);
        for(i=0;i<8;i++)
        { 
            printf("%6d",a[i]);
        }
        printf("\n");    /*换行*/
    } 
}

在这里插入图片描述

再看查找的题目
假设数组a有10个互不相同且从小到大排列的数，
从键盘上再输入一个同类型的数x，在数组中查找x，如果找到，输出相应的下标，否则输出“未找到”

查找算法

顺序查找

过程：
x与数组a中从第一个元素对比，若相等则结束查找；否则继续与第二和元素对比，重复上述过程直到数组的最后一个元素。若数组结束还未找到，则输出“未找到”

注意！！！：当数据量过大时，查找效率较低

#if 0
顺序查找（找到输出下标，否则输出未找到） 
#endif
#include<stdio.h>
int main()
{ 
    int x,i,a[10]={ 2,3,5,8,12,13,14,16,18,25};
    printf("输入待查找数据：");
    scanf("%d",&x);
    for(i=0;i<10;i++)    /*找到，则结束循环*/
    { 
        if(x==a[i])
        { 
            break;
        }
    }
    if(i==10)    /*不管找不找得到，当遍历整个数组后，必须结束循环*/ 
    { 
        printf("数组中未找到%d\n",x);
    }
    else
    { 
        printf("找到了，%d是数组中的第%d个元素\n",x,i+1);
    }
}

在这里插入图片描述

对半查找

又称折半查找或者二分法，算法要求待查数组是有序排列的

过程：
首先比较x和数组a的中间元素，如果相等则查找成功；否则，若x较小，则它只可能在数组a的前半部分，反之则在后半部分，这样每次比较结束，可将搜索范围缩小一半

核心思想：

设下界low=0,上界high=9
当low<high时循环
{ 
    计算中间元素下标值：mid=(low+high)/2
    若x=a[mid],查找成功，结束循环
    若x<a[mid],则调整上界high=mid-1
    若x>a[mid],则调整下界low=mid+1
}
#if 0
对半查找（找到输出下标，否则输出未找到）
也称【二分查找】
要求数组是--有序排列 
#endif
#include<stdio.h>
int main()
{ 
    int x,i,a[10]={ 2,3,5,8,12,13,14,16,18,25};
    printf("输入待查找数据：");
    scanf("%d",&x);
    int low,high,mid,n=0;
    low=0;        /*设定查找范围*/
    high=10-1;
    while(low<=high)
    { 
        n++;    /*记录比较次数*/
        mid=(low+high)/2;
        printf("第%d次比较，low=%d,high=%d,mid=%d\n",n,low,high,mid);
        if(x==a[mid])
        { 
            break;    /*找到，及跳出循环*/
        }
        else if(x<a[mid])
        { 
            high=mid-1;    /*到前半部分查找*/
        }
        else
        { 
            low=mid+1;    /*到后半部分查找*/
        }
    }
    if(low>high)
    { 
        printf("数组中未找到%d\n",x);
    }
    else
    { 
        printf("找到了，%d是数组中第%d个元素\n",x,mid+1);
    }
}