算法 排序算法之归并排序
归并排序
归并排序主要是二路归并排序
基本思想
- 设数组a中存放了n个数据元素
- 初始时把它们看成n个长度为1的有序子数组，然后从第一个子数组开始，把相邻子数组两两合并，得到n/2的整数上界个长度为2的新的有序子数组（当n为奇数时最后一个新的有序子数组的长度为1）
- 对这些新的有序子数组再两两合并，直到最后长度为n的有序数组位置
排序过程
以数组{50,10,90,30,70,40,80,60,20}为例
代码实现
void Merge(DataType a[], int n, DataType swap[], int k) {/*k为有序子数组的长度，一次二路归并排序后的有序子序列放在数组swap中*/int m = 0, u1, l2, i, j, u2;/*第一个有序子数组下界为0*/int l1 = 0;while (l1 + k <= n - 1) {l2 = l1 + k;//计算第二个有序子数组下界u1 = l2 - 1;//计算第一个有序子数组上界u2 = (l2 + k - 1 <= n - 1) ? l2 + k - 1 : n - 1;//计算第二个有序子数组上界/*两个有序子数组合并*/for (i = l1, j = l2; i <= u1 && j <= u2; m++) {if (a[i] <= a[j]) {swap[m] = a[i];i++;} else {swap[m] = a[j];j++;}}/*子数组2已归并完，将数组1中剩余的元素放到数组swap中*/while (i <= u1) {swap[m] = a[i];m++;i++;}/*子数组1已归并完，将数组2中剩余的元素放到数组swap中*/while (j <= u2) {swap[m] = a[j];m++;j++;}l1 = u2 + 1;}/*将原始数组中只够一组的元素顺序放到数组swap中*/for (i = l1; i < n; i++, m++) {swap[m] = a[i];}}void MergeSort(DataType a[], int n) {int i, k = 1;//归并长度从1开始DataType * swap;swap = (DataType *) malloc(sizeof(DataType) * n);while (k < n) {Merge(a, n, swap, k);for (i = 0; i < n; i++) {a[i] = swap[i];}k = 2 * k;}free(swap);}
java实现
public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);}private static void mergeSort(int[] arr, int low, int high) {int mid = (low + high) / 2;if (low < high) {//左边mergeSort(arr, low, mid);//右边mergeSort(arr, mid + 1, high);//左右归并merge(arr, low, mid, high);}}private static void merge(int[] arr, int low, int mid, int high) {int[] temp = new int[high - low + 1];int left = low;//左指针int right = mid + 1;//右指针int k = 0;//把较小的数先移动到新数组中while (left <= mid && right <= high) {if (arr[left] < arr[right]) {temp[k++] = arr[left++];} else {temp[k++] = arr[right++];}}//把左边剩余的数移入数组while (left <= mid) {temp[k++] = arr[left++];}//把右边剩余的数移入数组while (right <= high) {temp[k++] = arr[right++];}//把新数组中的数覆盖nums数组for (int k2 = 0; k2 < temp.length; k2++) {arr[k2 + low] = temp[k2];}}
算法分析
- 时间复杂度
* 一次二路归并排序归并的次数log2n 每次比较次数n-1 故时间复杂度是O(nlog2n)
- 空间复杂度
* 使用了n个临时内存单元存放数据 空间复杂度O(n)
- 稳定性
* 归并排序是一种**比较占内存**，但却**效率高且稳定**的算法
梦里梦外;
不念不忘少年蓝@
向右看齐
ゞ 浴缸里的玫瑰
你的名字
还没有评论，来说两句吧...