sort-mergesort2.html
来自「经典的数据结构源代码（java 实现）」· HTML 代码 · 共 44 行
HTML
44 行
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color = #ff0080>/** Sorts an array with a comparator using nonrecursive merge sort. */</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>static</font> <E> <font color=#8000a0><font color=#8000a0>void</font> </font><font color=#0000ff>mergeSort</font>(E[] orig, Comparator<E> c) { E[] in =<font color=#0000ff> </font>(E[]) <font color=#8000a0><font color=#ff8000>new</font> </font>Object[orig.length]; <font color=#ff0080>// make a new temporary array</font> System.<font color=#0000ff>arraycopy</font>(orig,0,in,0,in.length); <font color=#ff0080>// copy the input</font> E[] out =<font color=#0000ff> </font>(E[]) <font color=#8000a0><font color=#ff8000>new</font> </font>Object[in.length]; <font color=#ff0080>// output array</font> E[] temp; <font color=#ff0080>// temp array reference used for swapping</font> <font color=#8000a0><font color=#8000a0>int</font> </font>n = in.length; <font color=#ff8000>for</font><font color=#0000ff> </font>(<font color=#8000a0>int</font> i=1; i < n; i*=2) { <font color=#ff0080>// each iteration sorts all length-2*i runs </font> <font color=#ff8000>for</font><font color=#0000ff> </font>(<font color=#8000a0>int</font> j=0; j < n; j+=2*i) <font color=#ff0080>// each iteration merges two length-i pairs</font> <font color=#0000ff>merge</font>(in,out,c,j,i); <font color=#ff0080>// merge from in to out two length-i runs at j</font> temp = in; in = out; out = temp; <font color=#ff0080>// swap arrays for next iteration</font> } <font color=#ff0080>// the "in" array contains the sorted array, so re-copy it</font> System.<font color=#0000ff>arraycopy</font>(in,0,orig,0,in.length); } <font color = #ff0080>/** Merges two subarrays, specified by a start and increment. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>static</font> <E> <font color=#8000a0><font color=#8000a0>void</font> </font><font color=#0000ff>merge</font>(E[] in, E[] out, Comparator<E> c, <font color=#8000a0><font color=#8000a0>int</font> </font>start, <font color=#8000a0><font color=#8000a0>int</font> </font>inc) { <font color=#ff0080>// merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]</font> <font color=#8000a0><font color=#8000a0>int</font> </font>x = start; <font color=#ff0080>// index into run #1</font> <font color=#8000a0><font color=#8000a0>int</font> </font>end1 = Math.<font color=#0000ff>min</font>(start+inc, in.length); <font color=#ff0080>// boundary for run #1</font> <font color=#8000a0><font color=#8000a0>int</font> </font>end2 = Math.<font color=#0000ff>min</font>(start+2*inc, in.length); <font color=#ff0080>// boundary for run #2</font> <font color=#8000a0><font color=#8000a0>int</font> </font>y = start+inc; <font color=#ff0080>// index into run #2 (could be beyond array boundary)</font> <font color=#8000a0><font color=#8000a0>int</font> </font>z = start; <font color=#ff0080>// index into the out array</font> <font color=#ff8000>while</font><font color=#0000ff> </font>(<font color=#0000ff></font>(x < end1) &&<font color=#0000ff> </font>(y < end2)) <font color=#ff8000>if</font><font color=#0000ff> </font>(c.<font color=#0000ff>compare</font>(in[x],in[y]) <= 0) out[z++] = in[x++]; <font color=#8000a0><font color=#ff8000>else</font> </font>out[z++] = in[y++]; <font color=#ff8000>if</font><font color=#0000ff> </font>(x < end1) <font color=#ff0080>// first run didn't finish</font> System.<font color=#0000ff>arraycopy</font>(in, x, out, z, end1 - x); <font color=#8000a0><font color=#ff8000>else</font> </font><font color=#ff8000>if</font><font color=#0000ff> </font>(y < end2) <font color=#ff0080>// second run didn't finish</font> System.<font color=#0000ff>arraycopy</font>(in, y, out, z, end2 - y); }</dl></body></html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?