简介

冒泡排序和归并排序是两种常见的排序算法，它们在排序思想和实现方式上有很大的不同。冒泡排序通过重复遍历待排序的列表，每次遍历都将当前待排序的列表中的最大值或者最小值“冒泡”到正确的位置，其算法复杂度为$$O(n^2)$$。归并排序则是基于分而治之的思想，将待排序的数组分为左右两边，然后分别排序后合并，其中涉及到递归操作，算法复杂度为$$O(nlog(n))$$。

冒泡排序

算法原理

我们基于以下思想，当我们遍历一遍数组，我们就可以找到整个数组中的最小值，我们将这个最小值和数组第一个交换位置，然后开启下一轮遍历。此时，我们知道这一轮遍历可以排除掉第一个元素了，因为第一个元素的值必定比其它值都小。重复这个过程我们可以一直到列表的最后一个元素。

代码

我们基于练习32部分完成的链表，实现冒泡排序算法

void swap_node(ListNode* a,ListNode *b){
    void *c = a->value;
    a->value = b->value;
    b->value = c;
}
int List_bubble_sort(List *list, List_compare cmp)
{
    if(list->count < 2)
        return 0;
    for(ListNode *nodeA = list->first;nodeA != list->last ; nodeA=nodeA->next){
        for(ListNode *nodeB = nodeA->next;nodeB != NULL;nodeB=nodeB->next){
            if(cmp(nodeB->value,nodeA->value) < 1){
                swap_node(nodeA,nodeB);
            }
        }
    }
    return 0;
}

归并排序

算法原理

归并排序并不像冒泡排序那样便于理解，因为其中涉及到了递归的思想。
我们将一个数组分为左右两个部分，将左右两个部分排序好（我们假设我们已经完成了归并排序算法，所以这里我们对左右两边分别调用归并排序算法即可）后合并到一起，同时我们在函数入口判断，当传入的数组大小为0或者1时，我们直接将该数组返回。
用于合并左右两边的代码原理为，我们先跑一个循环，循环退出条件为两个数组其中一个为空。在循环中我们比较两个数组的首元素，将较小的那个压入result数组中。最后我们将剩下的数组接到result数组的最后。

代码实现

这里我们还是和前面一样，通过C语言实现。

List* merge_list(List* left, List* right,List_compare cmp){
    List* result = List_create();
    while(left->first && right->first){
        if(cmp(left->first->value,right->first->value) < 0){
            List_push(result,List_shift(left));
        } else {
            List_push(result,List_shift(right));
        }
    }
    while(left->first){
        List_push(result,List_shift(left));
    }
    while(right->first){
        List_push(result,List_shift(right));
    }
    return result;
}
List *List_merge_sort(List *list, List_compare cmp)
{
    if(list->count<2) return list;
    int left = list->count/2;
    int right = list->count - left;
    List * left_list = List_create();
    List * right_list = List_create();
    for(int i=0;i<right;i++){
        List_push(right_list,List_pop(list));
    }
    left_list = list;
    return merge_list(List_merge_sort(left_list,cmp),List_merge_sort(right_list,cmp),cmp);
}