FilesExpand file tree

 main

/

Code02_MergeSort.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

182 lines (169 loc) · 3.62 KB

 main

/

Code02_MergeSort.java

Copy path

Top

File metadata and controls

• Code
• Blame

182 lines (169 loc) · 3.62 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

package class08;

public class Code02_MergeSort {

// 递归方法实现

public static void mergeSort1(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

process(arr, 0, arr.length - 1);

}

// arr[L...R]范围上，请让这个范围上的数，有序！

public static void process(int[] arr, int L, int R) {

if (L == R) {

return;

}

// int mid = (L + R) / 2

int mid = L + ((R - L) >> 1);

process(arr, L, mid);

process(arr, mid + 1, R);

merge(arr, L, mid, R);

}

public static void merge(int[] arr, int L, int M, int R) {

int[] help = new int[R - L + 1];

int i = 0;

int p1 = L;

int p2 = M + 1;

while (p1 <= M && p2 <= R) {

help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];

}

// 要么p1越界，要么p2越界

// 不可能出现：共同越界

while (p1 <= M) {

help[i++] = arr[p1++];

}

while (p2 <= R) {

help[i++] = arr[p2++];

}

for (i = 0; i < help.length; i++) {

arr[L + i] = help[i];

}

}

public static void mergeSort2(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

int step = 1;

int N = arr.length;

while (step < N) {

int L = 0;

while (L < N) {

int M = 0;

if (N - L >= step) {

M = L + step - 1;

} else {

M = N - 1;

}

if (M == N - 1) {

break;

}

int R = 0;

if (N - 1 - M >= step) {

R = M + step;

} else {

R = N - 1;

}

merge(arr, L, M, R);

if (R == N - 1) {

break;

} else {

L = R + 1;

}

}

if (step > N / 2) {

break;

}

step *= 2;

}

}

// 非递归方法实现

// public static void mergeSort2(int[] arr) {

// if (arr == null || arr.length < 2) {

// return;

// }

// int N = arr.length;

// int mergeSize = 1;

// while (mergeSize < N) {

// int L = 0;

// while (L < N) {

// if (mergeSize >= N - L) {

// break;

// }

// int M = L + mergeSize - 1;

// int R = M + Math.min(mergeSize, N - M - 1);

// merge(arr, L, M, R);

// L = R + 1;

// }

// if (mergeSize > N / 2) {

// break;

// }

// mergeSize <<= 1;

// }

// }

// for test

public static int[] generateRandomArray(int maxSize, int maxValue) {

int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

for (int i = 0; i < arr.length; i++) {

arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());

}

return arr;

}

// for test

public static int[] copyArray(int[] arr) {

if (arr == null) {

return null;

}

int[] res = new int[arr.length];

for (int i = 0; i < arr.length; i++) {

res[i] = arr[i];

}

return res;

}

// for test

public static boolean isEqual(int[] arr1, int[] arr2) {

if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {

return false;

}

if (arr1 == null && arr2 == null) {

return true;

}

if (arr1.length != arr2.length) {

return false;

}

for (int i = 0; i < arr1.length; i++) {

if (arr1[i] != arr2[i]) {

return false;

}

}

return true;

}

// for test

public static void printArray(int[] arr) {

if (arr == null) {

return;

}

for (int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}

// for test

public static void main(String[] args) {

int testTime = 500000;

int maxSize = 100;

int maxValue = 100;

System.out.println("测试开始");

for (int i = 0; i < testTime; i++) {

int[] arr1 = generateRandomArray(maxSize, maxValue);

int[] arr2 = copyArray(arr1);

mergeSort1(arr1);

mergeSort2(arr2);

if (!isEqual(arr1, arr2)) {

System.out.println("出错了！");

printArray(arr1);

printArray(arr2);

break;

}

}

System.out.println("测试结束");

}

}