??個(gè)人主頁(yè):修修修也
??所屬專欄:數(shù)據(jù)結(jié)構(gòu)
??操作環(huán)境:Visual Studio 2022
目錄
一.簡(jiǎn)單選擇排序簡(jiǎn)介及思路
二.簡(jiǎn)單選擇排序的代碼實(shí)現(xiàn)
三.簡(jiǎn)單選擇排序的優(yōu)化
四.簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度分析
結(jié)語(yǔ)
一.簡(jiǎn)單選擇排序簡(jiǎn)介及思路
簡(jiǎn)單選擇排序算法(Simple Selection Sort)是一種簡(jiǎn)單直觀的選擇排序算法.
它的基本操作是:
- 每一次通過(guò)n-i次關(guān)鍵字間的比較,從n-i+1個(gè)數(shù)據(jù)中選出關(guān)鍵字最小(大)的數(shù)據(jù),并和第i(1≤i≤n)個(gè)數(shù)據(jù)交換
- 重復(fù)n-1次上述操作,直到全部待排序的數(shù)據(jù)元素排完.
算法動(dòng)圖演示如下:
二.簡(jiǎn)單選擇排序的代碼實(shí)現(xiàn)
算法實(shí)現(xiàn)步驟:(以升序?yàn)槔?
- 在元素集合arr[i]~arr[n-1]中選擇關(guān)鍵碼最小(大)的數(shù)據(jù)元素.
- 若它不是這組元素中的第一個(gè)(最后一個(gè))元素,則將它與這組元素中的第一個(gè)(最后一個(gè))元素交換.
- 在剩余的arr[i+1]~arr[n-1](arr[i]~arr[n-2])集合中,重復(fù)上述步驟,直到集合剩余一個(gè)元素.
清楚了實(shí)現(xiàn)步驟后,代碼的實(shí)現(xiàn)就比較簡(jiǎn)單了,代碼如下:
//交換函數(shù)
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//直接選則排序(升序
void SelectSort(int* a, int n)
{
int left = 0;
while (left < n - 1)
{
int mini = left;
for (int i = left + 1; i <= n - 1; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[left], &a[mini]);
left++;
}
}三.簡(jiǎn)單選擇排序的優(yōu)化
我們?cè)谠O(shè)計(jì)簡(jiǎn)單選擇排序時(shí),思路往往都是每趟循環(huán)選出一個(gè)最大或最小的將其放在相應(yīng)位置上,那么其實(shí)我們可不可以一趟直接將最大和最小的兩個(gè)元素都選出來(lái)呢?
依照這個(gè)思路,我們對(duì)簡(jiǎn)單選擇排序進(jìn)行優(yōu)化,使其一趟就可以將最大的元素和最小的元素都選出來(lái)交換到相應(yīng)的位置上,綜上,代碼實(shí)現(xiàn)如下:
//交換
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//選擇排序(直接選擇排序)
void SelectSort(int* a, int n)
{
//優(yōu)化:一趟選出最大和最小的
int left = 0;
int right = n - 1;
while (left < right)
{
int mini = left, maxi = left;
for (int i = left + 1; i <= right; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[left], &a[mini]);
//如果left和maxi重疊,交換后需要修正一下再交換right和maxi
if (left == maxi)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
left++;
right--;
}
}
注意:
??????? 當(dāng)我們?cè)谝惶吮容^結(jié)束后選出mini和maxi并做交換的時(shí)候,要小心如果left記錄的位置恰好存放的是maxi,則第一步交換left和mini后我們就要重新對(duì)maxi的位置做一個(gè)修正,如圖:
四.簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度分析
我們可以發(fā)現(xiàn),簡(jiǎn)單選擇排序的特點(diǎn)是:
???????? 元素挪動(dòng)交換次數(shù)很少,但是元素比較次數(shù)很多,并且無(wú)論是數(shù)組天生順序的情況還是天生逆序的情況,元素比較次數(shù)都是一樣的,都是:T(n)=(n-1)+(n-2)+...+2+1=n(n-1) / 2 次.
????????? 而對(duì)于交換次數(shù)而言,最好的時(shí)候,交換次數(shù)為0次,最壞的時(shí)候,交換次數(shù)為n-1次.
????????? 基于最終的排序時(shí)間是交換次數(shù)和比較次數(shù)的總和,因此,總的時(shí)間復(fù)雜度依然是O(n^2).
結(jié)語(yǔ)
希望這篇簡(jiǎn)單選擇排序算法詳解能對(duì)大家有所幫助,歡迎大佬們留言或私信與我交流.
有關(guān)更多排序相關(guān)知識(shí)可以移步:
【數(shù)據(jù)結(jié)構(gòu)】八大排序算法?https://blog.csdn.net/weixin_72357342/article/details/135038495?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22135038495%22%2C%22source%22%3A%22weixin_72357342%22%7D&fromshare=blogdetail
學(xué)海漫浩浩,我亦苦作舟!關(guān)注我,大家一起學(xué)習(xí),一起進(jìn)步!
?相關(guān)文章推薦
【數(shù)據(jù)結(jié)構(gòu)】八大排序之冒泡排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序之希爾排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序之直接插入排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序之簡(jiǎn)單選擇排序
【數(shù)據(jù)結(jié)構(gòu)】八大排序之堆排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序之快速排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序算法之歸并排序算法
【數(shù)據(jù)結(jié)構(gòu)】八大排序之計(jì)數(shù)排序算法
數(shù)據(jù)結(jié)構(gòu)排序算法篇思維導(dǎo)圖:
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-790986.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-790986.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】八大排序之簡(jiǎn)單選擇排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
