插入排序及希爾排序

插入排序

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)