排序初步
Suzhou 661 1

二分法的前提是要执行搜索的数字在数组中已经排好序。

无序数组根据算法排列成有序数组:

步骤一:找到数组a中最大的数字的位置

定义最大的数字位置为maxid,先令maxid为0,即数组中最大的数字是第一个元素,然后mixid的元素和顺序加1位置上的元素对比大小,定义变量i表示元素位置,一直对比到i=length-1,再输出maxid。 |0|1|2|3|4|5|6|7|8|9| |-|-|-|-|-|-|-|-|-|-| |2|48|18|29|64|25|3|54|16|35| 如上,先令maxid=0,i从maxid开始递增,a[maxid]和a[i]比较,a[0]<a[1],此时maxid=i,a[maxid]=48,继续对比a[maxid]和a[i],以此类推,直到i=length-1,输出maxid。

#include <stdio.h>

int  max(int a[],int length)
{
    int maxid = 0;
    int i;
    for(i=1;i<length;i++)
    {
        if( a[i]>a[maxid] )
        {
            maxid = i;
        }
    }
    return maxid;
}
int main()
{
    int a[] = {2,48,18,29,64,25,3,54,16,35};
    int maxid = max(a,sizeof(a)/sizeof(a[0]));  //length=sizeof(a)/sizeof(a[0])
    printf("%d\n",maxid);
    return 0;
}
4

--------------------------------
Process exited after 0.01162 seconds with return value 0

步骤二:对数组a中数字顺序排序

步骤一中找到了数组中最大的元素的位置,希望数组排序过后最大元素的位置为length-1,可以引入新的变量,对a[maxid]和a[length-1]做交换。此时确定了数组a中最大的元素,然后循环步骤二,从右向左把元素由大到小填充数组,直到只剩下两个元素。 在循环结束后,可以再加入一个循环遍历整个数组,来判断数组是否排序完成且正确。

#include <stdio.h>

int  max(int a[],int length)
{
    int maxid = 0;
    int i;
    for(i=1;i<length;i++)
    {
        if( a[i]>a[maxid] )
        {
            maxid = i;
        }
    }
    return maxid;
}
int main()
{
    int a[] = {2,48,18,29,64,25,3,54,16,35};
    int length = sizeof(a)/sizeof(a[0]);
    //选择排序 
    int i;
    for(i = length-1;i>0;i--)
    {
        int maxid = max(a,i+1);
        //swap a[maxid],a[length-1]
        int t = a[maxid];
        a[maxid] = a[i];
        a[i] = t;
    }
    for(i = 0;i<length;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}
2 3 16 18 25 29 35 48 54 64
--------------------------------
Process exited after 0.02294 seconds with return value 0
评论区

索引目录