Java归并排序

你的名字 2023-09-27 16:06 8阅读 0赞
  1. /**
  2. * 归并排序
  3. * 归并就是合并的意思
  4. *
  5. * @author 小流慢影
  6. * @date 2023年3月17日
  7. */
  8. public class MergeSort {
  9. public static void main(String[] args) {
  10. int[] array = {5, 4, 3, 1, 2, 13, 12, 10, 11, 9, 7, 8, 6, 3, 5};
  11. System.out.println("原数组:" + Arrays.toString(array));
  12. int[] newArray = mergeSort(array, 0, array.length - 1);
  13. System.out.println("新数组:" + Arrays.toString(newArray));
  14. }
  15. /**
  16. * 归并排序
  17. * @param array 待排数组
  18. * @param start 开始位置
  19. * @param end 结束位置
  20. * @return 排好序的新数组
  21. */
  22. public static int[] mergeSort(int[] array, int start, int end) {
  23. // 边界条件判断:如果开始位置和结束位置相等,直接把值放到新的数组返回
  24. if (start == end) {
  25. return new int[]{array[start]};
  26. }
  27. // 取中间点
  28. int middle = (start + end) / 2;
  29. // 递归操作:对中间点左边的数组进行排序
  30. int[] leftArray = mergeSort(array, start, middle);
  31. // 递归操作:对中间点右边的数组进行排序
  32. int[] rightArray = mergeSort(array, middle + 1, end);
  33. // 对上面左边和右边排好序的数组最后再进行一次合并排序操作
  34. return lastMergeSort(leftArray, rightArray);
  35. }
  36. /**
  37. * 最后合并排序
  38. * @param leftArray 左边排好序的数组
  39. * @param rightArray 右边排好序的数组
  40. * @return 合并后排好序的新数组
  41. */
  42. private static int[] lastMergeSort(int[] leftArray, int[] rightArray) {
  43. // 创建一个新数组,长度等于左右数组之和
  44. int[] newArray = new int[leftArray.length + rightArray.length];
  45. // 新数组的下标,从0开始
  46. int newIndex = 0;
  47. // 左边数组的下标,从0开始
  48. int leftIndex = 0;
  49. // 右边数组的下标,从0开始
  50. int rightIndex = 0;
  51. // 左下标的值与右下标的值进行比较,更小的值赋给新的数组
  52. while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
  53. newArray[newIndex++] =
  54. leftArray[leftIndex] <= rightArray[rightIndex]
  55. ? leftArray[leftIndex++]
  56. : rightArray[rightIndex++];
  57. }
  58. // 如果右数组弄完了,则直接把左数组剩下的都赋给新的数组
  59. while (leftIndex < leftArray.length) {
  60. newArray[newIndex++] = leftArray[leftIndex++];
  61. }
  62. // 如果左数组弄完了,则直接把右数组剩下的都赋给新的数组
  63. while (rightIndex < rightArray.length) {
  64. newArray[newIndex++] = rightArray[rightIndex++];
  65. }
  66. return newArray;
  67. }
  68. }

发表评论

表情:
评论列表 (有 0 条评论,8人围观)

还没有评论,来说两句吧...

相关阅读

    相关 java排序--归并排序

    1.概念: 归并(Merge)[排序][Link 1]法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序

    相关 排序-归并排序-Java

    归并是利用二叉树的思想来实现 将一个数组分成2个,再次分,再次分。一直分,然后再利用递归来实现。1个和另一个组成一个,两个再与另外两个有序的组成一个大的。一直进行下去。 !

    相关 归并排序java

    归并排序采用分治思想,递归的缩小规模来进行排序。先分后合,分治减少了比较次数,而合并仅仅只是移动元素。在java中,进行一次元素比较可能是昂贵的,但是移动元素则是省时的(

    相关 Java归并排序

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然

    相关 java归并排序

    归并排序 稳定性:稳定 归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一