本文實例講述了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)。

希望本文所述對大家java程序設計有所幫助。

總結

以上是生活随笔為你收集整理的java数据结构排序实验报告_java数据结构与算法之插入排序详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。