Catalog
  1. 1. 当数据量很大的时候 nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,用nlogn的算法要处理一天的话,用n^2的算法将要处理6020天。这就基本相当于是15年。一个优化改进的算法可能比一个比一个笨的算法速度快了许多,这就是为什么我们要学习算法的原因。
归并排序

前几天遇到了一道题,快排过不去,一定要用mergesort,特来学习一下。

该算法时间复杂度为O(NlogN).

当数据量很大的时候 nlogn的优势将会比n^2越来越大,当n=10^5的时候,nlogn的算法要比n^2的算法快6000倍,那么6000倍是什么概念呢,就是如果我们要处理一个数据集,用nlogn的算法要处理一天的话,用n^2的算法将要处理6020天。这就基本相当于是15年。一个优化改进的算法可能比一个比一个笨的算法速度快了许多,这就是为什么我们要学习算法的原因。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void merge(int a[], int l, int r, int mid) //并的思想
{
int *aux = new int[r - l + 1], i, j, k;
for (k = l; k <= r; k++)
aux[k - l] = a[k];
i = l;
j = mid + 1;
for (k = l; k <= r; k++)
{
if (i > mid)
{
a[k] = aux[j - l];
j++;
}
else if (j > r)
{
a[k] = aux[i - l];
i++;
}
else if (aux[i - l] > aux[j - l])
{
a[k] = aux[j - l];
j++;
}
else
{
a[k] = aux[i - l];
i++;
}
}
}
void merge_sort(int a[], int l, int r)//归的思想
{
if (l >= r)
return;
int mid = (l + r) / 2;
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
merge(a, l, r, mid);
}
void mergesort(int a[], int l, int r)//再写个函数,方标调用
{
merge_sort(a, l, r - 1);
}
int main()
{
int a[105], n, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
mergesort(a, 0, n);
for (i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}

下附运行结果:

Author: superzhaoyang
Link: http://yoursite.com/2019/10/21/归并排序/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝
��