百度百科:有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外（讓數(shù)組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成后，再將這個最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步將一個待排序的紀錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上，直到全部插入完為止。在網(wǎng)上找了一個動畫,如下圖所示:

下面上代碼:(這是一個簡單插入排序)

// 簡單插入排序public static void insertSort(int[] a) {int j, temp;for (int i = 1; i < a.length; i++) {temp = a[i];if (a[i] < a[i - 1]) {// 這里可以進行一次判斷 只有當a[i]<a[i-1]時才進入循環(huán)進行交換// 因為前面已經(jīng)有序了,只需要比較最大值,最大值不滿足無需交換for (j = i - 1; j >= 0 && a[j] > temp; j--) {a[j + 1] = a[j];}a[j + 1] = temp;}}}
由于待排序列是有序的,所以我們可以聯(lián)想到折半查找,為了找到a[i]的插入位置,我們使用折半查找的方法可以加快效率:

public static void binaryInsertSort(int[] a) {int j, temp, k;for (int i = 1; i < a.length; i++) {temp = a[i];if (a[i - 1] >= temp) {j = binarySearch(a, 0, i - 1, temp);for (k = i; k > j; k--)a[k] = a[k - 1];a[j] = temp;}}}// 折半插入排序public static int binarySearch(int[] a, int low, int high, int temp) {int mid;if (temp < a[low])return low;while (low <= high) {mid = (low + high) / 2;if (a[mid] <= temp && temp < a[mid + 1]) {return mid + 1;} else if (a[mid] > temp) {high = mid - 1;} else {low = mid + 1;}}return -1;}
這里特別需要注意的一個問題是我們在根據(jù)一個關(guān)鍵值在排好序的數(shù)組中查找位置時,數(shù)組有可能不存在這個數(shù),所以可以返回-1;但是我們在查找插入位置時,總是可以找到一個可以插入的位置.所以當temp比前面所有已經(jīng)排好序的數(shù)都小時,我們找到的插入位置應(yīng)該是low,這種特殊的情況一定要考慮到.

插入排序的進化版就是希爾排序.原理是:把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。通常情況下宏觀上調(diào)整的排序算法要比微觀調(diào)整的排序算法效率高.下面上代碼:

public static void shell(int[] a, int d) {int temp, j;for (int i = d; i < a.length; i += d) {temp = a[i];if (a[i - d] > temp) {for (j = i - d; j >= 0 && a[j] > temp; j -= d) {a[j + d] = a[j];}a[j + d] = temp;}}}public static void shellSort(int[] a) {for (int d = 5; d >= 1; d -= 2) {shell(a, d);}}

轉(zhuǎn)載于:https://www.cnblogs.com/cgsilent/p/4261276.html

總結(jié)

以上是生活随笔為你收集整理的算法研究:插入类排序(简单插入,折半插入,希尔排序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。