归并排序

曾经终败给现在 2022-08-21 01:20 5阅读 0赞

http://www.cnblogs.com/bluestorm/archive/2012/09/06/2673138.html

/\*\*

\* Merge\_Sort: 归并排序的递归实现  
 \* 注：算法导论上给出的合并排序算法  
 \* 递归过程是将待排序集合一分为二，  
 \* 直至排序集合就剩下一个元素为止，然后不断的合并两个排好序的数组  
 \* T(n) = O(nlgn)  
\*\*/  
\#include <stdio.h>  
\#define LEN 8  
  
  
// 合并  
void merge(int a\[\], int start, int mid, int end)  
\{  
    int n1 = mid - start + 1;  
    int n2 = end - mid;  
    int left\[n1\], right\[n2\];  
    int i, j, k;  
  
  
    for (i = 0; i < n1; i++) /\* left holds a\[start..mid\] \*/  
        left\[i\] = a\[start+i\];  
    for (j = 0; j < n2; j++) /\* right holds a\[mid+1..end\] \*/  
        right\[j\] = a\[mid+1+j\];  
  
  
    i = j = 0;  
    k = start;  
    while (i < n1 && j < n2)  
        if (left\[i\] < right\[j\])  
            a\[k++\] = left\[i++\];  
        else  
            a\[k++\] = right\[j++\];  
  
  
    while (i < n1) /\* left\[\] is not exhausted \*/  
        a\[k++\] = left\[i++\];  
    while (j < n2) /\* right\[\] is not exhausted \*/  
        a\[k++\] = right\[j++\];  
\}  
  
  
// merge\_sort()：先排序，再合并  
void merge\_sort(int a\[\], int start, int end)  
\{  
    int mid;  
    if (start < end)  
    \{  
        mid = (start + end) / 2;  
        printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\\n",  
               start, mid, mid+1, end,  
               a\[0\], a\[1\], a\[2\], a\[3\], a\[4\], a\[5\], a\[6\], a\[7\]);  
  
  
        // 分解 + 解决：Divide + Conquer  
        merge\_sort(a, start, mid); // 递归划分原数组左半边array\[start...mid\]  
        merge\_sort(a, mid+1, end); // 递归划分array\[mid+1...end\]  
        // 合并：Combine  
        merge(a, start, mid, end); // 合并  
  
  
        printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\\n",  
               start, mid, mid+1, end,  
               a\[0\], a\[1\], a\[2\], a\[3\], a\[4\], a\[5\], a\[6\], a\[7\]);  
    \}  
\}  
  
  
int main(void)  
\{  
    int a\[LEN\] = \{ 5, 2, 4, 7, 1, 3, 2, 6 \};  
    merge\_sort(a, 0, LEN-1);  
  
  
    return 0;  
\}  
  
  
  
  
  
  
  
  
  
  
  
  
/\*\*  
 \* merge\_sort: 非递归实现 --迭代  
 \* 非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序，  
 \* 构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，  
 \* 如此继续下去，直至整个数组排好序。  
\*\*/  
  
  
\#include <stdio.h>  
\#include <stdlib.h>  
\#define LEN 8  
  
  
// merge\_sort(): 非递归实现-自底向上  
// 将原数组划分为left\[min...max\] 和 right\[min...max\]两部分  
void merge\_sort(int \*list, int length)  
\{  
    int i, left\_min, left\_max, right\_min, right\_max, next;  
    int \*tmp = (int\*)malloc(sizeof(int) \* length);  
  
  
    if (tmp == NULL)  
    \{  
        fputs("Error: out of memory\\n", stderr);  
        abort();  
    \}  
  
  
    for (i = 1; i < length; i \*= 2) // i为步长，1,2,4,8……  
    \{  
        for (left\_min = 0; left\_min < length - i; left\_min = right\_max)  
        \{  
            right\_min = left\_max = left\_min + i;  
            right\_max = left\_max + i;  
  
  
            if (right\_max > length)  
                right\_max = length;  
  
  
            next = 0;  
            while (left\_min < left\_max && right\_min < right\_max)  
                tmp\[next++\] = list\[left\_min\] > list\[right\_min\] ? list\[right\_min++\] : list\[left\_min++\];  
  
  
            while (left\_min < left\_max)  
                list\[--right\_min\] = list\[--left\_max\];  
  
  
            while (next > 0)  
                list\[--right\_min\] = tmp\[--next\];  
        \}  
    \}  
  
  
    free(tmp);  
  
  
\}  
  
  
  
  
int main(void)  
\{  
    int a\[LEN\] = \{ 5, 2, 4, 7, 1, 3, 2, 6 \};  
    merge\_sort(a, LEN);  
  
  
    // print array  
    int i;  
    for (i = 0; i < LEN; i++)  
        printf("%d ", a\[i\]);  
  
  
    return 0;  
\}