Jimmy小站

小明也有大梦想 — 蒋明/铭
当前位置:网站首页 / 数据结构算法 / 正文

排序法的优化MergeSort+InsertSort

2015-09-17 / 数据结构算法 / 3097 次围观 / 1 次吐槽

数据量大概50个以下的时候,插入排序法的效率要高于归并排序。但是在很大的数据量的时候,归并排序又有很大的优势。基于这个原因以及它们各自排序的特点,在归并排序法往下拆分的时候,当每组数据量达到50左右的水平就改用插入排序法。通过大量的数据试验,效率确实提高不少。希望这对以后的开发有所启发。

#include <iostream>
using namespace std;

void Merge(int *, int, int, int);
void Merge_Sort(int *, int, int);
void Merge_Sort1(int *, int, int);
void Insertion_sort(int *, int);

int main()
{
    int a[] = {5, 7, 3, 8, 1, 4, 2};
    int len = sizeof(a)/sizeof(int);
    cout<<"Befor Sorting : "<<endl;
    for(int i = 0; i<len; i++)
        cout<<a[i]<<' ';
    cout<<endl;
    
    Merge_Sort1(a, 0, len-1);
    
    cout<<"After Sorting : "<<endl;
    for(int i = 0; i<len; i++)
        cout<<a[i]<<' ';
    cout<<endl;
    
    return 0;
}

void Merge_Sort(int *arr, int left, int right)
{
    if(left<right)
    {
        int middle = ( left + right ) / 2;
        Merge_Sort(arr, left, middle);
        Merge_Sort(arr, middle+1,right);
        Merge(arr, left, middle, right);
    }
    
}

void Merge(int *a, int left, int middle, int right)
{  
    int n1 = middle-left+1;
    int n2 = right-middle;
    int *L = new int[n1+1];
    int *R = new int[n2+1];
    int i, j, k;  
      
    for (i=0; i<n1; i++)
    {  
        L[i] = a[left+i];
    }  
    for (j=0; j<n2; j++)
    {  
        R[j] = a[middle+j+1];
    }  
    L[n1] = 10000000;
    R[n2] = 10000000;
  
    for (i=0, j=0, k=left; k<=right; k++)
    {  
        if (L[i]<=R[j])
        {
            a[k] = L[i];
            i++;
        }
        else
        {
            a[k] = R[j];
            j++;
        }  
    }
    delete []L;
    delete []R;
}

void Insertion_sort(int arr[], int len)
{
    int i, j;
    for(i = 1,j; i < len; i++)
    {
        j = i;
        int v = arr[j];
        while(j > 0 && arr[j-1] > v)
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = v;
    }
}

void Merge_Sort1(int *arr, int left, int right)
{
    if(right-left >=50)
    {
        int middle = ( left + right ) / 2;
        Merge_Sort(arr, left, middle);
        Merge_Sort(arr, middle+1,right);
        Merge(arr, left, middle, right);
    }
    else
    {
        Insertion_sort(arr+left, right-left+1);
    }
}


推荐您阅读更多有关于“排序算法,”的文章

[一个Java程序猿的转型之路,读研深造,专注机器学习推荐算法]
本站所有文章如无特别注明均为原创。作者:吉米酱 ,复制或转载请以超链接形式注明转自 Jimmy小站
原文地址《排序法的优化MergeSort+InsertSort

已有1位网友发表了看法:

1#访客  2015-09-17 17:08:41 回复该评论
jimmy大SB。

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996