插入排序及希尔排序

插入排序

public class Insertion_sort {0	PRivate static Integer[] data;	public static void main(String[] args) {		Random ra =new Random();		data=new Integer[30];		for(int i=0;i<30;i++)			data[i]=ra.nextInt(100)+1;		display(data);		insertionSort(data);		display(data);	}	public static void display(Integer[] data2) {		for(int i=0;i<data2.length;i++)			System.out.print(data2[i]+" ");		System.out.println();	}	public static<T extends Comparable<? super T>> void insertionSort(T[] data) {		for (int index = 1;index<data.length; index++) {			T key=data[index];			int position = index;			// data[position - 1].compareTo(key) > 0表示升序。			//data[position - 1].compareTo(key) < 0表示降序			while (position > 0 && data[position - 1].compareTo(key) > 0) {				data[position] = data[position - 1];				position--;			}			data[position] = key;		}	}}测试结果12 31 32 20 11 31 21 68 80 93 32 31 61 60 65 70 96 19 86 84 6 71 92 29 92 27 96 14 85 15 6 11 12 14 15 19 20 21 27 29 31 31 31 32 32 60 61 65 68 70 71 80 84 85 86 92 92 93 96 96 插入排序算法性能插入排序在最好的情况下是O(n)，在最坏的情况下是O(n2)的。数组越接近有序，插入排序所需的工作就越少。
希尔排序
希尔排序(Shell Sort)是插入排序的一种，是针对直接插入排序算法的改进。插入排序的增量是1，而希尔是一个数组决定的。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
public class Shell_sort {		private static Integer[] data;	public static void main(String[] args) {		Random ra =new Random();		data=new Integer[30];		for(int i=0;i<30;i++)			data[i]=ra.nextInt(100)+1;		display(data);		shellSort(data,0,data.length-1);		display(data);	}	public static void display(Integer[] data2) {		for(int i=0;i<data2.length;i++)			System.out.print(data2[i]+" ");		System.out.println();	}		public static<T extends Comparable<? super T>> void shellSort(T[] a,int first,int last){		int n=last-first+1;		for(int space=n/2;space>0;space=space/2){//			System.out.println(space+" ");			for(int begin=first;begin<first+space;begin++){				incrementalInsertionSort(a,begin,last,space);			}//			System.out.println();		}	}		private static<T extends Comparable<? super T>> void incrementalInsertionSort(T[] a,int first,int last,int space){		int unsorted,index;		for(unsorted=first+space;unsorted<=last;unsorted=unsorted+space){			T firstUnsorted=a[unsorted];//			System.out.print(firstUnsorted+" ");			for(index=unsorted-space;(index>=first)&&(firstUnsorted.compareTo(a[index])<0);index=index-space)				a[index+space]=a[index];			a[index+space]=firstUnsorted;		}	}}
算法比较
 
最好情况
平均情况
最坏情况
选择排序
O(n2)
O(n2)
O(n2)
插入排序
O(n)
O(n2)
O(n2)
希尔排序
O(n)
O(n1.5)
O(n2)或O(n1.5)