排序算法之插入排序(Java)

xiaoxiao2021-02-28  23

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

一、直接插入排序(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]); } }

转载请注明原文地址: https://www.6miu.com/read-1099985.html

最新回复(0)