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ù)級空間O(1)
穩(wěn)定性：穩(wěn)定
到此這篇關(guān)于C++排序算法之插入排序解析的文章就介紹到這了,更多相關(guān)C++插入排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了switch語句，switch語句是我們常見會用到的結(jié)構(gòu)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
C語言實(shí)現(xiàn)數(shù)組的循環(huán)移位的方法示例
這篇文章主要介紹了C語言實(shí)現(xiàn)數(shù)組的循環(huán)移位的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
這篇文章主要為大家詳細(xì)介紹了2048小游戲C語言實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要為大家詳細(xì)介紹了MFC實(shí)現(xiàn)連連看游戲之消子算法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家介紹了c++算法進(jìn)階刪除有序鏈表中的重復(fù)元素示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
C語言實(shí)現(xiàn)關(guān)機(jī)小程序
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)關(guān)機(jī)小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
最近寫MFC的程序，想在對話框里實(shí)現(xiàn)窗口的任意分割?，F(xiàn)在網(wǎng)絡(luò)資料一大抄，找個(gè)東西實(shí)在麻煩。總算這個(gè)很簡單，很快就搞定了，寫下來做個(gè)筆記。2015-06-06
C語言 module_init函數(shù)與initcall案例詳解
這篇文章主要介紹了C語言 module_init函數(shù)與initcall案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
為了讓程序盡快響應(yīng)用戶操作，在開發(fā)應(yīng)用程序時(shí)經(jīng)常會使用到線程。這篇文章就來和大家介紹一下Qt中線程的實(shí)際應(yīng)用，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)萬年歷效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11