黑马程序员技术交流社区

标题: 归并排序 [打印本页]

---

作者: 一直很安静    时间: 2013-11-22 20:02
标题: 归并排序
在网上查的：将目标数组一分为二 分别进行排序后 假设指针a指向第一个数组的第一个元素 指针b指向第二个数组的第一个元素 i为目标数组的索引 初始为0 将ab 进行比较 将较小的那个放入目标数组的索引i处 然后将较小的数组所在子数组的指针和i均加1 重复比较和加1的动作 直到其中一个子数组的指针指向该数组末尾 然后将另一个数组中的数按顺序添加到目标数组末尾即可。然后我自己在写代码的时候第一步就卡了 怎样将一个数组一分为二变为俩数组啊？

---

作者: 何丛    时间: 2013-11-22 20:45
通过下标
int mid = (first + last) / 2;
然后first到mid为一个数组，mid到last为另一个数组

---

作者: 简★零度    时间: 2013-11-22 22:21
package cn.itcase;

import java.util.Arrays;



public class SortTest {



public static void main(String[] args) {

int[] arr = { 2, 5, 3, 1, 4 };

System.out.println("排序前：" + Arrays.toString(arr));



MergeSort.sort(arr);



System.out.println("排序后：" + Arrays.toString(arr));

}



/*

* 交换数组中的两个元素

*/

public static void swap(int[] data, int i, int j) {

int temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

class MergeSort {

public static void sort(int[] data) {

int[] temp = new int[data.length];

mergeSort(data, temp, 0, data.length - 1);

}



private static void mergeSort(int[] data, int[] temp, int l, int r) {

int mid = (l + r) / 2;

if (l == r)

return;

mergeSort(data, temp, l, mid);

mergeSort(data, temp, mid + 1, r);



for (int i = l; i <= r; i++) {

temp[i] = data[i];

}

int i1 = l;

int i2 = mid + 1;

for (int cur = l; cur <= r; cur++) {

if (i1 == mid + 1)

data[cur] = temp[i2++];

else if (i2 > r)

data[cur] = temp[i1++];

else if (temp[i1] < temp[i2])

data[cur] = temp[i1++];

else



data[cur] = temp[i2++];

}

}

}


复制代码

---

作者: 零下五度的水    时间: 2013-11-22 22:31
楼上的，给点注释好么。。。{:soso_e134:}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2