前言
筆者屬于算法小白一枚欺栗，本系列文章屬于算法的學習筆記娶牌，也希望能給算法小小白起到些許的指引作用餐曹。如果有算法大佬不小心點了進來虑瀑，只能說一聲抱歉打擾了湿滓。
正文
題目
請實現一個冒泡排序，升序排列舌狗。
原理
- 比較相鄰的元素叽奥，如果前面一個比后面一個大，就交換他們兩個痛侍。
- 對每一對相鄰元素作同樣的工作朝氓，從開始的一對到結尾的最后一對。這步做完以后主届，最大元素就在隊列尾部赵哲。
- 重復以上步驟，找出第二大君丁、第三大的元素等等依次排列在尾部枫夺，直到沒有任何一對數字需要比較。
實現
冒泡排序需要兩層循環(huán)才能實現绘闷，個人建議先梳理清楚一層循環(huán)做了什么事情橡庞，得到了什么結果较坛，最后再加上一層循環(huán)嵌套，思路會更清晰一些毙死。
假設待排序的數組：[6, 4, 2, 1, 8, 3, 7, 9, 5]
我們在一層循環(huán)里面想要將最大的元素放在隊列尾部燎潮，結合算法原理喻鳄，不難寫出以下代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
System.out.println(Arrays.toString(array));
}
得到數組：[4, 2, 1, 6, 3, 7, 8, 5, 9]
分析：
- 數組一共9個元素扼倘，現在找到了最大的元素，并且這個元素在隊列尾部除呵。
- 接下來我只需要在剩下的8個元素里面找到第二大的元素就好了再菊。
繼續(xù)寫代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
for (int j = 0; j < array.length - 2; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
System.out.println(Arrays.toString(array));
}
得到數組：[2, 1, 4, 3, 6, 7, 5, 8, 9]
分析：
- 仔細觀察兩段 for 循環(huán)代碼，不難發(fā)現唯一的區(qū)別就是
array.length - 1和array.length - 2颜曾。 - 容易想到纠拔，當我們想要在剩余的7個元素里面找到第三大的元素的時候，對應的就是
array.length - 3泛豪。抽象出來就是array.length - i稠诲。 - 那么我們最終需要減到哪個數字為止呢？很簡單诡曙，
對9個元素排序臀叙，只需要進行8次即可。 - 就這樣价卤，新的一層循環(huán)嵌套已經呼之欲出了劝萤。
int i = 1; i < array.length; i++。
改進代碼：
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
for (int i = 1; i < array.length; i++) {
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
System.out.println(Arrays.toString(array));
}
到這里慎璧，一個完整的冒泡排序就實現了床嫌。
實際上，這并不是最完美的實現胸私，因為如果待排序的數組內部已經有序厌处，比如[1, 2, 3, 4, 5, 6, 7, 8, 9]，以上代碼還是會老老實實的依次比對岁疼，盡管它不會交換數據阔涉。因此，我們可以增加一個標記位用于判斷一次比對過程當中是否交換了數據五续，如果沒有洒敏，則代表數組已經有序，直接退出循環(huán)即可疙驾。
最終代碼：
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 1; i < array.length; i++) {
boolean exchange = false;
for (int j = 0; j < array.length - i; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
exchange = true;
}
}
if (!exchange) {
break;
}
}
System.out.println(Arrays.toString(array));
}
總結
冒泡排序是一個非常簡單的入門級排序凶伙，它具有如下特點：
- 時間復雜度是O(n2)。
- 空間復雜度是O(1)它碎。
- 是一個穩(wěn)定排序函荣。
請深入理解了它的實現以后显押，在純文本編輯的環(huán)境下手撕了它。
