摘要:二冒泡排序算法作為這一系列的第一部分,主要講解排序算法。直到隊列全部排好為止。到這里,我想你應該明白了冒泡排序的思想了。
一、說在前面
一直想寫一些簡單易懂的文章,因為平時看的很多的書籍或者文章都是看著很難受的感覺,當然,這并不是說書籍寫的不好,只是說對于一些沒有太多基礎或者基礎不是很好的來說,相對來說還是比較難以理解的。
這個系列主要是寫一些簡單易懂的數據結構與算法的文章,同時也是幫助自己再理解理解這方面的知識。
作為數據結構與算法的開篇,還是以排序算法作為第一部分的內容,需要注意的是,這一系列的文章并不是涉及到很多理論性質的知識,因為前面說了,主要還是希望文章是簡單易懂的,希望能達到讀故事的感覺。如果需要去學習理論性質的知識,可以去查看相關的數據結構與算法的書籍。
二、冒泡排序算法作為這一系列的第一部分,主要講解排序算法。從小到大,我們至少前20年的時間都是在學校度過了,校園生活在我看來是十分的美好的,以至于現在我都還在校園里面生活。在我們讀書的階段,是不是經常會碰到排隊的時候,因為大家都熟悉這一場景,所以,我們就一排隊來講解排序算法。
冒泡算法應該是我們最熟悉不過的算法了,也是我們最熟悉不過的排隊了,既然熟悉不過,那么我們今天就來排個冒泡排序的隊列吧。
今天早上,老師叫我們去操場上做早操,做早操之前呢,需要排隊,排隊都有一個排法,不是嗎?那么,老師今天就要求我們按照身高由低到高依次排好。
于是,我們早上很快就一起到了操場上,總共有5個人到了操場,剛剛去的時候,隊列肯定是散的對吧,這時候的隊列是下面這樣子的:第0個位置站的小明,第1個位置站的小海,第2個位置站的小劉,第3個位置站的小李,第5個位置站的小愛。
于是老師(假設老師是一個程序員哈,皮一下)要求我們按照冒泡排序的方法排好隊:挨個的比較身高,如果比下一個位置上的同學高,就換一下位置。
好了,同學們聽到老師的指示之后呢,同學們就開始動身了。
第0個位置上的小明同學和第1個位置上的小海同學相互比了一下身高,發現第1個位置上的小海同學(1.80m)比第0個位置上的小海同學(1.60m)高,于是就保持不動,所以第一次排隊后,隊列還是保持不變的。
接下來,第1個位置上的小海同學還想和第2個位置上的小劉同學比一下身高,發現第1個位置上的小海同學比第2個位置上的小劉同學高,所以,他們互換一下位置。
于是,隊列成了下面的樣子,小海和小劉換了一下位置。
之后,第2個位置上的小海同學,又和第3個位置上的小李同學比了一下身高,發現,第2個位置上的小海同學還是比第3個位置上的小李同學高,所以他們還是需要交換一下位置的。
這時候,隊列變成了下面的樣子,小海和小李互換。
接下來第3個位置上的小海同學和第4個位置上的小愛同學進行了身高的比較,發現第3個位置上的小海同學還是比第4個位置上的小愛同學高,所以又需要換一下。
交換后,變成了這樣子:
結果我們發現,通過這種排序方法,最高的小海從第2個位置上跑到了最后一個位置
好了,現在最高的小海的位置已經確定了,我們就不管他了,我們又從第0個位置上的同學開始,第0個位置的小明同學和第1個位置的小劉同學比較身高,發現小明的身高比小劉的矮,所以隊列維持不變。
接下來,第1個位置上的小劉和第2個位置上的小李比較,發現,小劉比小李高,所以需要交換位置
交換后,變成了下面的隊列
然后,第2個位置上的小劉和相鄰的第3個位置上的小愛比較身高,發現小愛比小劉高,所以不交換位置
最后一個位置的小海因為第一輪已經知道他最高了,所以不與他比較了,因此,這輪排完之后,我們發現,整個序列已經是有序的了,我們看一下隊列的變化。
從這排隊的過程中,我們是不是發現了冒泡排序的思想:
第一遍,第一個位置上的同學開始,挨個的比較身高,如果第0個位置的同學比第1個位置的同學高,就交換位置,否則,不換位置,然后,第1個位置與第2個位置的同學比一下身高,如果第1個位置的同學高比第2個位置的同學高,交換位置,否則不換,以此類推,最高的同學將會到最后一個位置上。
第二遍,還是從第一個位置上的同學開始,第1個同學和第2個同學比較,如果第一個同學比第二個同學高,交換位置,否則不變,然后,第2個位置上的同學和第3個位置的同學比較,如果第2個位置的同學高,則交換位置,否則不換。這一遍,因為第一遍已經找出來最高的同學在最后一個位置,所以最后一個位置不用比較了。
直到隊列全部排好為止。
到這里,我想你應該明白了冒泡排序的思想了。
接下來,我們看一下代碼的實現(這里我們使用Java代碼實現)。
public static void bubbleSort(int[] arr) { //如果數組為空,或者元素為1,直接返回。 if (arr == null || arr.length < 2) { return; } for (int e = 0; e < arr.length - 1; e++) {//每次最大元素就像氣泡一樣"浮"到數組的最后 for (int i = 0; i < n-1-e; i++) {//n-1-e:-1是因為元素從0下表開始,-e是因為可以減去已排到最后的幾個元素,可以減少比較次數。 if (arr[i] > arr[i + 1]) {//如果大于下一個位置 swap(arr, i, i + 1);//交換位置 } } } } /** * 交換元素位置 * @param arr * @param i * @param j */ public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
最差時間復雜度:O(n^2)
最優時間復雜度:如果已經是有序的,可以把最優時間復雜度降低到O(n)
平均時間復雜度:O(n^2)
所需輔助空間:O(1)
穩定性:穩定
穩定性說明:排序穩定不穩定,就是看每次排序的過程中,是否會改變整個序列的位置。
文章有不當之處,歡迎指正,如果喜歡微信閱讀,你也可以關注我的微信公眾號:好好學java,獲取優質學習資源。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75720.html
摘要:以此類推,直到所有元素均排序完畢。老師說,隊列都給你們排好了,小明同學也又很好的闡述了思想,你們把代碼實現以下吧哈哈哈。 一、說在前面 一直想寫一些簡單易懂的文章,因為平時看的很多的書籍或者文章都是看著很難受的感覺,當然,這并不是說書籍寫的不好,只是說對于一些沒有太多基礎或者基礎不是很好的來說,相對來說還是比較難以理解的。 這個系列主要是寫一些簡單易懂的數據結構與算法的文章,同時也是幫...
摘要:經過一次冒泡排序,最終在無序表中找到一個最大值,第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環,而不會執行第二層循環。因此冒泡排序的時間復雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...
摘要:聽了鵬哥的教導,也開始寫起了博客現在多粉,感覺都是機器人哈哈,最近粉絲也不漲了,不知道是不是我最近不發文章的原因。這一個多月,基本就是學刷算法題。在這里不得不吐槽一下學校,每條早上做早操,晚自習到點,感覺浪費了我很多學習技術的時間。 ...
閱讀 825·2023-04-26 00:13
閱讀 2794·2021-11-23 10:08
閱讀 2432·2021-09-01 10:41
閱讀 2112·2021-08-27 16:25
閱讀 4177·2021-07-30 15:14
閱讀 2359·2019-08-30 15:54
閱讀 857·2019-08-29 16:22
閱讀 2736·2019-08-26 12:13