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