1. 直接插入排序
直接插入排序是通过构建有序序列，对于未排序的序列，将其中的元素在已排序的序列中从后往前扫描，找到相应的位置，将其插入即可。 算法实现步骤： ● 从第一个元素开始，可以把第一个元素当做有序序列； ● 取出下一个元素，在已经排序的有序序列中从后往前扫描； ● 如果这个元素大于有序序列的最后一个元素，向后继续比较； ● 直到这个元素小于有序序列的最后一个元素，将它们交换； ● 重复步骤3； ● 重复步骤2-5。
代码实现：
package org.westos.insertsort; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr = new int[]{-1,6,-2,2,0,-6,5,4,89,10}; System.out.println("排序前："+Arrays.toString(arr)); insertSort(arr); System.out.println("插入排序后："+Arrays.toString(arr)); } public static void insertSort(int[] arr){ //外层循环控制一共比较几轮，从i=1开始是认为它已经是个有序序列，不作比较。 for (int i = 1; i < arr.length; i++) { //内层循环控制每轮比较的次数， // 从第二个元素开始，把它和它的前一个元素比较， // 如果它小于前一个元素，就交换它们的位置。 for (int j = i; j > 0; j--) { if (arr[j] < arr[j - 1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } } }执行结果：
2. 希尔排序
希尔排序就是直接插入排序的改进版，它和直接插入排序的不同之处就在于，它会优先选择距离较远的元素。希尔排序又叫缩小增量排序。 算法实现步骤： ● 选择一个增量序列，t1，t2，…，tk（初始增量d设置为数组的长度/2，往后遍历下一个增量是d/2，以此类推，直到增量等于0）； ● 然后再对每组的增量序列进行直接插入排序。
代码实现：
package org.westos.shellsort; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] arr = new int[]{-1,5,6,9,3,2,0,1,98,56}; System.out.println("未排序的数组："+ Arrays.toString(arr)); shellSort(arr); System.out.println("排序后："+Arrays.toString(arr)); } private static void shellSort(int[] arr) { //遍历所有的增量序列 for (int d = arr.length-1; d > 0; d/=2) { //遍历所有的元素 for (int i = d; i < arr.length; i++) { //遍历每个序列的所有元素 for (int j = i-d; j >= 0; j-=d){ if (arr[j] > arr[j+d]){ int temp = arr[j]; arr[j] = arr[j+d]; arr[j+d] = temp; } } } } } }执行结果：
