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)對應(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ù)級空間O(1)。
穩(wěn)定性
穩(wěn)定性是指排序之后相同的數(shù)相對位置不變。
實(shí)例：3 2 3 1 從小到大排序（選擇最小的放前面），排序之后第二個(gè)3在第一個(gè)3前面，所以不穩(wěn)定。
到此這篇關(guān)于C++排序算法之選擇排序解析的文章就介紹到這了,更多相關(guān)C++選擇排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本章主要介紹C++的內(nèi)存管理，以C++的內(nèi)存分布作為引入，介紹C++不同于C語言的內(nèi)存管理方式（new delete對比 malloc free)，最后為了加深讀者的理解，會介紹new和delete的底層實(shí)現(xiàn)原理2021-11-11
這篇文章主要介紹了C++中 string 中的常用方法使用心得，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03
C語言實(shí)現(xiàn)動態(tài)版通訊錄的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C語言實(shí)現(xiàn)一個(gè)簡單的動態(tài)版通訊錄，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C語言有一定幫助，需要的可以參考一下2022-08-08
這篇文章主要為大家詳細(xì)介紹了c語言實(shí)現(xiàn)簡單的五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
運(yùn)算符重載使自定義類型支持內(nèi)置運(yùn)算符操作,提升代碼可讀性,通過成員或全局函數(shù)實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-07-07
C++中的類型查詢之探索typeid和type_info(推薦)
C++ 是一種靜態(tài)類型語言,這意味著每個(gè)變量的類型在編譯時(shí)就已經(jīng)確定,在這篇技術(shù)分享中,我們將探討 C++ 中的 typeid 和 type_info,以及如何使用它們來獲取類型信息,需要的朋友可以參考下2024-05-05
之所以寫這個(gè)繪制簡單三角形的實(shí)例其實(shí)是想知道如何在Unreal中通過代碼繪制自定義Mesh，如果你會繪制一個(gè)三角形，那么自然就會繪制復(fù)雜的Mesh了。所以這是很多圖形工作者的第一課，快跟隨小編一起學(xué)習(xí)起來吧2023-02-02
關(guān)于C/C++中的side effect(負(fù)效應(yīng))和sequence point(序列點(diǎn))
不知你在寫code時(shí)是否遇到這樣的問題？int i = 3; int x = (++i) + (++i) + (++i); 問x值為多少？進(jìn)行各種理論分析，并在編譯器上實(shí)踐，然而可能發(fā)現(xiàn)最終的結(jié)果是不正確的，也是不穩(wěn)定的，不同的編譯器可能會產(chǎn)生不同的結(jié)果。這讓人很頭疼2013-10-10
這篇文章主要為大家詳細(xì)介紹了C++的原生數(shù)組，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
《戰(zhàn)狼》中兩軍作戰(zhàn)入侵代碼竟然是輸出星期幾的！
這篇文章主要介紹了《戰(zhàn)狼》中兩軍作戰(zhàn)入侵代碼竟然是輸出星期幾的，喜歡戰(zhàn)狼和編程的同學(xué)可以了解下。2017-11-11