归并排序: 平均时间复杂度与最坏时间复杂度都是O(nlogn)，稳定排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。void
merge(int *array, int *aux, int begin, int mid, int end)
{
int len = end - begin + 1;
memcpy(aux+begin, array+begin, sizeof(int)*len);
int *first, *second, *ptr = array+begin;
first = aux+begin;
second = aux+mid+1;
while(first<=aux+mid && second<=aux+end) {
if(*first <= *second)
*ptr++ = *first++;
else
*ptr++ = *second++;
}
if(first <= aux+mid)
while(first <= aux+mid)
*ptr++ = *first++;
if(second <= aux+end)
while(second <= aux+end)
*ptr++ = *second++;
}
void
merge_sort_dc(int *array, int *aux, int begin, int end)
{
if(begin >= end)
return;
int mid = begin + ((end-begin)>>1);
merge_sort_dc(array, aux, begin, mid);
merge_sort_dc(array, aux, mid+1, end);
merge(array, aux, begin, mid, end);
}
void
merge_sort(int *array, int len)
{
int *aux = (int *)malloc(sizeof(int) * len);
merge_sort_dc(array, aux, 0, len-1);
free(aux);
}
struct Node {
int val;
struct Node *next;
};
struct Node *
list_merge(struct Node *first, struct Node *second)
{
if(first == NULL)
return second;
if(second == NULL)
return first;
struct Node *node = NULL;
if(first->val <= second->val) {
node = first;
first = first->next;
} else {
node = second;
second = second->next;
}
node->next = list_merge(first, second);
return node;
}
struct Node *
list_merge_sort(struct Node *list)
{
if(list==NULL || list->next==NULL)
return list;
struct Node *once = list;
struct Node *twice = list;
while(twice->next && twice->next->next) {
once = once->next;
twice = twice->next->next;
}
twice = once->next;
once->next = NULL;
once = list;
list_merge(list_merge_sort(once), list_merge_sort(twice));
}