插入排序

package sort;


import java.util.ArrayList;
import java.util.Arrays;

public class InsertSortDemo {

    public static void main(String[] args) {
        int[] arr = new int[]{101, 34, 119, 1, 52, 38, 67, 96, 23, 15, 2, 111};
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            //定义待插入的数
            insertVal = arr[i];
            insertIndex = i - 1;//即arr[1]的前面这个数的下标

            //给insertVal找到插入的位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]  = insertVal;
        }
        System.out.println(Arrays.toString(arr));

    }
}

希尔排序的两种实现方式
1)希尔排序时， 对有序序列在插入时采用交换法
2)希尔排序时， 对有序序列在插入时采用移动法

package sort;

import java.util.Arrays;

public class ShellSortDemo {
    public static void main(String[] args) {
        int[] arr = new int[]{101, 34, 119, 1, 52, 38, 67, 96, 23, 15, 2, 111};
        shellSort(arr);
        shellSort2(arr);
    }


    private static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j >= gap && temp <= arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        System.out.println("希尔排序:" + Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println("希尔排序:" + Arrays.toString(arr));
    }

}