java實作插入排序的實例詳解

這篇文章主要介紹了java資料結構與演算法之插入排序,結合實例形式分析了java插入排序的概念、分類、原理、實現方法與相關注意事項,需要的朋友可以參考下

本文實例敘述了java資料結構與演算法之插入排序。分享給大家供大家參考，具體如下：

複習之餘，就將資料結構中關於排序的這塊知識點整理了一下，寫下來是想與更多的人分享，最關鍵的是做一備份，為方便以後查閱。

排序

1、概念：

有n個記錄的序列{R1, R2,.......,Rn}（此處注意：1,2,n 是下表序列，以下是相同的作用），其對應關鍵字的序列為{K1,K2,.... .....,Kn}。透過排序，要求找出目前下標序列1,2,......,n的一種排列p1,p2,........pn，使得對應關鍵字滿足如下的非遞減（非遞增）關係，即：Kp1<=Kp2<=Kpn，這樣就得到一個按關鍵字有序的記錄序列：{Rp1,Rp2,.......,Rpn}。

2、分類

根據排序時資料所佔用記憶體的不同，可將排序分為兩類。

內部排序：整個排序過程完全在記憶體中進行，如下：

插入類別排序（直接插入排序、折半插入排序、希爾排序);

交換類別排序（冒泡排序、快速排序）；

選擇類別排序（簡單選擇排序、樹型選擇排序、堆排序）；

歸併排序；

分配類別排序（多關鍵字排序、鍊式基數排序、基數排序的順序表實現））；

#外部排序：由於待排序記錄資料量太大，記憶體無法容納全部數據，排序需要藉助外部儲存設備才能完成（磁碟排序，磁帶排序）。

3、穩定性

假設在待排序的序列中存在多個具有相同關鍵字的記錄。設Ki=Kj(1<=i<=n,1<=j<=n,i != j)，若在排序前的序列中Ri領先與Rj(即i<=j)，經過排序後得到的序列中Ri仍然領先與Rj，則稱所使用的排序方法是穩定的；反之，當相同關鍵字的領先關係在排序過程中發生變化，則所使用的排序方法是不穩定的。

插入排序：

想法：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子檔案中的適當位置，直到全部記錄插入完成為止。

直接插入排序：

演算法想法：假設待排序的記錄存放在陣列R[1.. n]中。初始時，R[1]自成1個有序區，無序區為R[2..n]。從i=2起直至i=n為止，依序將R[i]插入目前的有序區R[1..i-1]中，產生含n個記錄的有序區。

用java實作的程式碼如下：

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

演算法分析：最好的情況是待排序記錄本身已經依照關鍵字有序排列，最壞的情況是待排序記錄是按照關鍵字逆序排列的；時間複雜度是O(N^2)，空間複雜度是O(1)； 此演算法是穩定的排序演算法：比較適用於待排序記錄數目較少且基本上有序的情況。

折半插入排序：

#演算法想法：對於有序表進行折半查找，其效能優於順序查找。

演算法實作程式碼如下：

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

演算法分析：是一種穩定的排序演算法，比直接插入演算法明顯減少了關鍵字之間比較的次數，因此速度比直接插入排序演算法快，但記錄移動的次數沒有變，所以折半插入排序演算法的時間複雜度仍然為O (n^2)，與直接插入排序演算法相同。 附加空間O(1)。

【相關推薦】

#1. 特別推薦：「php程式設計師工具箱”V0.1版本下載

#

2. Java免費影片教學

#3. YMP線上手冊

##########

以上是java實作插入排序的實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！