魔兽7.2国内做插件网站,营销型企业网站系统,摄影网站采用照片做宣传 版权费是多少,如何做网站推广页面07 归并排序 #xff08;Merge Sort#xff09; 归并操作的工作原理如下#xff1a;第一步#xff1a;申请空间#xff0c;使其大小为两个已经排序序列之和#xff0c;该空间用来存放合并后的序列#xff1b;第二步#xff1a;设定两个指针#xff0c;最初位置分别为两… 07 归并排序 Merge Sort 归并操作的工作原理如下 第一步申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 第二步设定两个指针最初位置分别为两个已经排序序列的起始位置 第三步比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 //循环实现void merge(int arr[], int l, int m, int r)
{ int i, j, k; int n1 m - l 1; int n2 r - m; int L[n1], R[n2]; for (i 0; i n1; i) L[i] arr[l i]; for (j 0; j n2; j) R[j] arr[m 1 j]; i 0; j 0; k l; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else{ arr[k] R[j]; j; } k; } while (i n1) { arr[k] L[i]; i; k; } while (j n2) { arr[k] R[j]; j; k; }
} void merge_sort(int arr[], int l, int r)
{ if (l r) { int m l(r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m1, r); merge(arr, l, m, r); }
} //递归实现
void merge(int arr[], int tmp[], int start, int end, int middle) {int l, r, s;s start;l start;r middle 1;while (l middle r end) {if (arr[l] arr[r]) tmp[s] arr[l];else tmp[s] arr[r];}while (l middle) tmp[s] arr[l];while (r end) tmp[s] arr[r];for (;start end;start)arr[start] tmp[start];
}void msort(int arr[], int *tmp, int start, int end) {int middle;if (start end) {middle (start end) / 2;msort(arr, tmp, start, middle);msort(arr, tmp, middle 1, end);merge(arr, tmp, start, end, middle);}
}void merge_sort(int arr[], int n) {int *tmp (int*)malloc(n*sizeof(int));msort(a, tmp, 0, n - 1);free(tmp);
} 空间效率O(n) 时间效率最好情况O(Nlog2N) 平均情况O(Nlog2N) 最坏情况O(Nlog2N) 稳定性相同元素相对位置变化情况稳定 转载于:https://www.cnblogs.com/wanghao-boke/p/10424405.html
