选择排序、插入排序、希尔排序总结

本来昨天想写最小生成树的kruskal算法，但是其中需要将图的边集数组进行排序，要用到排序算法，所以暂时先将kruskal算法放一下，把排序算法好好复习和总结一遍

以下的排序结果默认为非递减

1、选择排序

选择排序的思想：从第i个元素开始（i=1,i++），遍历一遍数组，找出数组中的最小值，然后与第i个元素交换位置，i++,不断的循环下去直到i>数组长度（长度为length-1,第0个元素习惯用作哨兵位）

看看具体算法

public void selectSort(int arc[]){ int min; for(int j=1;j<arc.length;j++){ min = j; for(int i=j+1;i<arc.length;i++){ if(arc[i]<arc[min]) min = i; } each(arc,j,min); //交换arc[j]和arc[min]的位置 System.out.println(arc[j]); } }

选择排序的几个特点：

1.时间复杂度为O（n^2）；

2.运行的时间与输入参数的初始状态无关，因为每一次的遍历都不会为下一次提供任何有用的信息；

3.数据的移动是最少的。

2、插入排序

插入排序的思想：将第i个元素与i-1的元素比较，如果第i个元素较小，则把其插入到arc[0]的哨兵位，然后比哨兵位大的元素不断的往后移动一位，最后将哨兵位的元素插入到最后移动的那个位置。注：i一般从2开始，因为假设第1位已经排好序了。

看看具体算法

public void insertSort(int arc[]){ int i; for(int j=2;j<arc.length;j++){ if(arc[j]<arc[j-1]){ arc[0] = arc[j]; //插入哨兵位 for(i=j-1;arc[i]>arc[0];i--){ arc[i+1] = arc[i]; //元素不断向后移动一位 } arc[i+1] = arc[0]; //将哨兵位的元素插入到最后一次移动的位置 } } output(arc); //输出排好序的数组元素 } output(int arc[])具体代码

private void output(int[] arc) { for(int i=1;i<arc.length;i++){ System.out.println(arc[i]); } } 插入排序的几个特点：

1.时间复杂度为O（n^2），但插入排序平均速度要比选择排序快；

2.运行时间与输入的参数初始化状态有关，比如对于部分有序的数组十分高效；

3、希尔排序

希尔排序思想：希尔排序是简单的改进了插入排序，交换不相邻的元素以进行局部的排序，并最终用插入排序对局部的数组排序。

看看具体代码

public void shellSort(int arc[]){ int i; int increment = arc.length/3+1; //增量序列 while(increment>0){ for(int j=1+increment;j<arc.length;j++){ if(arc[j]<arc[j-increment]){ arc[0] = arc[j]; for(i=j-increment;i>0&&arc[i]>arc[0];i-=increment){//i>0是表示当要插到第1位时的条件，且i>0一定要在逻辑运算中的前面 arc[i+increment] = arc[i]; //否则会ArrayIndexOutOfBoundsException } arc[i+increment] = arc[0]; } } increment/=3; } output(arc); //输出排好序的数组元素 }

希尔排序的几个特点：

1.时间复杂度为O（n^3/2）

2.对于较大的数组，希尔排序的速度相较于插入排序的优势更加明显

总结

虽然选择排序和插入排序的时间复杂度一样，但是选择排序的运行时间和参数的初始状态无关，只要数组参数的长度一样，不管数组里面的元素初始排序是怎样的，运行时间都不会有改变（默认理想环境，忽略硬件环境造成的误差）。而插入排序的运行时间和参数初始状态有关，特别是对于部分有序数组，十分高效，因此插入排序比选择排序的平均运行时间要快一些。

希尔排序是对插入排序的改进，对距离increment的元素进行比较和交换，元素的跳跃跨度较大，使得希尔排序在较大的数组中的运行时间要比插入排序短。