菜鸟也来学算法之冒泡排序

冒泡排序可以说是众多排序算法之中较简单的一种，思想与选择排序类似，选择排序每一次遍历取出最小的数放在首位（暂时这样认为），而冒泡排序则每一次遍历把最大的数放在数组的最后一个位置，举个例子：

12,56,34,789,8,28

第一次遍历：12,34,56,8,28,789

第二次遍历：12,34,8,28,56,789

第三次遍历：12,8,28,34,56,789

第四次遍历：8,12,28,34,56,789

第五次遍历：8,12,28,34,56,789

通常用双重循环，外层循环的次数为N-1次（N为排序的个数），数组代码实现如下：

 1 void Bubble_Sort(int array[], int length)
 2 {
 3     if (NULL == array || 0 == length)
 4     {
 5         return;
 6     }
 7     bool flag = true;
 8     int temp = 0;
 9 
10     for (int outer = length - 1; outer > 0 && flag; --outer)
11     {
12         flag = false;
13         for (int inner = 1; inner <= outer; ++inner)
14         {
15             if (array[inner] < array[inner - 1])
16             {
17                 temp = array[inner];
18                 array[inner] = array[inner - 1];
19                 array[inner - 1] = temp;
20                 flag = true;
21             }
22         }
23     }
24 }

链表代码实现如下：

void Bubble_Link_Sort(struct Node *head)
{
    struct Node *p = head;
    struct Node *q = head->next;
    int temp = 0;
    
    while(NULL != p)
    {
        while (NULL != q)
        {
            if (p->data < q->data)
            {
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->next;
        }
        p = p->next;
        if (NULL != p)
        {
            q = p->next;
        }    
    }
}