本文共 1405 字，大约阅读时间需要 4 分钟。

直接插入排序：

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。

package com.algorithm.sort;/** * 直接插入排序 */public class InsertSort {    public static void main(String[] args) {        int[] a=new int[]{3,5,1,2,6};        insertSort(a);    }    public static void insertSort(int[] array){        for(int i=1;i
   
    =0;j--){                if(temp
   

二分法插入排序：

在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们 中间的那个元素比，如果小，则对前半再进行折半，否则对后半 进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间 的所有元素后移，再把第i个元素放在目标位置上。

package com.algorithm.sort;/** * 二分法插入排序 */public class BinaryInsertSort {    public static void main(String[] args) {        int[] a=new int[]{3,5,1,2,6,8,10,22};        for(int i=0;i
   
    =left;j--){                a[j+1]=a[j];            }            if (left!=i){                a[left]=temp;            }        }        for(int i=0;i
   

希尔排序：

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。我们下面选择的增量序列{n/2,(n/2)/2...1}(希尔增量)，其最坏时间复杂度依然为O(n2)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)。

package com.algorithm.sort;/** * 希尔排序 */public class ShellSort {    public static void main(String[] args) {        int[] a={8,9,1,7,2,3,5,4,6,0};        for(int grap=a.length/2;grap>=1;grap/=2){            for(int i=grap;i
   
    =0;j-=grap){//注意这里需要一个循环，否则只能保证相邻项大小关系，不能保证整组的排序                if(a[j]
   

原文链接：

转载地址：http://drpqb.baihongyu.com/