1 選擇排序法的定義
選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理是:第一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素,存放在序列的起始位置,然后再?gòu)氖S嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪病R源祟愅疲钡饺看判虻臄?shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。(來(lái)自百度百科)
2 選擇排序法詳細(xì)過(guò)程解析
假定有這樣一個(gè)數(shù)組
int[] nums = new int[]{6, 4, 5, 1, 3, 2};
現(xiàn)在需要將他從大到小排列。
選擇排序法代碼如下:
排序詳細(xì)過(guò)程:
[6, 4, 5, 1, 3, 2] 第一次遍歷6和2交換位置
[6, 5, 4, 1, 3, 2] 第二次遍歷5和4交換位置
[6, 5, 4, 1, 3, 2] 第三次遍歷4位置不變
[6, 5, 4, 3, 1, 2] 第四次遍歷3和1交換位置
[6, 5, 4, 3, 2, 1] 第五次遍歷2和1交換位置
3 選擇排序法時(shí)間復(fù)雜度
數(shù)據(jù)比較次數(shù):
C = (N-1)+(N-2)+……+2+1=(((N-1)+1)*(N-1)) / 2=(N^2)/2-N/2
數(shù)據(jù)交換次數(shù):
M = N-1
時(shí)間復(fù)雜度:
C+M=(N^2)/2-N/2+ N-1=O(N^2)
因此,選擇排序的時(shí)間復(fù)雜度為O(N^2)
4 結(jié)語(yǔ)
感謝各位的閱讀,如有問(wèn)題,歡迎大家留言反饋,我會(huì)在第一時(shí)間修正。
-
算法
+關(guān)注
關(guān)注
23文章
4706瀏覽量
95175 -
C語(yǔ)言
+關(guān)注
關(guān)注
180文章
7631瀏覽量
141148 -
排序算法
+關(guān)注
關(guān)注
0文章
53瀏覽量
10237
發(fā)布評(píng)論請(qǐng)先 登錄
HarmonyOS實(shí)戰(zhàn):自定義時(shí)間選擇器

低成本電源排序器解決方案

如何選擇適合您的過(guò)程控制器?

數(shù)字電路—13、數(shù)據(jù)選擇器
PID控制算法的C語(yǔ)言實(shí)現(xiàn):PID算法原理
詳解Linux sort命令之掌握排序技巧與實(shí)用案例
TimSort:一個(gè)在標(biāo)準(zhǔn)函數(shù)庫(kù)中廣泛使用的排序算法
加密算法的選擇對(duì)于加密安全有多重要?
直播報(bào)名丨第3講:如何選擇合適的算法模塊

智能選擇ADC/DAC可實(shí)現(xiàn)更好的軟件定義無(wú)線電設(shè)計(jì)

時(shí)間復(fù)雜度為 O(n^2) 的排序算法

評(píng)論