归并排序
归并排序和快速排序有类似之处,同样采用分治法,不同的是,归并排序不选取基准值,采用递归方式直接将数据分为两个区间,再进行排序合并。需要注意的是,排序实际是从最小单位,即分区大小为1时开始的。
时间复杂度
因为都是从中间划分区间,且无基准值。归并排序时间复杂度较稳定
O(nlogn)
步骤
- 对半划分区间
- 递归,直到分区大小为1
- 依次合并区间
以本次代码的数据为例,原始数据为:
10, 15, 14, 85, 45, 62, 312, 47, 51, 84, 99, 78, 41
第一次划分区间后为:
10, 15, 14, 85, 45, 62
312, 47, 51, 84, 99, 78, 41
左分区第二次划分:
10, 15, 14
85, 45, 62
左分区第三次划分:
10
15, 14
85
45, 62
左分区第四次划分:
10
15
14
85
45
62
随后合并分区得到:
10
14, 15
85
45, 62
再次合并:
10, 14, 15
45, 62, 85
直到完成合并
代码实现
/*归并排序*/ #include <iostream> using namespace std; int *Merge( int *arr1, int len1, int *arr2, int len2 ) //从小到大合并值 { int *arr3 = new int[len1 + len2]; int p1 = 0, p2 = 0, p3 = 0; while ( p1 < len1 && p2 < len2 ) { if ( p1 < len1 && arr1[p1] <= arr2[p2] ) { arr3[p3++] = arr1[p1++]; } else { arr3[p3++] = arr2[p2++]; } } //收尾处理 while ( p1 < len1 ) { arr3[p3++] = arr1[p1++]; } while ( p2 < len2 ) { arr3[p3++] = arr2[p2++]; } return arr3; } void MergeSort( int *arr, int len ) { int *arr1 = new int[len / 2]; int *arr2 = new int[len - len / 2]; if ( len > 1 ) { for ( int i = 0; i < len / 2; i++ ) { arr1[i] = arr[i]; } MergeSort( arr1, len / 2 );//分治递归 for ( int i = 0; i < len - len / 2; i++ ) { arr2[i] = arr[len / 2 + i]; } MergeSort( arr2, len - len / 2 );//分治递归 int *date = Merge( arr1, len / 2, arr2, len - len / 2 ); for ( int i = 0; i < len; i++ ) { arr[i] = date[i]; } delete date; } } int main() { int arr[] = {10, 15, 14, 85, 45, 62, 312, 47, 51, 84, 99, 78, 41}; int len = sizeof( arr ) / sizeof( arr[0] ); MergeSort( arr, len ); int i = 0; while ( i < len ) { cout << arr[i++] << endl; } return 0; }