冒泡排序

冒泡算法

冒泡排序：从序列的一端开始，依次比较相邻的两个数的大小,直到另一端，始终将更大或更小的一个数与数组第一个索引的数进行交换，每经过一轮交换，下一轮的交换起始点索引+1，当最大经过数组长度-1的轮次后，排序完成，整个过程就像一个个从大到小的泡泡从底部向上冒出，故称为冒泡排序。

设数组长度为N。

1. 每轮比较相邻的前后两个数据，如果前面数据大于或者小于后面的数据，就将二个数据交换。

2. 这样每轮对数组的第0个数据到N-1个数据进行一次遍历后，最大或者最小的一个数据就到数组第N-1个位置。

3. 第一轮比较到下标为N-1的数据（最后一个），以后每次比较都-1。

#include <stdio.h>

    int main () {
    int list[10] = {4,37,94,57,64,29,83,18,19,40};
    int i, j, temp;
    for (i = 0; i < 9 ; i++)
        for (j = 0; j < 9 - i; j++)
        if (list[j ] > list[j+1]) //比较当前值和下一个值
    {
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;  //交换
    }
    for (i = 0;i < 10; i++)
        printf("%d\n",list[i]);
}

优化算法

冒泡有一个最大的问题就是不管序列有序还是没序，双层循环的每一次比较都执行了。

下面对其进行优化，设置一个标志，如果这一轮发生了交换，则为1，否则为0。

如果有一趟没有发生交换，说明排序已经完成，则结束排序。

#include <stdio.h>

    int main () {
    int list[10] = {4,37,94,57,64,29,83,18,19,40};
    int  j, temp;
    int  i = 9;
    int bool = 1;
    while(bool)
    {    
        bool = 0; //初始化布尔值
        for (j = 0; j < i; j++)
            if (list[j] > list[j+1])
        {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;
            bool = 1;  //进行过交换，排序未完成
        }
        i--;
    }
    for (i = 0;i < 10; i++)
        printf("%d\n",list[i]);
}