算法——归并排序(自顶向下、自底向上)
自顶向下
#include <iostream> #include <algorithm> #include "InsertionSort.h" using namespace std; template<typename T> // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 void __merge(T arr[] , int l, int mid, int r){ T aux[r-l+1]; // 将数组复制一份到aux[] for( int i = l ; i <= r ; i ++ ) aux[i-l] = arr[i]; // 初始化,i、j指向左、右半部分的起始索引位置 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++; } } } // 递归使用归并排序,对arr[l...r]的范围进行排序 template<typename T> void __mergeSort(T arr[] , int l, int r){ if( l >= r) return; int mid = (l+r)/2; __mergeSort(arr,l,mid); __mergeSort(arr,mid+1,r); // 优化,前后两部分有序时不归并 if( arr[mid] > arr[mid+1] ) __merge(arr, l, mid, r); } template<typename T> void mergeSort(T arr[] , int n){ __mergeSort( arr , 0 , n-1 ); }
自底向上
//自底向上归并,可对链表排序 template<typename T> void mergeSortBU(T arr[], int n){ for( int sz = 1 ; sz <= n ; sz += sz ) for( int i = 0 ; i + sz < n ; i += sz + sz ) // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并 __merge( arr , i , i + sz - 1 , min(i + sz + sz -1,n-1)); }
应用:求逆序对
相关推荐
nongfusanquan0 2020-08-18
Broadview 2020-07-19
数据与算法之美 2020-07-05
Masimaro 2020-06-21
wonner 2020-06-17
Oudasheng 2020-06-04
从零开始 2020-06-05
清溪算法君老号 2020-06-01
风吹夏天 2020-05-26
yangjingdong00 2020-05-11
Tips 2020-04-30
troysps 2020-04-26
ustbfym 2020-04-25
清溪算法君老号 2020-04-24
dushine00 2020-04-19
数据与算法之美 2020-04-18
wulaxiaohei 2020-04-17
nurvnurv 2020-04-16