C++排序算法之插入排序解析
更新時間：2023年10月31日 09:34:00 作者：大慶指針
這篇文章主要介紹了C++排序算法之插入排序解析,將數(shù)組分為有序表和無序表,每次從有序表中取出一個元素,插入到有序表的適當(dāng)位置,每遍歷一次,有序表中元素增加一個,無序表中元素個數(shù)減少一個,重復(fù)n-1次,完成排序,需要的朋友可以參考下
C++插入排序
思想
將數(shù)組分為有序表和無序表，每次從有序表中取出一個元素，插入到有序表的適當(dāng)位置，剛開始有序表中只有一個數(shù)，無序表中有n-1個數(shù)。
每遍歷一次，有序表中元素增加一個，無序表中元素個數(shù)減少一個，重復(fù)n-1次，完成排序。
代碼
#include<iostream>
#include<vector>
using namespace std;
void insertSort(vector<int>&vec, int n)
{
//j表示無序表第一個元素下標(biāo)
for (int j = 1; j <n; j++)
{
//i表示有序表最后一個元素下標(biāo)
for (int i = j - 1; i >= 0; i--)
{
if (vec[i] > vec[i + 1])
{
swap(vec[i], vec[i + 1]);
}
}
}
}
int main()
{
vector<int>vec = { 2,3,5,8,9,7,4,6,1 };
insertSort(vec, vec.size());
for (auto it : vec)
{
cout << it << " ";
}
return 0;
}解析
時間復(fù)雜度：
最好時間復(fù)雜度(全部有序)：O(n)
比較n-1趟，每一趟比較一次，不移動元素，最好時間復(fù)雜度為O(n)
最壞時間復(fù)雜度(全部逆序)：O(n2)
第一次排序時有序表1個元素，無序表n-1個元素，比較1次，移動1次
第二次排序時有序表2個元素，無序表n-2個元素，比較2次，移動2次
...
第n-1次排序時有序表n-1個元素，無序表1個元素，比較n-1次，移動n-1次
故最壞時間復(fù)雜度為O((1+2+3+...+n-1)*2)=O(n*(n-1))=O(n2)
空間復(fù)雜度：
在原數(shù)組上操作，即使用了常數(shù)級空間O(1)
穩(wěn)定性：穩(wěn)定
到此這篇關(guān)于C++排序算法之插入排序解析的文章就介紹到這了,更多相關(guān)C++插入排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Vs2019+Qt+Opencv環(huán)境配置心得(圖文)
這篇文章主要介紹了Vs2019+Qt+Opencv環(huán)境配置心得(圖文)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
這篇文章主要為大家介紹了Qt5實現(xiàn)qDebug日志信息寫入日志文件的過程示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
這篇文章主要為大家詳細(xì)介紹了Linux系統(tǒng)上C++如何使用alsa庫播放聲音文件,文中示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-04-04
C語言實現(xiàn)字符轉(zhuǎn)unix時間戳的簡單實例
下面小編就為大家?guī)硪黄狢語言實現(xiàn)字符轉(zhuǎn)unix時間戳的簡單實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
C++ std::Set＜std::pair＞的實現(xiàn)示例
本文主要介紹了C++ std::Set＜std::pair＞的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-10-10
本文主要介紹了C++之內(nèi)存分區(qū)的實現(xiàn)示例,主要包含了4個區(qū)域,分為代碼區(qū),全局區(qū),棧區(qū)和堆區(qū),文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-03-03
本篇文章是對C語言中string函數(shù)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
c++實現(xiàn)跳躍表（Skip List）的方法示例
跳表（skiplist）是一個非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)簡單，插入、刪除、查找的復(fù)雜度均為O(logN)，下面這篇文章主要介紹了c++實現(xiàn)跳躍表（Skip List）的相關(guān)資料，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09
下面小編就為大家?guī)硪黄狾LEDB打開Excel文件的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要為大家介紹了C/C++開發(fā)中extern一些使用注意事項的事例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01