一、插入排序（Insertion Sort）
1、原理：如同整理桥牌的方法，将每一张牌插入到其他已经有序的牌中的适当位置，直到全部记录插入完毕为止。
2、思路：（1）首先需要明确待排序的数列由两部分组成，已排好序的部分（有序表）和待排序的部分（无序表）；
（2）每次从无序表中取出一个元素；
（3）接着我们每次选择待排序的部分的第 1 个元素，分别与前面的元素进行比较。当大于前面的元素时，可以直接进入已排好序的部分；当小于前面的元素时，需要把这个元素拿出来，将前面的元素后移一位，继续与前面的元素相比，直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素，这时停止比较、移动，直接把这个元素放到当时的空位上；
（4）一直重复步骤 2，当待排序的部分已经没有元素可进行插入时，停止操作，当前的数列为已排好序的数列。
3、算法实现
/*** @author HPC*插入排序算法实现*/
public class Insertion {//对数组a进行排序public static void sort(int[]a) {//将a按升序排列//对于1~N-1：每次将a[j]与前一个元素比较和交换，一直比到a[0];for(int i=1;i<a.length;++i) {for(int j=i;j>0; --j) {//找到最小的元素,与数组第一个交换if(less(a[j],a[j-1])) exch(a,j,j-1);}}} //比较两个数private static boolean less(int v,int w) {if(v<w)return true;else return false; }//交换两个数private static void exch(int[]a,int i,int j) {int t=a[i];a[i]=a[j];a[j]=t;}//打印结果private static void show(int[] a) {// TODO Auto-generated method stub//在单行中打印数组for(int i=0;i<a.length;++i) {System.out.print(a[i]+" ");}System.out.println(); } /*** @param args*/public static void main(String[] args) {int []a =new int[] {2,5,1,4,9,6,8,7,0,3};sort(a);show(a);}
}4、算法分析
最佳情况：T(n) = O(n)；最差情况T(n) = O(n?)；平均情况T(n) = O(n?)
二、Shell排序（Shell Sort）
1、原理：Shell排序改进了插入排序，先把N个小部分元素排序好，让元素大概有个顺序，最后再全面使用插入排序。
2、思路：（1）使用一个增量序列h1,h2,...ht，只要h1=1，任何增量序列都是可行的；
（2）先将待排元素序列分成若干个子序列（每个子序列由相隔某个“增量”的元素组成），分别进行插入排序；
在使用增量hk的一趟排序后，对每个i，都有a[i]≤a[i+hk]，即所有相隔hk的元素都被排序，此时称文件是hk排序的；
一趟hk排序的作用，即对hk个独立子数组执行一次插入排序；
（3）依次缩减增量，再重复步骤 1）进行排序；
（4）直到hk为1时，再对全体元素进行一次直接插入排序（insertion sort）。
3、算法实现
/*** @author HPC*Shell排序*/
/** 基本思想：先把几个小部分元素排序好，让元素大概有个顺序，然后再全面使用插入排序。* 算法的性能不仅取决于h，还取决于h之间的数学性质，比如它们的公因子等。* 希尔排序比插入排序和选择排序要快很多，并且数组越大，优势越大* */
public class Shell {//对数组a进行排序/** 基于插入排序的改进，先取间隔h进行插入排序，完成后h=h/3，若h>0,则再重复上述排序* */public static void sort(int[]a) {//使用了序列1/2(3^k -1)，从N/3开始递减至1int N=a.length;
// int h=1;
// while(h<N/3) h=3*h+1;int h=N/2;while(h>=1) {for(int i=h;i<N;++i) {//将a[i]插入到a[i-h]，a[i-2*h],a[i-3*h]...之中for(int j=i;j>=h;j-=h) {if(less(a[j],a[j-h])) exch(a,j,j-h);}}
// h=h/3;h=h/2;}} //比较两个数private static boolean less(int v,int w) {if(v<w)return true;else return false;}//交换两个数private static void exch(int[]a,int i,int j) {int t=a[i];a[i]=a[j];a[j]=t;}//打印结果private static void show(int[] a) {//在单行中打印数组for(int i=0;i<a.length;++i) {System.out.print(a[i]+" ");}System.out.println(); } /*** @param args*/public static void main(String[] args) {int []a =new int[] {2,5,1,4,9,6,8,7,0,3};sort(a);show(a);}}
4、算法分析
最佳情况：T(n) = O(nlog2 n)；最差情况T(n) =O(nlog2 n)；平均情况T(n) =O(nlog n)