前言:
✌ 作者簡介:遊坦之 ✌
🏆 大學軟體工程在讀,希望學到真本領,經世緻用 🏆
📫 如果文章知識點有錯誤的地方,請指正!和大家一起學習,一起進步👀
💬 人生格言:成好人,行好事,做儒猿💬
🔥 如果感覺部落客的文章還不錯的話,還請👍關注、點贊、收藏三連支援👍一下部落客哦
@TOC
🍉什麼是直接插入排序?
直接插入排序(Straight Insertion Sort)是一種最簡單的排序方法,其基本操作是将一條記錄插入到已排好的有序表中,進而得到一個新的、記錄數量增1的有序表。
🍊舉個例子
對{5,2,8,7,9,4,3}進行直接插入排序
第一步,容器是空的,取出第一個元素5,放在容器的第一位。
第二步,取出第二位元素2,與有序容器裡的元素依次排序,此時有序容器裡隻有一個元素5,2與5進行比較,2比5小,2放在5前面。
第三步,取出元素8,依次與有序容器裡的元素進行比較。與2進行比較,大于2,繼續往後進行比較,8還是大于5,是以放在5的後面。
第四步,取出元素7,依次與有序容器裡的元素進行比較。和2進行比較,7>2,繼續往後取出元素5進行比較,7>5,繼續取出元素8進行比較。7<8,是以7放在元素8的前面。
第五步,取出元素9,依次與有序容器裡的元素進行比較。和2進行比較,9>2,繼續往後取出元素5進行比較,9>5,繼續元素7進行比較,9>7,繼續往後取出元素8,進行比較,9>8,是以9放在8的後面。
第六步,取出元素4,依次與有序容器裡的元素進行比較,和2進行比較,4>2,繼續往後取出元素5進行比較,4<5,是以4就放在5前面。
第七步,取出元素3,依次與有序容器裡的元素進行比較,和2進行比較,3>2,繼續取出元素4進行比較,此時3<4,是以把元素3放在元素4的前面。
🍌代碼
#include <iostream>
using namespace std;
const int M = 10010;
int a[M];
int s[M];
int n;
int s_num = 0;//記載
int main()
{
cout<<"請輸入有多少個資料"<<endl;
cin>>n;
cout<<"請輸入資料"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
bool flag = true;
for(int j=0;j<s_num;j++)
{
if(a[i]<=s[j])
{
for(int k = s_num-1;k>=j;k--)//後移的操作
{
s[k+1] = s[k];
}
s_num++;
flag = false;//代表置換了
s[j] = a[i];
break;
}
}
if(flag)//意味着這個數比s這個有序數組裡面所有的元素的都大
{
s[s_num++] = a[i];
}
}
for(int i=0;i<s_num;i++)
{
cout<<s[i]<<" ";
}
return 0;
}
🍋總結
由上面的栗子可以清晰的看出,直接插入排序需要兩個容器,一是承載所有的集合,而是承載逐漸擴充的有序集合。有序集合本是空集,随着每一步的擴充,集合的元素總數加1.也就是原集合有多少個元素,就需要進行多少步,即原有n個元素,就要進行n步排序。而每一步排序,最壞情況都需要周遊m次,這就意味着直接插入排序的時間複雜度即為O(n2)。但是從上面的代碼來看,如果用到的是普通的數組,對于數組後移這樣的操作,仍需要周遊z次,這就意味着時間複雜度變成了O(n3)。對此,我們可以用動态數組或者是連結清單進行優化。
就比賽而言,每個比賽的時間限制大體在1s,計算量在10的8次方,對于O(n2)的時間複雜度而言,直接插入排序适合的計算量大約在10000左右,超過10000的資料不太适合用直接插入排序。則需要更高效的算法,或者需要更友善的容器。
而對于容器而言,常見的有數組、連結清單、set、vector、map、queue、stack等等。