資訊專欄INFORMATION COLUMN
摘要：二冒泡排序算法作為這一系列的第一部分，主要講解排序算法。直到隊列全部排好為止。到這里，我想你應該明白了冒泡排序的思想了。
一、說在前面
一直想寫一些簡單易懂的文章，因為平時看的很多的書籍或者文章都是看著很難受的感覺，當然，這并不是說書籍寫的不好，只是說對于一些沒有太多基礎或者基礎不是很好的來說，相對來說還是比較難以理解的。
這個系列主要是寫一些簡單易懂的數據結構與算法的文章，同時也是幫助自己再理解理解這方面的知識。
作為數據結構與算法的開篇，還是以排序算法作為第一部分的內容，需要注意的是，這一系列的文章并不是涉及到很多理論性質的知識，因為前面說了，主要還是希望文章是簡單易懂的，希望能達到讀故事的感覺。如果需要去學習理論性質的知識，可以去查看相關的數據結構與算法的書籍。
二、冒泡排序算法作為這一系列的第一部分，主要講解排序算法。從小到大，我們至少前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
