Last active
December 14, 2015 13:18
-
-
Save doubledouble/5092531 to your computer and use it in GitHub Desktop.
插入排序,归并排序
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package test.algorithm; | |
import java.util.Arrays; | |
/** | |
* from wiki http://zh.wikipedia.org/wiki/插入排序 | |
* http://zh.wikipedia.org/wiki/归并排序 | |
**/ | |
public class ALG { | |
/** | |
* @param args | |
*/ | |
public static void main(String[] args) { | |
Comparable[] c = {1,5,3,0,9,8}; | |
System.out.println("before sort: " + Arrays.asList(c)); | |
insertionSort(c); | |
System.out.println("after sort: " + Arrays.asList(c)); | |
System.out.println("====================================="); | |
Comparable[] d = {1,5,3,0,9,8}; | |
System.out.println("before sort: " + Arrays.asList(d)); | |
mergeSort(d); | |
System.out.println("after sort: " + Arrays.asList(d)); | |
} | |
public static void insertionSort(Comparable<Object>[] data) { | |
InsertionSort.sort(data); | |
} | |
public static <T extends Comparable<? super T>> void mergeSort(T[] data) { | |
MergeSort.sort(data); | |
} | |
} | |
class InsertionSort { | |
public static void sort(Comparable<Object>[] data) { | |
for (int index=1; index<data.length; index++) { | |
Comparable<Object> key = data[index]; | |
int pos = index; | |
// shift larger values to the right | |
while ( pos > 0 && data[pos-1].compareTo(key) > 0 ) { | |
data[pos] = data[pos-1]; | |
pos--; | |
} | |
data[pos] = key; | |
} | |
} | |
} | |
class MergeSort { | |
@SuppressWarnings("unchecked") | |
public static <T extends Comparable<? super T>> void sort(T[] arr) { | |
T[] tmpArr = (T[]) new Comparable[arr.length]; | |
sort(arr, tmpArr, 0, arr.length - 1); | |
} | |
private static <T extends Comparable<? super T>> void sort(T[] arr, T[] tmpArr, int start, int end) { | |
if (start < end) { | |
int mid = (start + end) / 2; | |
System.out.printf("sort (%d-%d, %d-%d) %s\n", start, mid, mid + 1, end, Arrays.asList(arr)); | |
sort(arr, tmpArr, start, mid); | |
sort(arr, tmpArr, mid + 1, end); | |
merge(arr, tmpArr, start, mid + 1, end); | |
System.out.printf("merge (%d-%d, %d-%d) %s\n", start, mid, mid + 1, end, Arrays.asList(arr)); | |
} | |
} | |
private static <T extends Comparable<? super T>> void merge(T[] arr, T[] tmpArr, int lPos, int rPos, int rEnd) { | |
int lEnd = rPos - 1; | |
int tPos = lPos; | |
int leftTmp = lPos; | |
while (lPos <= lEnd && rPos <= rEnd) { | |
if (arr[lPos].compareTo(arr[rPos]) <= 0) { | |
tmpArr[tPos++] = arr[lPos++]; | |
} else { | |
tmpArr[tPos++] = arr[rPos++]; | |
} | |
} | |
//copy the rest element of the left half subarray | |
while (lPos <= lEnd) { | |
tmpArr[tPos++] = arr[lPos++]; | |
} | |
//copy the rest element of the right half subarray.(only one loop will be execute) | |
while (rPos <= rEnd) { | |
tmpArr[tPos++] = arr[rPos++]; | |
} | |
//copy the tmpArr back cause we need to change the arr array items. | |
for (; rEnd >= leftTmp; rEnd--) { | |
arr[rEnd] = tmpArr[rEnd]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
before sort: [1, 5, 3, 0, 9, 8]
after sort: [0, 1, 3, 5, 8, 9]
before sort: [1, 5, 3, 0, 9, 8]
sort (0-2, 3-5) [1, 5, 3, 0, 9, 8]
sort (0-1, 2-2) [1, 5, 3, 0, 9, 8]
sort (0-0, 1-1) [1, 5, 3, 0, 9, 8]
merge (0-0, 1-1) [1, 5, 3, 0, 9, 8]
merge (0-1, 2-2) [1, 3, 5, 0, 9, 8]
sort (3-4, 5-5) [1, 3, 5, 0, 9, 8]
sort (3-3, 4-4) [1, 3, 5, 0, 9, 8]
merge (3-3, 4-4) [1, 3, 5, 0, 9, 8]
merge (3-4, 5-5) [1, 3, 5, 0, 8, 9]
merge (0-2, 3-5) [0, 1, 3, 5, 8, 9]
after sort: [0, 1, 3, 5, 8, 9]