算法分析
归并排序算法的时间复杂度能达到nlog(n)。
归并排序算法的基本思想:归并排序算法是把数据逐次分割成每块,对每块进行排序后,然后再进行合并成为一个排好序的数据。
第一步:数据平均分割
第二步:再次对数据进行平均分割,直到数据无法再分割,也就是每份数据只有一个了,然后再对每份数据进行合并,依次向上进行合并每份有序的数据。
根据以上算法的基本思想,相信大家也想到了,归并排序使用递归实现起来相对更加简单。以上所说的归并排序为自顶向下的归并排序算法,还有一种自底向上的归并排序算法实现下边再说。
自顶向下归并排序
以下是自顶向下的归并排序算法的实现示例:
template<typename T>
void __merge(T arr[], int l, int mid, int r)
{
//int aux[r - l + 1]; //数据量达到千万时,申请数组程序崩溃
int *aux = new int[r-l+1];
for(int i = l; i <= r; i++)
aux[i - l] = arr[i];
int i = l, j = mid +1;
for(int k= l; k <= r; k++)
{
if(i > mid)
{
arr[k] = aux[j-l]; j++;
}
else if(j > r)
{
arr[k] = aux[i-l]; i++;
}
else if(aux[i-l] < aux[j-l])
{
arr[k] = aux[i-l]; i++;
}
else{
arr[k] = aux[j-l]; j++;
}
}
delete []aux;
}
template<typename T>
void __mergeSort(T arr[], int l, int r)
{
if(r - l <= 15) //优化点2:对小数据量使用插入排序
{
insertionSort(arr, l, r);
return ;
}
int mid = (l + r)/2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
if(arr[mid] > arr[mid+1]) //优化点1:对于arr[mid] <= arr[mid+1]的情况不需要进行merge
__merge(arr, l, mid, r);
}
//此为自顶向下的归并排序算法
template<typename T>
void mergeSort(T arr[], int n)
{
__mergeSort(arr, 0, n - 1);
}
自底向上归并排序
自底向上的归并排序算法与自顶向下的归并排序正好相反,先指定一个步长,把数据按步长分割,每份数据使用插入排序算法(插入排序对小数据量性能好,插入排序参考博文)
示例代码:
template<typename T>
void insertionSort(T arr[], int l, int r)
{
for(int i = l+1; i <= r; i++)
{
T tmp = arr[i];
int j;
for(j = i; j > l && arr[j - 1] > tmp; j --)
arr[j] = arr[j - 1];
arr[j] = tmp;
}
}
//此为自底向上的归并排序算法
template<typename T>
void mergeSortBU(T arr[], int n)
{
for(int i = 0; i < n; i += 16)
insertionSort(arr, i, min(i+15, n-1));
for(int sz = 16; sz < n; sz += sz)
for(int i = 0; i < n - sz; i += sz+sz)
if(arr[i+sz-1] > arr[i+sz])
__merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));
}
总结
归并排序算法的时间复杂度为nlog(n),相对与时间复杂度为O(n^2)的选择排序、插入排序、冒泡排序等基础排序算法更好,但在小数据量或者几乎有序的数据中,时间复杂度为O(n^2)的插入排序与nlog(n)的归并排序相差无几。