c语言----003(冒泡排序和选择排序)

以升序排列为例
（1）从左到右，依次比较相邻的两个变量
（2）若a[i]>a[i+1],交换a[i]与a[i+1]的值，i++后重复上述比较与交换
（3）就这样一趟一趟的比较，每一趟右边得到相对最大的值，像冒泡一样
（4）一个容量为n的数组就要走n-1趟，故时间复杂度为o(n^2)

#include 
#include 

int main()
{
    int num[12]={5,6,8,4,2,6,45,2,23,4,45,28};
    for(int i=0;i<11;i++)//控制遍历次数
    {
        for(int j=0;j<11;j++)//比较相临值，交换
        {
            if(num[j]>num[j+1])
            {
                int temp=num[j];
                num[j]=num[j+1];
                num[j+1]=temp;
            }
        }
    }
    for(int i=0;i<12;i++)
    {
        printf("%d ",num[i]);
    }
    printf("nHello world!n");
    return 0;
}

注意到，第（ i+1 ）趟循环结束，右边（i+1）个数已经是排的相对于剩下数最大的了，因此，这一部分不在需要排序，下面代码示例，更直观的感受一一下。

#include 
#include 

int main()
{
    int num[12]= {5,6,8,4,2,6,45,2,23,4,45,28};
    for(int i=0; i<11; i++) //控制遍历次数
    {
        for(int j=0; j<11; j++) //比较相临值，交换
        {
            if(num[j]>num[j+1])
            {
                int temp=num[j];
                num[j]=num[j+1];
                num[j+1]=temp;
            }
        }
        printf("第%2d次循环",i+1);
        for(int i=0; i<12; i++)
        {
            printf("%d ",num[i]);
        }
        printf("n");
    }

    printf("nHello world!n");
    return 0;
}

然后我们又发现第六次循环时其实就已经排好了序，这时候我们可以判断是否交换了值，未交换值说明已经排好了，结束循环

#include
int main()
{
    int num[12]= {5,6,8,4,2,6,45,2,23,4,45,28};
    int flag;//用于判断是否交换的标记
    for(int i=0;i<11;i++)
    {
        flag=1;
        for(int j=0;j<11-i;j++)
        {
            if(num[j]>num[j+1])
            {
                int temp=num[j];
                num[j]=num[j+1];
                num[j+1]=temp;
                flag=0;
            }
        }
        printf("第%2d趟排序",i+1);
        for(int i=0;i<12;i++)
        {
            printf("%d ",num[i]);
        }
        printf("n");
        if(flag)
        {
            break;
        }
    }
    for(int i=0;i<12;i++)
    {
        printf("%d ",num[i]);
    }
    return 0;
}

（1）顾名思义，选择排序就是每回选择最大或者最小的数和每一趟开始的数交换值
（2）一般设置一个盯哨，记录最大值所在位置，以数组为例，记录数组下标

#include

void print(int num[],int n)
{
    for(int i=0; i
        printf("%d ",num[i]);
    }
    printf("n");
}

void swap(int*m,int*n)
{
    int temp;
    temp=*m;
    *m=*n;
    *n=temp;
}

int main()
{
    int num[12]= {12,45,56,78,45,15,14,54,5,45,1,23};
    int temp;//监视哨
    for(int i=0; i<11; i++)
    {
        temp=i;
        for(int j=i+1; j<12; j++)
        {
            if(num[temp]
                temp=j;
            }
        }
        swap(&num[temp],&num[i]);
    }
    print(num,12);
    return 0;
}

我们可以同时选择最大和最小的数，两边同时进行

//优化选择排序
{12,45,56,78,45,15,14,54,5,45,1,23}
//对以上数组排序



#include 
void print(int num[],int n)
{
    for(int i=0;i
        printf("%d ",num[i]);
    }
    printf("n");
}

void Swap(int *m,int *n)
{
    int temp;
    temp=*m;
    *m=*n;
    *n=temp;
}

int main()
{
    int num[12]={12,45,56,78,45,15,14,54,5,45,1,23};
    int Max,Min;//监视哨
    for(int i=0,j=11;i<5;i++,j--)
    {
        Max=i;
        Min=i;
        for(int j=i+1;j<12-i;j++)
        {
            if(num[Max]
                Max=j;
            }
            if(num[Min]>num[j])
            {
                Min=j;
            }
        }
        Swap(&num[Max],&num[i]);
        Swap(&num[Min],&num[j]);
    }
    print(num,12);
    return 0;
}

突然发现C语言好像不能引用传参，另外，后面的代码计划用C++编写，个人认为都差不多。