摘要:以此類推,直到所有元素均排序完畢。老師說,隊列都給你們排好了,小明同學(xué)也又很好的闡述了思想,你們把代碼實現(xiàn)以下吧哈哈哈。
一、說在前面
一直想寫一些簡單易懂的文章,因為平時看的很多的書籍或者文章都是看著很難受的感覺,當(dāng)然,這并不是說書籍寫的不好,只是說對于一些沒有太多基礎(chǔ)或者基礎(chǔ)不是很好的來說,相對來說還是比較難以理解的。
這個系列主要是寫一些簡單易懂的數(shù)據(jù)結(jié)構(gòu)與算法的文章,同時也是幫助自己再理解理解這方面的知識。
作為數(shù)據(jù)結(jié)構(gòu)與算法的開篇,還是以排序算法作為第一部分的內(nèi)容,需要注意的是,這一系列的文章并不是涉及到很多理論性質(zhì)的知識,因為前面說了,主要還是希望文章是簡單易懂的,希望能達(dá)到讀故事的感覺。如果需要去學(xué)習(xí)理論性質(zhì)的知識,可以去查看相關(guān)的數(shù)據(jù)結(jié)構(gòu)與算法的書籍。
二、選擇排序算法今天早上,老師又叫我們?nèi)ゲ賵錾献鲈绮伲鲈绮僦澳兀裉煲残枰抨牐讲賵龅耐瑢W(xué)有5個人,今天的排序方法還是按照身高由低到高排列。
但是,今天老師說換一種方法排隊,我來給你們排隊,昨天你們排隊太慢了。
于是,老師說:第一個同學(xué)站在原地不要動。
然后,我從后面4個同學(xué)當(dāng)中挑一個最矮的同學(xué),這個同學(xué)站在第一個同學(xué)后面,你們兩個站在原地不要動。
之后,老師再從后面3個同學(xué)里面挑一個最矮的同學(xué),然后讓他站在前面兩個排好的同學(xué)后面,這樣這三個同學(xué)就排好了,你們站著不要動。
老師又從最后兩個同學(xué)中挑一個最矮的同學(xué),讓他站在前面三個已經(jīng)排好的隊伍后面,這樣,這四個同學(xué)就排好隊列,這四個同學(xué)站著不要動。
四個同學(xué)排好了,只有最后一個同學(xué)了,然后,這個同學(xué)自己站到前面四個已經(jīng)排好隊的隊伍的最后,這樣5個同學(xué)的位置就排好了。
老師看到排好了隊,非常開心,對同學(xué)們說:“我排隊是不是比你們自己排隊快啊!”
然后,這位程序員老師說,哪位同學(xué)懂了剛剛我給你們排隊的思想,能不能敘述一下,這時候,小明說:我會!,于是,小明說了一下思想:
初始時在隊伍中找到最小(大)元素,放到隊伍的起始位置作為已排好隊伍;然后,再從剩余未排序隊伍中繼續(xù)尋找最小(大)元素,放到已排序隊伍的末尾。以此類推,直到所有元素均排序完畢。
老師說,隊列都給你們排好了,小明同學(xué)也又很好的闡述了思想,你們把代碼實現(xiàn)以下吧(哈哈哈!)。
于是,小海同學(xué)就去按照老師的排隊方法,實現(xiàn)了選擇排序算法
</>復(fù)制代碼
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
//在待排序區(qū)選擇最小的元素
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);// 放到已排序序列的末尾,該操作很有可能把穩(wěn)定性打亂,所以選擇排序是不穩(wěn)定的排序算法
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
最差時間復(fù)雜度:O(n^2)
最優(yōu)時間復(fù)雜度:O(n^2)
平均時間復(fù)雜度: O(n^2)
所需輔助空間:O(1)
穩(wěn)定性:不穩(wěn)定
</>復(fù)制代碼
文章有不當(dāng)之處,歡迎指正,如果喜歡微信閱讀,你也可以關(guān)注我的微信公眾號:好好學(xué)java,獲取優(yōu)質(zhì)學(xué)習(xí)資源。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/75721.html
摘要:二冒泡排序算法作為這一系列的第一部分,主要講解排序算法。直到隊列全部排好為止。到這里,我想你應(yīng)該明白了冒泡排序的思想了。 一、說在前面 一直想寫一些簡單易懂的文章,因為平時看的很多的書籍或者文章都是看著很難受的感覺,當(dāng)然,這并不是說書籍寫的不好,只是說對于一些沒有太多基礎(chǔ)或者基礎(chǔ)不是很好的來說,相對來說還是比較難以理解的。 這個系列主要是寫一些簡單易懂的數(shù)據(jù)結(jié)構(gòu)與算法的文章,同時也是幫...
摘要:聽了鵬哥的教導(dǎo),也開始寫起了博客現(xiàn)在多粉,感覺都是機(jī)器人哈哈,最近粉絲也不漲了,不知道是不是我最近不發(fā)文章的原因。這一個多月,基本就是學(xué)刷算法題。在這里不得不吐槽一下學(xué)校,每條早上做早操,晚自習(xí)到點,感覺浪費了我很多學(xué)習(xí)技術(shù)的時間。 ...
摘要:基本介紹選擇式排序也屬于內(nèi)部排序法,是從欲排序的數(shù)據(jù)中,按指定的規(guī)則選出某一元素,再依規(guī)定交換位置后達(dá)到排序的目的。而移動次數(shù)與序列的初始排序有關(guān)。空間復(fù)雜度簡單選擇排序需要占用個臨時空間,在交換數(shù)值時使用。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://segmentfault....
摘要:經(jīng)過一次冒泡排序,最終在無序表中找到一個最大值,第一次冒泡結(jié)束。也是我們后面要說的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán),而不會執(zhí)行第二層循環(huán)。因此冒泡排序的時間復(fù)雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要:選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數(shù)據(jù)時有兩種基本方式數(shù)組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。 選擇排序是下一章將介紹的快速排序的基石。 內(nèi)存的工作原理 計算機(jī)就像是很多抽屜的集合體,每個抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...
閱讀 956·2021-09-26 09:55
閱讀 3218·2021-09-22 15:36
閱讀 2997·2021-09-04 16:48
閱讀 3154·2021-09-01 11:41
閱讀 2607·2019-08-30 13:49
閱讀 1503·2019-08-29 18:46
閱讀 3556·2019-08-29 17:28
閱讀 3441·2019-08-29 14:11