Skip to content

Instantly share code, notes, and snippets.

@doubledouble doubledouble/ALG.java
Last active Dec 14, 2015

Embed
What would you like to do?
插入排序,归并排序
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];
}
}
}
@doubledouble

This comment has been minimized.

Copy link
Owner Author

doubledouble commented Mar 6, 2013

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]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.