影響排序效率的一般從3個面向比較：資料比較的次數，資料移動的次數，記憶體空間佔用的大小。
我們就冒泡排序、選擇排序、插入排序、快速排序做一個總的比較。一般情況下不會使用冒泡排序演算法，因為它的比較次數和移動次數在幾種排序演算法中都是最多的，它的唯一好處是演算法簡單，易於理解，所以在資料量很小的時候它會有些應用價值。選擇排序在比較次數上和冒泡排序一樣，都是n的平方，但它把交換的次數降低到了最低，所以在數據量很小且交換數據相對於比較數據更加耗時的情況下，可以應用選擇排序。
在大多數情況下，當資料量比較小或基本上有序時，插入排序演算法是最好的選擇。對於更大的資料量排序來說，快速排序通常是最好的方法。
上述排序演算法在記憶體空間上佔用很少，只需要一個額外的變數來暫時儲存交換時的資料項。所以在記憶體空間佔用的大小上沒有可比性。
插入排序的比較次數仍然是n的平方，但在一般情況下，它要比冒泡排序快一倍，比選擇排序還要快一點。它常常被用在複雜排序演算法的最後階段，例如快速排序。
演算法：經過i-1遍處理後，L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，
使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。
先比較L[i]和L[i-1]，如果L[i-1]否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，
使得L[j] ≤L[j+1]時為止
優點:移動元素次數少，只需要一個輔助空間
時間複雜度n*n
當待排序記錄的數量n很小時，這是一種很好的排序方法。但是n很大時，則不適
例如：int[] values = { 5, 2, 4, 1, 3 };
排序過程：
第1次：2,5,4,1,3
第2次：2,4,5,1,3
第3次：1,2,4,5,3
第4次：1,2,3,4,5
java程式碼：
public class InsertSort {
public static void main(String[] args) {
int[] values = { 5, 2, 4, 1, 3 };
sort(values);
for (int i = 0; i < values.length; ++i) {
System.out.println(values[i]);
}
}
public static void sort(int[] values) {
int temp;
int j = 0;
for (int i = 1; i < values.length; i++) {
if(values[i]<values[i-1])//此处的判断很重要，这里体现了插入排序比冒泡排序和选择排序快的原因。
{
temp = values[i];
//数据往后移动
for (j=i-1; j>=0 && temp<values[j]; j--)
{
values[j+1] =values[j];
}
//将数据插入到j+1位置
values[j+1] =temp;
System.out.print("第" + (i + 1) + "次：");
for (int k = 0; k < values.length; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}第二個範例
package cn.cqu.coce.xutao;
public class zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
if(a[i]>a[j])
break;
if(j!=i-1){
int temp;
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=temp;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
}
}
更多java直接插入排序範例相關文章請關注PHP中文網！
