主要思想:分治。
步骤:
1.确定分界点:mid=(left+right)/2;
2.分别递归排序right and left;
3.归并左右两边。
归并方法:1)两指针分别指向两数组的第一个数,数列最小值是两者其中之一;
2)取两指针所指数的最小值,作为有序数组的下一个数;
3)被取值的指针后移一位,再与另一指针所指数比较;
4)重复上述过程,直到有一数组值被取完;
5)将数组剩余的数直接连接到有序数列后。
eg.从小到大
void merge_sort(int q[], int l, int r) { if (l >= r)return; //未排列数列只剩一个或没有数时退出 //确定分界点 int mid = (l + r) / 2; //两边分别递归 merge_sort(q, l, mid); merge_sort(q, mid + 1, r); //合二为一 int k = 0, i = l, j = mid + 1;//i取第一个数组,j取第二个 while (i <= mid && j <= r) { if (q[i] <= q[j]) { t[k++] = q[i++]; } else { t[k++] = q[j++]; } } //如果有一数组已经被去完,则直接连接剩余的数 while (i <= mid) { t[k++] = q[i++]; } while (j <= r) { t[k++] = q[j++]; } //把替换数组t存入原数组 for (i = l,j=0; i <= r; j++,i++) { q[i] = t[j]; } }
eg.从小到大
void merge_sort(int q[], int l, int r) { if (l >= r)return; int mid = (l + r) / 2; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (q[i] >= q[j])//只需更改此处运算符号 { t[k++] = q[i++]; } else { t[k++] = q[j++]; } } while (i <= mid) { t[k++] = q[i++]; } while (j <= r) { t[k++] = q[j++]; } for (i = l,j=0; i <= r; j++,i++) { q[i] = t[j]; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)