通过Java实现插入排序（直接插入，希尔）与选择排序（直接选择，堆排）

目录

（一）插入排序

1.直接插入排序

（1）核心思想：

（2）代码实现（以从小到大排序为例）：

（3）代码分析：

2.希尔排序（缩小增量排序）

（1）核心思想：

（2）代码实现（以从小到大排序为例）：

（3）代码分析：

（二）选择排序

1.直接选择排序

（1）核心思想：

（2）代码实现（以从小到大排序为例）：

（3）代码分析：

2.堆排序

（1）核心思想：

（2）代码实现（以从小到大排序为例）：

（3）代码分析：

（三）示例以及各算法耗时参考

1.代码结构

2.程序源码

（1）Sort类：

（2）Test类：

3.测试结果

编辑

（一）插入排序

1.直接插入排序

（1）核心思想：

直接插入排序，顾名思义，即将非有序部分的元素按大小规律逐个插入到有序的部分中，最终使得整体有序。举个简单的例子：当我们在玩扑克牌逐个摸牌时，就会将新牌插入到原来有序的手牌中，此时其实就用到了插入排序的思想。

（2）代码实现（以从小到大排序为例）：

    public static void insertSort(int[] array){//遍历非有序部分数组for(int i=1;i<array.length;i++){//取出非有序部分的第一个元素并向前逐个比对int tmp=array[i];int j=i-1;for(;j>=0;j--){if(tmp<array[j]){//若该元素比前面某元素小，则某元素后移，该元素继续向前比对array[j+1]=array[j];}else{//相反若该元素比前面某元素大，则退出循环break;}//内层循环结束说明已经为该元素找到合适位置，直接插入即可array[j+1]=tmp;}}}

（3）代码分析：

1）时间复杂度：最好情况下（数组本身有序）：O(N)；最坏情况下（数组本身逆序）：O(N^2)。

2）空间复杂度：O（1）（即并未申请额外内存）。

3）稳定性：稳定。

由上可知对于越有序的数组，使用直接插入排序更有优势。

2.希尔排序（缩小增量排序）

（1）核心思想：

希尔排序，又称为缩小增量排序，其本质为直接插入排序的优化形式，在直接插入排序的基础上采取了分治（即分而治之，分组考虑）的思想：通过设定元素下标间隔增量gap来将一组元素分为多组，分别进行直接插入排序，将每个组排完序后将gap减小重复上述过程，直到gap为1，上述全过程整租元素都在不断趋于有序，最终实现排序效果。

例如：数组元素为10时且设定第一次gap为5的情况：

（2）代码实现（以从小到大排序为例）：

//实现希尔排序方法public static void shellSort(int[] array){//设定间隔增量gapint gap=array.length;while (gap > 1) {//每次循环缩小间隔增量gap/=2;//以间隔增量对数组进行分组插入排序shellSortChild(array,gap);}}//实现希尔排序的底层方法private static void shellSortChild(int[]array,int gap){//遍历非有序部分数组，i++表示对每组进行交替排序for(int i=gap;i<array.length;i++){//取出非有序部分的第一个元素并向前逐个比对int tmp=array[i];int j=i-gap;for(;j>=0;j-=gap){if(tmp<array[j]){//若该元素比前面某元素小，则某元素后移，该元素继续向前比对array[j+gap]=array[j];}else{//相反若该元素比前面某元素大，则退出循环break;}//内层循环结束说明已经为该元素找到合适位置，直接插入即可array[j+gap]=tmp;}}}

（3）代码分析：

1）时间复杂度：目前无法严格证明，原因是该算法根据gap的取法不同而不同（本题中gap取法为二分法，即不断除以二），并且当gap较大时每组遍历次数较少，gap较小时整体又更有序，无法进行严格计算，但有学者通过大量实验证明希尔排序的时间复杂度应该介于N^1.25~1.6N^1.25之间，可以估计为O(N^1.3)。

2）空间复杂度：O（1）（即并未申请额外内存）。

3）稳定性：不稳定。

联系直接插入排序可知，希尔排序可以克服传统直接插入排序在完全逆序情况下时间复杂度过高的劣势。

（二）选择排序

1.直接选择排序

（1）核心思想：

直接选择排序，顾名思义，即每一次从非有序部分的元素中选出最小（或最大）的一个元素，存放在非有序部分的起始位置，直到全部非有序部分元素全部排完，此时整组元素有序。

（2）代码实现（以从小到大排序为例）：

    //实现直接选择排序public static void selectSort(int[]array){//遍历非有序部分数组for(int i=0;i< array.length;i++){//默认最小值下标为起始下标int minIndex=i;//遍历剩余部分寻找最小值下标for(int j=i+1;j< array.length;j++){if(array[j]<array[i]){minIndex=j;}}//循环结束证明已经找到最小值下标，与非有序部分起始位置交换int tmp=array[minIndex];array[minIndex]=array[i];array[i]=tmp;}}

（3）代码分析：

1）时间复杂度：无论何时均为O(N^2)。

2）空间复杂度：O（1）（即并未申请额外内存）。

3）稳定性：不稳定。

2.堆排序

（1）核心思想：

利用堆的优先级特性，升序排列建大堆，降序排列建小堆，每次将堆顶元素和未排序堆尾元素互换后进行向上调整（这样堆尾元素一定是当前堆的最值），最终整个堆有序。（思路类似于直接选择排序或者冒泡排序，即每次都将未排序的部分中的最值放于末尾，如此最终整个数组有序）。

（2）代码实现（以从小到大排序为例）：

    //实现堆排序//创建一个大根堆的方法public static void createMaxHeap(int[] array){//从最后一棵子树倒序调整for(int parent=((array.length-1-1)/2);parent>=0;parent--){//调用向下调整的底层方法maxSiftDown(array,parent,array.length-1);}}//创建大根堆时调用到的向下调整的底层方法private static void maxSiftDown(int[]array,int parent,int end){//默认子女中的最大值为左子女int child=2*parent+1;while(child<end){//判断右子女是否为二者中最大值if(child+1<end){if(array[child]<array[child+1]){child++;}}if(array[parent]<array[child]){//子女节点中最大值大于双亲则进行交换调整int temp=array[parent];array[parent]=array[child];array[child]=temp;//向下迭代parent=child;child=2*parent+1;}else{//子女节点中最大值小于双亲说明该树已经为大根堆，无需向下调整，直接中断即可break;}}}//利用创建的大根堆实现堆排序public static void heapSort(int[]array){createMaxHeap(array);int end= array.length-1;while(end>0){//将堆顶元素和堆尾元素交换int temp=array[end];array[end]=array[0];array[0]=temp;//利用大根堆向下调整的方法maxSiftDown(array,0,end);end--;}}

（注：堆的创建，向上调整部分具体思路及讲解可见本人博客：通过Java模拟实现堆（大根堆与小根堆）及其相关操作http://t.csdnimg.cn/JZlWL ）

（3）代码分析：

1）时间复杂度：O(N^log N)。

2）空间复杂度：O（1）（即并未申请额外内存，注意建堆也是在原数组上进行操作的）。

3）稳定性：不稳定。

（三）示例以及各算法耗时参考

1.代码结构

1. Sort类：内部实现直接选择排序，希尔排序，直接插入排序，堆排序相关方法（即上文实现的四种算法）

2.Test类：实现创建顺序数组，逆序数组，随机数组的方法（用来测试四种算法）以及测量四种算法耗时的方法，并在main方法中进行示例演示。

2.程序源码

（1）Sort类：

public class Sort {//实现直接插入排序方法public static void insertSort(int[] array){//遍历非有序部分数组for(int i=1;i<array.length;i++){//取出非有序部分的第一个元素并向前逐个比对int tmp=array[i];int j=i-1;for(;j>=0;j--){if(tmp<array[j]){//若该元素比前面某元素小，则某元素后移，该元素继续向前比对array[j+1]=array[j];}else{//相反若该元素比前面某元素大，则退出循环break;}//内层循环结束说明已经为该元素找到合适位置，直接插入即可array[j+1]=tmp;}}}//实现希尔排序方法public static void shellSort(int[] array){//设定间隔增量gapint gap=array.length;while (gap > 1) {//每次循环缩小间隔增量gap/=2;//以间隔增量对数组进行分组插入排序shellSortChild(array,gap);}}//实现希尔排序的底层方法private static void shellSortChild(int[]array,int gap){//遍历非有序部分数组，i++表示对每组进行交替排序for(int i=gap;i<array.length;i++){//取出非有序部分的第一个元素并向前逐个比对int tmp=array[i];int j=i-gap;for(;j>=0;j-=gap){if(tmp<array[j]){//若该元素比前面某元素小，则某元素后移，该元素继续向前比对array[j+gap]=array[j];}else{//相反若该元素比前面某元素大，则退出循环break;}//内层循环结束说明已经为该元素找到合适位置，直接插入即可array[j+gap]=tmp;}}}//实现直接选择排序public static void selectSort(int[]array){//遍历非有序部分数组for(int i=0;i< array.length;i++){//默认最小值下标为起始下标int minIndex=i;//遍历剩余部分寻找最小值下标for(int j=i+1;j< array.length;j++){if(array[j]<array[i]){minIndex=j;}}//循环结束证明已经找到最小值下标，与非有序部分起始位置交换int tmp=array[minIndex];array[minIndex]=array[i];array[i]=tmp;}}//实现堆排序//创建一个大根堆的方法public static void createMaxHeap(int[] array){//从最后一棵子树倒序调整for(int parent=((array.length-1-1)/2);parent>=0;parent--){//调用向下调整的底层方法maxSiftDown(array,parent,array.length-1);}}//创建大根堆时调用到的向下调整的底层方法private static void maxSiftDown(int[]array,int parent,int end){//默认子女中的最大值为左子女int child=2*parent+1;while(child<end){//判断右子女是否为二者中最大值if(child+1<end){if(array[child]<array[child+1]){child++;}}if(array[parent]<array[child]){//子女节点中最大值大于双亲则进行交换调整int temp=array[parent];array[parent]=array[child];array[child]=temp;//向下迭代parent=child;child=2*parent+1;}else{//子女节点中最大值小于双亲说明该树已经为大根堆，无需向下调整，直接中断即可break;}}}//利用创建的大根堆实现堆排序public static void heapSort(int[]array){createMaxHeap(array);int end= array.length-1;while(end>0){//将堆顶元素和堆尾元素交换int temp=array[end];array[end]=array[0];array[0]=temp;//利用大根堆向下调整的方法maxSiftDown(array,0,end);end--;}}
}

（2）Test类：

import java.util.Arrays;
import java.util.Random;public class Test {//生成一个顺序数组的方法public static void order(int[] array){for(int i=0;i< array.length;i++){array[i]=i;}}//生成一个逆序数组的方法public static void reverseOrder(int[] array){for(int i=0;i<array.length;i++){array[i]= array.length-i;}}//生成一个随机数数组的方法public static void randomOrder(int[] array){Random random=new Random();for(int i=0;i<array.length;i++){array[i]= random.nextInt(10_0000);}}//测试直接插入排序时间的方法public static void testInsertSort(int[]array){//拷贝一个新的数组array= Arrays.copyOf(array,array.length);//获取起始时间戳long starttime=System.currentTimeMillis();Sort.insertSort(array);//获取终止时间戳long endtime=System.currentTimeMillis();//输出耗时System.out.println("直接插入排序耗时:"+(endtime-starttime));}//测试希尔排序时间的方法public static void testShellSort(int[]array){//拷贝一个新的数组array= Arrays.copyOf(array,array.length);//获取起始时间戳long starttime=System.currentTimeMillis();Sort.shellSort(array);//获取终止时间戳long endtime=System.currentTimeMillis();//输出耗时System.out.println("希尔排序耗时:"+(endtime-starttime));}//测试直接选择排序时间的方法public static void testSelectSort(int[]array){//拷贝一个新的数组array= Arrays.copyOf(array,array.length);//获取起始时间戳long starttime=System.currentTimeMillis();Sort.selectSort(array);//获取终止时间戳long endtime=System.currentTimeMillis();//输出耗时System.out.println("直接选择排序耗时:"+(endtime-starttime));}//测试直接选择排序时间的方法public static void testHeapSort(int[]array){//拷贝一个新的数组array= Arrays.copyOf(array,array.length);//获取起始时间戳long starttime=System.currentTimeMillis();Sort.heapSort(array);//获取终止时间戳long endtime=System.currentTimeMillis();//输出耗时System.out.println("堆排序耗时:"+(endtime-starttime));}public static void main(String[] args) {int[]array=new int[10_0000];//测试顺序数组情况System.out.println("***********************");System.out.println("顺序数组情况：");order(array);testInsertSort(array);testShellSort(array);testSelectSort(array);testHeapSort(array);System.out.println("***********************");//测试逆序数组情况System.out.println("逆序数组情况：");reverseOrder(array);testInsertSort(array);testShellSort(array);testSelectSort(array);testHeapSort(array);System.out.println("***********************");//测试随机数组情况System.out.println("随机数组情况：");randomOrder(array);testInsertSort(array);testShellSort(array);testSelectSort(array);testHeapSort(array);System.out.println("***********************");}
}