归并排序www

package sort_;public class 归并排序 {public 归并排序() {}/*** 归并排序入口*/public void merge_sort(int[] arr, int n) {//  分配一个辅助数组int[] tempArr = new int[n];this.msort(arr, tempArr, 0, n - 1);}/*** 归并排序*/private void msort(int[] arr, int[] tempArr, int left, int right) {//  如果只有一个元素，那么就不需要继续划分//  只有一个元素的区域，本身就是有序的，只需要归并即可if (left < right) {//  找中间点int mid = (left + right) / 2;//  递归划分左半区this.msort(arr, tempArr, left, mid);//  递归划分右半区this.msort(arr, tempArr, mid + 1, right);//  合并已经排序的部分this.merge(arr, tempArr, left, mid, right);}}/*** 合并*/private void merge(int[] arr, int[] tempArr, int left, int mid, int right) {//  标记左半区第一个未排序的元素int l_pos = left;//  标记右半区第一个未排序的元素int r_pos = mid + 1;//  临时数组元素的下标int pos = left;//  合并while (l_pos <= mid && r_pos <= right) {if (arr[l_pos] < arr[r_pos]) {      //  左半区第一个剩余元素更小tempArr[pos++] = arr[l_pos++];} else {                            //  右半区第一个剩余元素更小tempArr[pos++] = arr[r_pos++];}}//  合并左半区剩余的元素while (l_pos <= mid) {tempArr[pos++] = arr[l_pos++];}//  合并右半区剩余的元素while (r_pos <= right) {tempArr[pos++] = arr[r_pos++];}//  把临时数组中合并后的元素复制回原来的数组while (left <= right) {arr[left] = tempArr[left];left++;}}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！