C語言深入淺出講解直接插入排序算法的實現(xiàn)
更新時間：2022年05月18日 10:53:02 作者：安然無虞
插入排序也是最簡單的一類排序方法，我今天介紹的也是插入排序里最直觀且淺顯易懂的直接插入排序。對這個很簡單的排序，記得當時也是花了近兩個晚上才搞懂它的原理的，接下來就來介紹一下
插入排序分為兩種：直接插入排序&希爾排序
直接插入排序
1.基本思想
直接插入排序是一種簡單的插入排序算法，其基本思想是：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
說得通俗一點就是：
假設區(qū)間[0, end]有序，將end+1位置的值插入到[0, end]中，保持區(qū)間[0, end+1]依舊有序。
生活中我們玩撲克牌時，就用了插入排序的思想。
在這里，我們以排升序為例。
核心思想：摸牌的過程
動圖演示：
2.算法實現(xiàn)
寫排序時，先從單趟開始考慮
//[0, end]已經(jīng)有序，將end+1位置的值插入到[0,end]中，使得[0,end+1]依舊保持有序
//有一個有序區(qū)間，插入一個數(shù)據(jù)，依舊保持有序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
//控制摸牌的過程，一開始從僅一張開始
//注意循環(huán)結束條件，只需要到n-2的位置，若將其改成i<n，則會出現(xiàn)越界的情況
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)//保證牌是有序的
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//往后挪，注意畫圖感受哦
end--;
}
else
//有兩種可能：（現(xiàn)想常規(guī)的，再考慮特殊情況）
//一是找到了比它小的數(shù)，放到其后；
//二是沒有比它小的數(shù)，直到end為-1才結束
{
break;
}
}
a[end + 1] = tmp;
}
}
完整代碼：
3.時間復雜度
直接插入排序時間復雜度是O(N^2)，注意哦，不是因為雙重循環(huán)，需要實際計算來得出時間復雜度。
最壞情況：逆序有序，1+2+3+……+n - 1；O(N^2)
最好情況：順序有序，1+1+1+……+1。O(N)
到此這篇關于C語言深入淺出講解直接插入排序算法的實現(xiàn)的文章就介紹到這了,更多相關C語言直接插入排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++編輯距離（動態(tài)規(guī)劃），編輯距離是指兩個字符串之間，由一個轉成另一個所需的最少編輯操作次數(shù)，限免詳細內容，需要的小伙伴可以參考一下2022-01-01
這篇文章主要介紹了C++ 標準模板庫 STL 順序容器詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
這篇文章主要介紹了VS2019配置BOOST的方法(v1.70.0庫)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
缺省參數(shù)函數(shù)重載以及引用的出現(xiàn)是為了補充C語言語法的不足以及對C語言設計不合理的地方進行優(yōu)化,引用的出現(xiàn)大大降低了我們學習C語言時相對于指針的難度,也便于我們更好的理解和使用,感興趣的朋友一起看看吧2024-04-04
結構體指針是一種非常有用的數(shù)據(jù)類型，它可以讓我們更方便地操作結構體，本文主要介紹了C語言結構體指針的具體使用，非常具有實用價值，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了 C語言中枚舉與指針的實例詳解的相關資料,希望通過本文大家能夠掌握枚舉與指針的知識，需要的朋友可以參考下2017-09-09
qsort是一個庫函數(shù),基于快速排序算法實現(xiàn)的一個排序的函數(shù),下面這篇文章主要給大家介紹了關于C語言qsort()函數(shù)使用的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-09-09
c語言中字符串函數(shù)(庫函數(shù)使用)和模擬實現(xiàn)圖文教程
C語言中對字符和字符串的處理很是頻繁,但是C語言本身并沒有字符串類型,這篇文章主要給大家介紹了關于c語言中字符串函數(shù)(庫函數(shù)使用)和模擬實現(xiàn)的相關資料,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細介紹了C++實現(xiàn)浮點數(shù)精確加法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05![C 語言基礎教程(我的C之旅開始了)[八]](http://img.jbzj.com/images/xgimg/bcimg9.png)
C 語言基礎教程(我的C之旅開始了)[八]...2007-02-02