文章目錄
- 前言
- 一、插入排序的基礎知識點
- 1.插入排序的排序原理
- 2.插入排序的所屬類別
- 3.插入排序的演算法復雜度
- 二、插入排序動態圖
- 三、代碼
- 總結
前言
今天來和大家分享插入排序，
一、插入排序的基礎知識點
1.插入排序的排序原理
用未排序序列中的首個元素a，與已排序元素b從后向前逐個對比，若a>b則a插入b的后一位，若a<b，則a、b位置互換，
2.插入排序的所屬類別
插入排序屬于“比較類排序”
3.插入排序的演算法復雜度
最壞的情況為與所求序列相反的序列，所以需要依次操作 1、2、3…（n-1）次，由公式得，共為n(n-1)/2次，
所以時間復雜度為O(n2)，
二、插入排序動態圖
圖來自 https://visualgo.net/zh/sorting?slide=10-2，侵刪，
三、代碼
代碼如下：
void calculate()
{
int n, count, i, min, x, temp;
cin >> n; //定義n個數
int a[999]; //陣列里存放n個數
for(count = 1; count <= n; count++)
{
cin >> a[count]; //輸入已知序列 a[1]-a[n]
}
for(count = 2; count <= n; count++) //以此提取 a[2]到a[n]
{
x = a[count]; //先得到a[count]也就是提取出來的那個數
for(i = count-1; i >= 1 ; i--) //遍歷提取的數之前的每個數 到a[1]
{
if(x < a[i]) //若之前的數比提取出來的數大
{
a[i+1] = a[i]; //向后移動一位
a[i] = x;
}
}
}
for(count = 1; count <= n; count++)
cout << a[count] << " ";
}
總結
以上就是今天要和大家分享的內容，本文僅僅簡單介紹了插入排序的使用，筆者不才，若有錯誤，愿大家提出，筆者定及時糾正，愿與大家同學習，共進步！轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260331.html
標籤：其他
上一篇：c++ 實作矩陣運算器