java直接插入排序示例

2019-11-26 15:30:12

字體：大中小

供稿：網(wǎng)友

影響排序效率的一般從3個(gè)方面比較：數(shù)據(jù)比較的次數(shù)，數(shù)據(jù)移動(dòng)的次數(shù)，內(nèi)存空間占用的大小。
我們就冒泡排序、選擇排序、插入排序、快速排序做一個(gè)總的比較。一般情況下不會(huì)使用冒泡排序算法，因?yàn)樗谋容^次數(shù)和移動(dòng)次數(shù)在幾種排序算法中都是最多的，它的唯一好處是算法簡(jiǎn)單，易于理解，所以在數(shù)據(jù)量很小的時(shí)候它會(huì)有些應(yīng)用價(jià)值。選擇排序在比較次數(shù)上和冒泡排序一樣，都是n的平方，但它把交換的次數(shù)降低到了最低，所以在數(shù)據(jù)量很小且交換數(shù)據(jù)相對(duì)于比較數(shù)據(jù)更加耗時(shí)的情況下，可以應(yīng)用選擇排序。
在大多數(shù)情況下，當(dāng)數(shù)據(jù)量比較小或基本上有序時(shí)，插入排序算法是最好的選擇。對(duì)于更大的數(shù)據(jù)量排序來(lái)說(shuō)，快速排序通常是最好的方法。
上述排序算法在內(nèi)存空間上占用很少，僅需要一個(gè)額外的變量來(lái)暫時(shí)存儲(chǔ)交換時(shí)的數(shù)據(jù)項(xiàng)。所以在內(nèi)存空間占用的大小上沒(méi)有可比性。

插入排序的比較次數(shù)仍然是n的平方，但在一般情況下，它要比冒泡排序快一倍，比選擇排序還要快一點(diǎn)。它常常被用在復(fù)雜排序算法的最后階段，比如快速排序。

算法：經(jīng)過(guò)i-1遍處理后，L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，
使得L[1..i]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。
首先比較L[i]和L[i-1]，如果L[i-1]<=L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了;
否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)，
使得L[j] ≤L[j+1]時(shí)為止
優(yōu)點(diǎn):移動(dòng)元素次數(shù)少，只需要一個(gè)輔助空間
時(shí)間復(fù)雜度n*n
當(dāng)待排序記錄的數(shù)量n很小時(shí)，這是一種很好的排序方法。但是n很大時(shí)，則不適

例如：int[] values = { 5, 2, 4, 1, 3 };

排序過(guò)程：
第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代碼：

復(fù)制代碼代碼如下:

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])//此處的判斷很重要，這里體現(xiàn)了插入排序比冒泡排序和選擇排序快的原因。
           {
               temp = values[i];
               //數(shù)據(jù)往后移動(dòng)
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //將數(shù)據(jù)插入到j(luò)+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("");
           }
       }
   }
}

第二個(gè)示例

復(fù)制代碼代碼如下:

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();
}
}