归并排序---数组

浏览数：18 / 时间：2015年06月08日

/*merge sort*/
#include <iostream>
using namespace std;

const int max_num = 1000000000;

void mergeData(int *s, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int ld[n1 + 1];
    int rd[n2 + 1];
    int i = 0, j = 0, k = 0;
    for(i = 0; i < n1; i++)
    {
        ld[i] = s[p + i];
    }
    for(j = 0; j < n2; j++)
    {
        rd[j] = s[q + j + 1];
    }
    i = 0;
    j = 0;
    ld[n1] = max_num; // 哨兵
    rd[n2] = max_num;
    for(k = p; k <= r; k++)
    {
        if(ld[i] <= rd[j])
        {
            s[k] = ld[i];
            i++;
        }
        else
        {
            s[k] = rd[j];
            j++;
        }
    }
}

void mergeSort(int *s, int p, int r)
{
    int q = 0;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(s, p, q);
        mergeSort(s, q+1, r);
        mergeData(s, p, q, r);
    }
}

int main()
{
    int i = 0;
    int s[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    mergeSort(s, 0, 9);
    for(i = 0; i < 10; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

归并排序---数组