通俗易懂講解 直接插入排序

直接插入排序介紹

直接插入排序(Straight Insertion Sort)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表。開始時有序表中只包含1個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重複n-1次可完成排序過程。

插入排序圖文說明

下面選取直接插入排序的一個中間過程對其進行說明。假設{20,30,40,10,60,50}中的前3個數已經排列過，是有序的了；接下來對10進行排列。示意圖如下：

圖中將數列分為有序區和無序區。我們需要做的工作只有兩個：(1)取出無序區中的第1個數，並找出它在有序區對應的位置。(2)將無序區的數據插入到有序區；若有必要的話，則對有序區中的相關數據進行移位。看，是不是很簡單。

直接插入排序實現

根據上面的分析，不難實現直接插入排序的實現。

/* * 直接插入排序 * * 參數說明： n* a -- 待排序的數組 n* n -- 數組的長度 n*/nnvoid insert_sort(int a[], int n)n{n int i, j, k;nn for (i = 1; i < n; i++)n {n //為a[i]在前面的a[0..i-1]有序區間中找一個合適的位置n for (j = i - 1; j >= 0; j--)n if (a[j] < a[i])n break;nn //如找到了一個合適的位置n if (j != i - 1)n {n //將比a[i]大的數據向後移n int temp = a[i];n for (k = i - 1; k > j; k--)n a[k + 1] = a[k];n //將a[i]放到正確位置上n a[k + 1] = temp;n }n }n}n

時間複雜度和穩定性

直接插入排序的時間複雜度是 ：假設被排序的數列中有N個數，遍歷一趟時間複雜度是O(N)，需遍歷多少次呢？N-1次，因此，其時間複雜度是 。

直接插入排序是穩定的演算法，它滿足穩定演算法的定義：假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；並且排序之後，a[i]仍然在a[j]前面。則這個排序演算法是穩定的！

更多文章見本文公眾號：碼農有道

版權所有！

推薦閱讀：