歸并排序: 平均時(shí)間復(fù)雜度與最壞時(shí)間復(fù)雜度都是O(nlogn)，穩(wěn)定排序
歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個(gè)元素(認(rèn)為直接有序)或者2個(gè)序列(1次比較和交換),然后把各個(gè)有序的段序列合并成一個(gè)有序的長(zhǎng)序列，不斷合并直到原序列全部排好序。可以發(fā)現(xiàn)，在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換，2個(gè)元素如果大小相等也沒有人故意交換，這不會(huì)破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。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));
}