C++實(shí)現(xiàn)選擇性排序(SelectionSort)
“選擇性排序”是數(shù)列排序的算法之一。
其思路引點(diǎn)來(lái)源于經(jīng)典的“可樂(lè)雪碧問(wèn)題”
“現(xiàn)有兩杯飲料,一杯是雪碧,一杯是可樂(lè),試問(wèn)如何可以將兩杯飲料交換?”
“答:最簡(jiǎn)單的解決方案就是利用一個(gè)空杯,創(chuàng)造一個(gè)緩存區(qū)。”
選擇性排序就是利用線性搜索數(shù)列并找到當(dāng)前最小值,通過(guò)不斷的將當(dāng)前最小值放置當(dāng)前位置索引的算法。
1、算法思路
這是一個(gè)未排序的數(shù)列。
首先,線性搜索數(shù)列,找到最小值。
將最小值替換為列中左端的數(shù)字并進(jìn)行排序,如果最小值已經(jīng)在左端,則不執(zhí)行任何操作。
重復(fù)相同操作,直到所有的數(shù)字都被排序。
3、動(dòng)畫(huà)演示
4、代碼清單及其測(cè)試結(jié)果
#include <iostream> template <class T> int getSizeOfArray(T& ss){ return sizeof(ss)/ sizeof(ss[0]); } void selectionSort(int * ss,int size){ for(int i=0;i<size-1;i++){ int minimalIndex = i;//初始化當(dāng)前范圍內(nèi)最小值索引 for(int j=i+1;j<size;j++){//查找當(dāng)前范圍內(nèi)最小值索引 if(ss[j]<ss[minimalIndex]){ minimalIndex = j; } } if(minimalIndex!=i){//如果當(dāng)前范圍內(nèi)最小值索引不為初始化索引,才進(jìn)行交換 int cup = 0; cup = ss[i]; ss[i] = ss[minimalIndex]; ss[minimalIndex] = cup; } } } int main() { using namespace std; int ss[] = {2,3,5,1,0,8,6,9,7}; int size = getSizeOfArray(ss); cout<< "原數(shù)列:"; for(int i = 0;i<size;i++) { cout<< ss[i] << " "; } cout<< "\n" << "選擇性排序后:"; selectionSort(ss,size); for(int i = 0;i<size;i++) { cout<< ss[i] << " "; } return 0; }
6. 算法分析
時(shí)間復(fù)雜度
選擇排序的交換操作介于 0 和 (n - 1) 次之間。選擇排序的比較操作為 n (n - 1) / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1) 次之間。
比較次數(shù)O(n^2),比較次數(shù)與關(guān)鍵字的初始狀態(tài)無(wú)關(guān),總的比較次數(shù)N=(n-1)+(n-2)+…+1=n*(n-1)/2。交換次數(shù)O(n),最好情況是,已經(jīng)有序,交換0次;最壞情況交換n-1次,逆序交換n/2次。交換次數(shù)比冒泡排序少多了,由于交換所需CPU時(shí)間比比較所需的CPU時(shí)間多,n值較小時(shí),選擇排序比冒泡排序快。
穩(wěn)定性
選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,比如給第一個(gè)位置選擇最小的,在剩余元素里面給第二個(gè)元素選擇第二小的,依次類(lèi)推,直到第n-1個(gè)元素,第n個(gè)元素不用選擇了,因?yàn)橹皇O滤粋€(gè)最大的元素了。那么,在一趟選擇,如果一個(gè)元素比當(dāng)前元素小,而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面,那么交換后穩(wěn)定性就被破壞了。比較拗口,舉個(gè)例子,序列5 8 5 2 9,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中兩個(gè)5的相對(duì)前后順序就被破壞了,所以選擇排序是一個(gè)不穩(wěn)定的排序算法。 [1]
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語(yǔ)言超細(xì)致講解循環(huán)語(yǔ)句
我們說(shuō)到當(dāng)滿(mǎn)足特定條件時(shí),就會(huì)執(zhí)行if語(yǔ)句或者switch語(yǔ)句后面的語(yǔ)句,否則不執(zhí)行,但是這只能執(zhí)行一次,在日常生活中,有些事情是需要重復(fù)去做的,C語(yǔ)句就為此引入了循環(huán)語(yǔ)句。所以今天繼續(xù)為大家分享C語(yǔ)言循環(huán)家族2022-05-05一起來(lái)學(xué)習(xí)C語(yǔ)言的輸入和輸出
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言的輸入和輸出,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-03-03C/C++ 中怎樣使用SetConsoleTextAttribute()函數(shù)來(lái)控制輸出字符的顏色
這篇文章主要介紹了C/C++ 中如何使用SetConsoleTextAttribute()函數(shù)來(lái)控制輸出字符的顏色,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-03-03C語(yǔ)言中變量與其內(nèi)存地址對(duì)應(yīng)的入門(mén)知識(shí)簡(jiǎn)單講解
這篇文章主要介紹了C語(yǔ)言中變量與其內(nèi)存地址對(duì)應(yīng)的入門(mén)知識(shí)簡(jiǎn)單講解,同時(shí)這也是掌握指針部分知識(shí)的基礎(chǔ),需要的朋友可以參考下2015-12-12C++獲取字符串長(zhǎng)度的幾個(gè)函數(shù)方式
這篇文章主要介紹了C++獲取字符串長(zhǎng)度的幾個(gè)函數(shù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12C語(yǔ)言實(shí)現(xiàn)從文件讀入一個(gè)3*3數(shù)組,并計(jì)算每行的平均值
今天小編就為大家分享一篇C語(yǔ)言實(shí)現(xiàn)從文件讀入一個(gè)3*3數(shù)組,并計(jì)算每行的平均值,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12C語(yǔ)言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01C語(yǔ)言用棧和隊(duì)列實(shí)現(xiàn)的回文檢測(cè)功能示例
這篇文章主要介紹了C語(yǔ)言用棧和隊(duì)列實(shí)現(xiàn)的回文檢測(cè)功能,結(jié)合具體實(shí)例形式分析了C語(yǔ)言棧和隊(duì)列的定義及使用棧和隊(duì)列進(jìn)行回文檢測(cè)的操作技巧,需要的朋友可以參考下2017-06-06詳解C++的靜態(tài)內(nèi)存分配與動(dòng)態(tài)內(nèi)存分配
內(nèi)存分配 (Memory Allocation) 是指為計(jì)算機(jī)程序或服務(wù)分配物理內(nèi)存空間或虛擬內(nèi)存空間的一個(gè)過(guò)程,本文主要介紹了C++的靜態(tài)內(nèi)存分配與動(dòng)態(tài)內(nèi)存分配,感興趣的同學(xué)可以參考閱讀2023-06-06