C++排序算法之插入排序解析
更新時間：2023年10月31日 09:34:00 作者：大慶指針
這篇文章主要介紹了C++排序算法之插入排序解析,將數(shù)組分為有序表和無序表,每次從有序表中取出一個元素,插入到有序表的適當位置,每遍歷一次,有序表中元素增加一個,無序表中元素個數(shù)減少一個,重復(fù)n-1次,完成排序,需要的朋友可以參考下
C++插入排序
思想
將數(shù)組分為有序表和無序表，每次從有序表中取出一個元素，插入到有序表的適當位置，剛開始有序表中只有一個數(shù)，無序表中有n-1個數(shù)。
每遍歷一次，有序表中元素增加一個，無序表中元素個數(shù)減少一個，重復(fù)n-1次，完成排序。
代碼
#include<iostream>
#include<vector>
using namespace std;
void insertSort(vector<int>&vec, int n)
{
//j表示無序表第一個元素下標
for (int j = 1; j <n; j++)
{
//i表示有序表最后一個元素下標
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)文章
這篇文章主要為大家介紹了switch語句，switch語句是我們常見會用到的結(jié)構(gòu)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
C語言實現(xiàn)數(shù)組的循環(huán)移位的方法示例
這篇文章主要介紹了C語言實現(xiàn)數(shù)組的循環(huán)移位的方法示例，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
這篇文章主要為大家詳細介紹了2048小游戲C語言實現(xiàn)代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要為大家詳細介紹了MFC實現(xiàn)連連看游戲之消子算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家介紹了c++算法進階刪除有序鏈表中的重復(fù)元素示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)關(guān)機小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
最近寫MFC的程序，想在對話框里實現(xiàn)窗口的任意分割?，F(xiàn)在網(wǎng)絡(luò)資料一大抄，找個東西實在麻煩。總算這個很簡單，很快就搞定了，寫下來做個筆記。2015-06-06
C語言 module_init函數(shù)與initcall案例詳解
這篇文章主要介紹了C語言 module_init函數(shù)與initcall案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
為了讓程序盡快響應(yīng)用戶操作，在開發(fā)應(yīng)用程序時經(jīng)常會使用到線程。這篇文章就來和大家介紹一下Qt中線程的實際應(yīng)用，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)萬年歷效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11