C++排序算法之選擇排序解析
C++選擇排序
思想
遍歷數(shù)組，選擇找到最大值，記錄最大值下標(biāo)maxindax，然后將最大值與最后一個(gè)值交換，即swap（vec[maxindax],vec[n-1]);
在剩下的待排序數(shù)組中，重新找到最大值，重復(fù)第一步，swap(vec[maxidnax],vec[n-2]),循環(huán)操作，直至數(shù)組排序完成。
代碼
#include<iostream>
#include<vector>
using namespace std;
void selectSort(vector<int>&vec,int n)
{
//j代表是待排序數(shù)組的個(gè)數(shù),下標(biāo)對(duì)應(yīng)就是0到j(luò)-1
for (int j = n; j >= 1; j--)
{
int max = vec[0];
int maxindax = 0;
for (int i = 0; i < j; i++)
{
if (vec[i] > max)
{
//找到最大數(shù)，并且記錄下標(biāo)maxIndax
max = vec[i];
maxindax = i;
}
}
//交換最大值與待排序數(shù)組的最后一個(gè)
swap(vec[maxindax], vec[j - 1]);
}
}
int main()
{
vector<int>vec = { 2,3,5,8,9,7,4,6,1 };
selectSort(vec, vec.size());
for (auto it : vec)
{
cout << it << " ";
}
return 0;
}解析
時(shí)間復(fù)雜度：
第一次排序時(shí)是n個(gè)元素，比較n-1次
第二次排序時(shí)是n-1個(gè)元素，比較n-2次
...
第n-1次排序時(shí)是2個(gè)元素，比較1次
第n次排序時(shí)是1個(gè)元素，比較0次
元素交換次數(shù)為k(k<n-1次）
時(shí)間復(fù)雜度=比較次數(shù)+交換次數(shù)
故選擇排序時(shí)間復(fù)雜度為O(1+2+3+...+n-1+k)=O(n*(n-1)/2+k)=O(n2)
空間復(fù)雜度：
在原數(shù)組上操作，即使用了常數(shù)級(jí)空間O(1)。
穩(wěn)定性
穩(wěn)定性是指排序之后相同的數(shù)相對(duì)位置不變。
實(shí)例：3 2 3 1 從小到大排序（選擇最小的放前面），排序之后第二個(gè)3在第一個(gè)3前面，所以不穩(wěn)定。
到此這篇關(guān)于C++排序算法之選擇排序解析的文章就介紹到這了,更多相關(guān)C++選擇排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實(shí)現(xiàn)評(píng)教管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)評(píng)教管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
圖解C++的STL之stack和queue,輕松理解數(shù)據(jù)結(jié)構(gòu)
聚焦?C++?的?STL?中的?stack?和?queue,讓數(shù)據(jù)結(jié)構(gòu)變得簡(jiǎn)單有趣!?通過圖解的方式,我們將輕松理解這兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu),準(zhǔn)備好開啟?STL?學(xué)習(xí)之旅了嗎?讓我們一起探索?stack?和?queue?的奧秘吧!2024-03-03
本文主要介紹了C++11 智能指針的具體使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了C/C++中組合的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
Qt圖形圖像開發(fā)之曲線圖表庫(kù)QChart編譯安裝詳細(xì)方法與使用實(shí)例
這篇文章主要介紹了Qt圖形圖像開發(fā)之曲線圖表庫(kù)QChart編譯安裝詳細(xì)方法與使用實(shí)例,需要的朋友可以參考下2020-03-03
C++簡(jiǎn)易通訊錄系統(tǒng)實(shí)現(xiàn)流程詳解
這篇文章主要為大家介紹了C語(yǔ)言簡(jiǎn)易版通訊錄的具體實(shí)現(xiàn)流程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
C語(yǔ)言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解
我們知道c語(yǔ)言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過本文給大家分享c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷毀過程，一起看看吧2022-05-05
這篇文章主要為大家詳細(xì)介紹了C++通過COM接口操作PPT的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05
這篇文章主要為大家詳細(xì)介紹了C++的類與對(duì)象，使用數(shù)據(jù)庫(kù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C++使用CriticalSection實(shí)現(xiàn)線程同步實(shí)例
這篇文章主要介紹了C++使用CriticalSection實(shí)現(xiàn)線程同步實(shí)例,是使用CriticalSection對(duì)前文實(shí)例的擴(kuò)展,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-10-10