逐步分析Java归并排序的实现步骤
引言:
归并排序是一种经典的分而治之算法,将一个数组分成两个较小的数组,然后分别对这两个数组进行排序,最后将两个排序后的数组合并成一个有序的数组。在本文中,我们将逐步解析Java中归并排序的实现过程,并提供具体代码示例。
class MergeSort { // 归并排序函数 public void mergeSort(int[] array, int left, int right) { if (left < right) { // 找出中点 int mid = (left + right) / 2; // 递归排序左半部分和右半部分 mergeSort(array, left, mid); mergeSort(array, mid + 1, right); // 合并排序好的左半部分和右半部分 merge(array, left, mid, right); } } // 合并函数 public void merge(int[] array, int left, int mid, int right) { // 定义临时数组来存储合并后的数组 int[] temp = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; // 将左半部分和右半部分按顺序合并到临时数组中 while (i <= mid && j <= right) { if (array[i] <= array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 将剩余的元素复制到临时数组中 while (i <= mid) { temp[k++] = array[i++]; } while (j <= right) { temp[k++] = array[j++]; } // 将临时数组中的元素复制回原数组 for (int m = 0; m < temp.length; m++) { array[left + m] = temp[m]; } } // 测试 public static void main(String[] args) { int[] array = {8, 5, 2, 9, 5, 6, 3}; int n = array.length; MergeSort mergeSort = new MergeSort(); mergeSort.mergeSort(array, 0, n - 1); System.out.println("归并排序结果:"); for (int i = 0; i < n; i++) { System.out.print(array[i] + " "); } } }
mergeSort
方法是归并排序的入口函数,它接收一个待排序的数组以及数组的左右边界。在该函数中,我们首先判断左右边界是否满足拆分的条件(即left ),如果满足,则找出数组的中点,并递归调用<code>mergeSort
函数对左半部分和右半部分进行排序。最后,调用merge
函数将两个有序的子数组合并为一个有序的数组。mergeSort
方法是归并排序的入口函数,它接收一个待排序的数组以及数组的左右边界。在该函数中,我们首先判断左右边界是否满足拆分的条件(即left ),如果满足,则找出数组的中点,并递归调用<code>mergeSort
函数对左半部分和右半部分进行排序。最后,调用merge
函数将两个有序的子数组合并为一个有序的数组。
merge
函数中,我们创建一个临时数组来存储合并后的子数组,然后定义三个指针i
、j
、k
merge
函数中,我们创建一个临时数组来存储合并后的子数组,然后定义三个指针i
、j
、k
分别指向左半部分的起始位置、右半部分的起始位置以及临时数组的起始位置。我们比较左半部分和右半部分的元素大小,将较小的元素放入临时数组中,并将对应指针后移一位。如果某一个子数组的所有元素都放入了临时数组中,那么我们将剩下子数组中的元素复制到临时数组的末尾。最后,我们将临时数组中的元素复制回原数组。以上是逐步分析Java归并排序的实现步骤的详细内容。更多信息请关注PHP中文网其他相关文章!