input:{31,41,59,26,41,58}
output:{31,26,41,41,58,59}
伪代码:
InsertionSort(A, n) { for j = 2 to n { key = A[j]; i = j - 1; while (i > 0) and (A[i] > key) { A[i+1] = A[i]; i = i - 1; } A[i+1] = key; } }
真代码:
public static int[] insertionSoftIntArr(int[] A){ for (int i = 2; i < A.length; i++) { int key = A[i]; int j = i -1; while (j > 0 && A[j] > key){ A[j+1] = A[j]; j = j -1; } A[j+1] = key; } return A; }
执行流程:
2.1-2 重写InsertSoft算法使之递减
伪代码:
InsertionSort(A, n) { for j = 1 to n { key = A[j]; i = j - 1; while (i >= 0) and (A[i] < key) { A[i+1] = A[i]; i = i - 1; } A[i+1] = key; } }
真实代码:
public static int[] RewriteinsertionSoftIntArr(int[] A){ for (int i = 1; i < A.length; i++) { int key = A[i]; int j = i -1; while (j >= 0 && A[j] < key){ A[j+1] = A[j]; j = j -1; } A[j+1] = key; } return A; }
过程略
全部代码:
package 测试学习; /** * 插入排序 * 输入:{31,41,59,26,41,58} * */ public class insertionSoft { public static void main(String[] args) { int [] A = {31,41,59,26,41,58}; A = RewriteinsertionSoftIntArr(A); for (int i = 0; i < A.length; i++) { System.out.print(A[i]+" "); } } public static int[] insertionSoftIntArr(int[] A){ for (int i = 2; i < A.length; i++) { int key = A[i]; int j = i -1; while (j > 0 && A[j] > key){ A[j+1] = A[j]; j = j -1; } A[j+1] = key; } return A; } /** * 重写 * @param A * @return */ public static int[] RewriteinsertionSoftIntArr(int[] A){ for (int i = 1; i < A.length; i++) { int key = A[i]; int j = i -1; while (j >= 0 && A[j] < key){ A[j+1] = A[j]; j = j -1; } A[j+1] = key; } return A; } }