有一個已經有序的數據序列,要求在這個已經排好的數據序列中插入一個數,但要求插入後此數據序列仍然有序,這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,算法適用於少量數據的排序,時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分:第一部分包含了這個數組的所有元素,但將最後一個元素除外(讓數組多一個空間才有插入的位置),而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後,再將這個最後元素插入到已排好序的第一部分中。
插入排序的基本思想是:每步將一個待排序的記錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。
/**
* @param a
*/
public static void insertSort(int[] a) {
int length = a.length;
for (int i = 1; i < length; i++) {
int temp = a[i];
int j = i;
for (; j > 0 && a[j - 1] > temp; j--) {
a[j] = a[j - 1];
}
a[j] = temp;
}
}
閱讀更多 JAVA熊 的文章