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