Jimmy小站
小明也有大梦想 — 蒋明/铭排序法的优化MergeSort+InsertSort
2015-09-17 / 数据结构算法 / 4182 次围观 / 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); } }
推荐您阅读更多有关于“排序算法,”的文章
- 上一篇:搞笑段子:两个程序员的故事
- 下一篇: JUST搜搜信息检索能力大赛入口
本月热文
Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996
已有1位网友发表了看法:
发表评论