排序算法：插入排序和希尔排序

一、插入排序

1.基本原理

���入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2.动态图

3.代码

①:交换方式

public class ThreadNew{    public static void main(String[] args) {        int[] arr = new int[] {6,5,3 ,1,8,7,2,4};        Sort(arr);    }    public static void Sort(int[] arr) {        for (int i = 1; i = 0; j--) {                //前后位置进行交换                if (arr[j] > arr[j+1]) {                    int temp = arr[j];                    arr[j] = arr[j+1];                    arr[j+1] = temp;                }else {                    break;                }            }            System.out.println(Arrays.toString(arr));        }    }}

②:移位方式

public class InsertSort {    public static void main(String[] args) {        int[] arr = {-1,100,4,23,2,45,67,89,-3,56};        System.out.print("排序前：");        System.out.println(Arrays.toString(arr));        insertSort(arr);    }    //直接插入排序（移位方式）    public static void insertSort(int[] arr){        for(int i=1;i           int insertVal = arr[i];           int insertIndex = i;           while (insertIndex0 && insertVal               arr[insertIndex]=arr[insertIndex-1];               insertIndex--;           }           arr[insertIndex] = insertVal;           //输出每趟的结果           System.out.print("第" + i + "轮:");           System.out.println(Arrays.toString(arr));        }        //排序完成后输出最终的结果        System.out.println("==================================================");        System.out.println(Arrays.toString(arr));    }}    public static void main(String[] args) {        int arr[] = new int[]{8,9,1,7,2,3,5,4,6,0};        shellSort(arr);    }    // 使用逐步推导的方式来编写希尔排序    public static void shellSort(int[] arr){        // 第一轮：是将10个数据分成了5组，这里的 i 值得是我们的步长，       // 既 我们的 i 指向一组元素当中的 第二个 ：注意是第二个        for (int i = 5 ;i  arr[j+5]){                    int temp = arr[j];                     arr[j] = arr[j+5];                     arr[j+5] = temp;                }            }        }        // 第二轮：是将10个数据分成了2组，这里的 i 值得是我们的步长，       // 既 我们的 i 指向一组元素当中的 第二个 ：注意是第二个        for (int i = 2 ;i =0; j -= 2){                // 如果当前元素大于加上步长之后的元素，则交换                if(arr[j] > arr[j+2]){                    int temp = arr[j];                    arr[j] = arr[j+2];                    arr[j+2] = temp;                }            }        }        // 第三轮：是将10个数据分成了1组，这里的 i 值得是我们的步长，        // 既 我们的 i 指向一组元素当中的 第二个 ：注意是第二个        for (int i = 1 ;i =0; j -= 1){                // 如果当前元素大于加上步长之后的元素，则交换                if(arr[j] > arr[j+1]){                    int temp = arr[j];                    arr[j] = arr[j+1];                    arr[j+1] = temp;                }            }        }        System.out.println(Arrays.toString(arr));    }        //最后的整合代码            for(int gap = arr.length /2;gap > 0;gap /= 2){                for (int i = gap ;i =0; j -= gap){                        // 如果当前元素大于加上步长之后的元素，则交换                        if(arr[j] > arr[j+gap]){                            int temp = arr[j];                            arr[j] = arr[j+gap];                            arr[j+gap] = temp;                        }                    }                }            }}

完成以后我们来进行一下测试，让他和我们的直接插入排序进行对比。

public static void main(String[] args) {    int[] arr = new int[80000];    for(int i = 0;i 
这个时间差距好像不是我们想要看到的结果。
耗时的原因：交换所产生的的耗时
 
5.移位式 算法实现
 
// 这个算法需要仔细去推敲public static void shellSort2(int[] arr){    for(int gap = arr.length /2;gap > 0;gap /= 2){        for (int i = gap ;i