排序算法之插入排序（Java）

插入排序包括直接插入排序和希尔插入排序

一、直接插入排序（directSort）

算法思想：定义一个备份，并赋予值为数组第i个元素，然后依次和第i个元素前面元素的进行比较， 如果有某一个位置上大于它,则将该位置后移 ，直到某一位置小于它，则就将备份赋值给该位置的后一位元素。

时间复杂度：O(n²),如果待排序的序列为正序的话，则时间复杂度为O(n)

二、希尔排序（shellSort）

算法思想：将待排序的数组等分为若干个分别进行直接插入排序，算法步骤，创建一个n，并将n=数组.length，每次循环都对n/2向上取整，即令n=[Math.ceil(n/2)],然后从数组第一位开始，比较与之下标相差n的元素，如果位置靠前的元素大于位置靠后的，则交换位置。

时间复杂度：O(n)

Java代码实现：

public class SortTestTest { SortTest st = new SortTest(); Scanner sc = new Scanner(System.in); String a[] = null; @Test public void testDirectSort() { System.out.println("请输入想要排序的数字串，数字之间以逗号分隔："); String input = sc.nextLine(); a = input.split(","); st.directSort(a); } @Test public void testHillSort() { System.out.println("请输入想要排序的数字串，数字之间以逗号分隔："); String input = sc.nextLine(); a = input.split(","); st.hillSort(a); } } public class SortTest { // 直接插入排序 public void directSort(String array[]) { System.out.println("原序列如下："); for (int i = 0; i < array.length - 1; i++) { System.out.print(array[i] + ","); } System.out.println(array[array.length - 1]); for (int i = 1; i < array.length; i++) { String copy = array[i]; int j; for (j = i - 1; j >= 0; j--) { if (Integer.parseInt(array[j]) > Integer.parseInt(copy)) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = copy; } System.out.println("通过直接排序后："); for (int i = 0; i < array.length - 1; i++) { System.out.print(array[i] + ","); } System.out.println(array[array.length - 1]); } // 希尔插入排序 public void hillSort(String array[]) { System.out.println("原序列如下："); for (int i = 0; i < array.length - 1; i++) { System.out.print(array[i] + ","); } System.out.println(array[array.length - 1]); double n = array.length; // for (int k = 0; k < Integer.MAX_VALUE; k++) { while (true) { n = Math.ceil(n / 2); int n1 = (int) n; if (n1 > 0) { for (int i = 0; i < array.length - n1; i++) { if (Integer.parseInt(array[i]) > Integer.parseInt(array[i + n1])) { String m = array[i + n1]; array[i + n1] = array[i]; array[i] = m; } } if (n1 == 1) { break; } } } System.out.println("通过希尔排序后："); for (int i = 0; i < array.length - 1; i++) { System.out.print(array[i] + ","); } System.out.println(array[array.length - 1]); } }