归并排序

#include <iostream>
using namespace std;
int tem[1005];
int a[1005];
bool com1(int x,int y)
{
    return x >= y;
}
bool com2(int x ,int y)
{
    return x <=y;
}
void merges(int from[] , int to[],int b ,int m, int e , bool com(int x,int y))
{
    int i = b;
    int j = m+1;
    int k = b;
    while (i<=m&&j<=e)
    {
        if (com(from[i],from[j]))
            to[k++] = from[i++];
        else to[k++] = from[j++];
    }
    for (int t = i; t<=m;) to[k++] = from[t++];
    for (int t = j; t<=e;) to[k++] = from[t++];
    for (int t = b; t <= e ;t++)
        from[t] = to[t];
}
void mergesort(int a[], int b, int e,bool com(int x,int y))
{
    if (b >= e ) return;
    int mid = (b+e)/2;
    mergesort(a,b,mid,com);
    mergesort(a,mid+1,e,com);
    merges(a,tem,b,mid,e,com);
}
void print(int a[],int n)
{
    for (int i = 1; i<= n; i++)
    {
        cout << a[i] <<" ";
    }
    cout << endl;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1 ; i<= n; i++)
        cin >> a[i];
    mergesort(a,1,n,com1);
    print(a,n);
    mergesort(a,1,n,com2);
    print(a,n);
}

递归数组慢

#include <iostream>
using namespace std;
int tem[1005];
int a[1005];
bool com1(int x,int y)
{
    return x >= y;
}
bool com2(int x ,int y)
{
    return x <=y;
}
void merges(int from[] , int to[],int b ,int m, int e , bool com(int x,int y))
{
    int i = b;
    int j = m+1;
    int k = b;
    while (i<=m&&j<=e)
    {
        if (com(from[i],from[j]))
            to[k++] = from[i++];
        else to[k++] = from[j++];
    }
    for (int t = i; t<=m;) to[k++] = from[t++];
    for (int t = j; t<=e;) to[k++] = from[t++];
}
//倍增法归并
void mergesort(int a[], int b, int e,bool com(int x,int y))
{
    int l = 1;
    int L = e-b+1; //长度
    while (l <= L)
    {
        int i;
        for (i = b; i+2*l-1 <= e; i+=2*l)
        {
            merges(a,tem,i,i+l-1,i+2*l-1,com);
        }
        merges(a,tem,i,min(i+l-1,e),e,com);
        l *= 2;
        // 循环数组
        for (i = b; i+2*l-1 <= e; i+=2*l)
        {
            merges(tem,a,i,i+l-1,i+2*l-1,com);
        }
        merges(tem,a,i,min(i+l-1,e),e,com);
        l *= 2;
    }
}
void print(int a[],int n)
{
    for (int i = 1; i<= n; i++)
    {
        cout << a[i] <<" ";
    }
    cout << endl;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1 ; i<= n; i++)
        cin >> a[i];
    mergesort(a,1,n,com1);
    print(a,n);
    mergesort(a,1,n,com2);
    print(a,n);
}

迭代倍增数组

 1 #include <iostream>
 2 using namespace std;
 3 bool com1(int x,int y)
 4 {
 5     return x >= y;
 6 }
 7 bool com2(int x ,int y)
 8 {
 9     return x <=y;
10 }
11 struct list_
12 {
13     int v;
14     int next;
15 }a[1005];
16 int merge_list(list_ a[],int first ,int second ,bool com(int x ,int y),int n)
17 {
18     int new_head = n+1;
19     int * ptr;
20     while (first!=-1 && second != -1)
21     {
22         if (com(a[first].v,a[second].v))
23             ptr = &first;
24         else
25             ptr = &second;
26         a[new_head].next = (*ptr);
27         new_head = (*ptr);
28         (*ptr) = a[(*ptr)].next;
29     }
30     a[new_head].next = first + second + 1;
31     return a[n+1].next;
32 }
33 int mergesort(list_ a[], int b, int e ,bool com(int x,int y),int n)
34 {
35     if (b == e) return b;
36     if (b > e ) return -1;
37     int mid = (e+b)/2;
38     int first = mergesort(a,b,mid,com,n);
39     int second = mergesort(a,mid+1,e,com,n);
40     return merge_list(a,first,second,com,n);
41 }
42 void print(list_ a[],int n,int head)
43 {
44     for (int i = head; i != -1; i = a[i].next)
45     {
46         cout << a[i].v <<" ";
47     }
48     cout << endl;
49 }
50 void init(int n)
51 {
52     for (int i = 1; i<=n;i++)
53         a[i].next = -1;
54 }
55 int main()
56 {
57     int n;
58     cin >> n;
59     for (int i = 1 ; i<= n; i++)
60         cin >> a[i].v;
61     init(n);
62     int head = mergesort(a,1,n,com1,n);
63     print(a,n,head);
64     init(n);
65     head = mergesort(a,1,n,com2,n);
66     print(a,n,head);
67 }

递归链表快