本文實例講述了Java插入排序方法。分享給大家供大家參考。具體分析如下：
有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到插入排序法。本文主要介紹的是插入排序的java實現。
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據。比較和交換的時間復雜度為O(n^2)，算法自適應，對于數據已基本有序的情況，時間復雜度為O(n)，算法穩定，開銷很低。算法適合于數據已基本有序或者數據量小的情況。
插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最后一個元素除外，而第二部分就只包含這一個元素。在第一部分排序后，再把這個最后元素插入到此刻已是有序的第一部分里的位置。
算法描述
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到下一位置中
6. 重復步驟2
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public void insertionSort() { // 插入排序 int out, in; int count1 = 0, count2 = 0;// 復制次數，比較次數 for (out = 1; out < nElems; out++) { long temp = a[out]; in = out; boolean flag=in>0&&a[in-1]>=temp; while(flag){ if(a[in-1]>=temp){ if(in>0){ a[in]=a[in-1]; count1++; --in; } } count2++; flag=in>0&&a[in-1]>=temp; } a[in] = temp; } System.out.println("復制次數為：" + count1 + " 比較次數為：" + count2); } |
插入排序法在數據已有一定順序的情況下，效率較好。但如果數據無規則，則需要移動大量的數據，其效率就與冒泡排序法和選擇排序法一樣差了。
希望本文所述對大家的java程序設計有所幫助。
