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