C++歸並排序總結

C++歸並排序總結

#include 
using namespace std;
//歸並排序非遞歸版。
void Sort(int a[], int n,int high)
{
    int k;
    for (int i = 0; i < high; i += 2 * n)
    {
        int x = i;//001
        int y = i + n;//2  2 3
        int z = i + 2 * n;// 4
        if (z>high)
        {
            z = high;
        }
        for (int j = y; j <= z; j++)
        {
            int temp = a[j];
            for (k = j; k > 0; k--)
            {
                if (a[k - 1]>temp)
                {
                    a[k] = a[k - 1];
                }
                else
                {
                    break;
                }
            }
            a[k] = temp;
            //在需要合並的時候，我選擇使用插入排序，不開辟新的空間。
        }
    }
}
void Grial(int a[],int high)
{
    int n = high / 2+1;//終止位置。
    //1 2 3

    for (int i = 1; i <= n; i *= 2)
    {
        Sort(a,i,high);
    }
}
int main()
{
    int a[] = { 5,4,3,7,1,3,2,0,5,6,7,9,654,5,423,3,4,
              5,6,8,523,423,4,5,6,7,8,45,6,53,423,4,100 };
    Grial(a,sizeof(a) / sizeof(int)-1);
    for (int i = 0; i < sizeof(a) / sizeof(int);i++)
    {
        cout << a[i] <<  ;
    }
    cout << endl;
    return 0;
}

#include 
using namespace std;                        
//遞歸版本的歸並排序。               
void Sort(int a[], int low, int mid, int high)                     
{                                                
    int i;
    int j;
    int temp;
    for (i = mid+1; i <= high; i++)
    {
        temp = a[i];
        for (j = i; j > low;j--)
        {
            if (temp < a[j - 1])
            {
                a[j] = a[j-1];
            }
            else
            {
                break;
            }
        }
    //既然已經接近排序好的，那麼我們可以選擇使用插入排序或者冒泡排序來提高效率
    //並且不開辟額外的空間。
        a[j] = temp;
    }
}              

void Sert(int a[],int low,int high)                      
{                                     
    if (low >= high)return;               

    int mid = (low + high) / 2;                 
    Sert(a,low, mid);                    
    Sert(a, mid + 1, high);
    Sort(a,low,mid,high);
}
int main()
{
    int a[] = {6,2,1,3,4,-1,2-3,4,5,6,7,532,4,432,-23,
               -32,1,-3,21,-321,-3,5,6,8,432,5,66,991};
    Sert(a, 0,sizeof(a) / sizeof(int)-1);
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        cout << a[i] <<  ;
    }
    cout << endl;
    return 0;
}